Fast Factorization Algorithm

Question

I am writing code in C that returns the number of times a positive integer can be expressed as the sum of perfect squares of two natural numbers.

R(n) is the number of couples (x,y) such that x² + y² = n where x, y, n are all non negative integers. 

To compute R (n), I need to first find a simple factorization of n.

The problem is that I tried many simple factorization algorithms that I can use in C, but I need my code to be as fast as possible, so I would appreciate if anyone could give me what he / it is considered the fastest algorithm for calculating a simple factorization of a number equal to 2147483742.

Answer 1

What an odd limit; 2147483742 = 2 ^ 31 + 94.

As others have pointed out, for a number this is a small trial division into prime numbers, most likely quite quickly. Only if this is not the case, you can try the Pollard Roe method:

 /* WARNING! UNTESTED CODE! */ long rho(n, c) { long t = 2; long h = 2; long d = 1; while (d == 1) { t = (t*t + c) % n; h = (h*h + c) % n; h = (h*h + c) % n; d = gcd(th, n); } if (d == n) return rho(n, c+1); return d; } 

Called as rho(n,1) , this function returns a (possibly compound) coefficient n; put it in a loop and name it again if you want to find all factors n. You will also need validation; for your limit, the Rabin-Miller test with bases 2, 7 and 61 proved its accuracy and reasonableness. You can learn more about programming with primes in my blog .

But in any case, given such a small limit, I think that you are better off using trial division by primes. Everything else can be asymptotically faster, but almost slower.

EDIT: This answer received a few recent posts, so I am adding a simple program that factorizes wheels with 2,3,5-wheels. Called as wheel(n) , this program prints the coefficients n in ascending order.

 long wheel(long n) { long ws[] = {1,2,2,4,2,4,2,4,6,2,6}; long f = 2; int w = 0; while (f * f <= n) { if (n % f == 0) { printf("%ld\n", f); n /= f; } else { f += ws[w]; w = (w == 10) ? 3 : (w+1); } } printf("%ld\n", n); return 0; } 

I discuss wheel factorization on my blog ; the explanation is long, so I will not repeat it here. For integers that match in long , it is unlikely that you can significantly improve the wheel function mentioned above.

Answer 2

There is a quick way to reduce the number of candidates. This procedure tries 2, then 3, then all the odd numbers are not divisible by 3.

 long mediumFactor(n) { if ((n % 2) == 0) return 2; if ((n % 3) == 0) return 3; try = 5; inc = 2; lim = sqrt(n); while (try <= lim) { if ((n % try) == 0) return try; try += inc; inc = 6 - inc; // flip from 2 -> 4 -> 2 } return 1; // n is prime } 

The insertion between 2 and 4 is carefully aligned so that it skips all even numbers and numbers divisible by 3. For this case: 5 (+2) 7 (+4) 11 (+2) 13 (+4) 17

Tests stop at sqrt (n), because at least one factor must be square root or lower. (If both factors were> sqrt (n), then the product of the factors would be greater than n.)

The number of attempts is sqrt (m) / 3, where m is the maximum possible number in your series. For a limit of 2147483647, which gives a maximum of 15,448 divisions of the worst case (for a prime number of about 2147483647), including 2 and 3 tests.

If the number is composite, the total number of divisions is usually much less and will very rarely be more; even taking into account the procedure call repeatedly to get all the factors.