Factor WITHOUT division / multiplication:

[Mark Jones]

Here's a version which uses pseudo-random values. I slopped the code together so maybe this is all wrong. Anyways here is my output:

Code Select Expand


Random number samples: 146891097 380636641 6240874 622665325 447979919

CPU Square Root Factoring: 112,167,130,136,147,156,138,136,159,154 cycles
FPU Square Root Factoring: 27,27,27,27,27,27,30,27,27,27 cycles

Press ENTER to exit...

[attachment deleted by admin]

[Posit]

Hello,

It is based on Fermat's factoring which makes use of the fact that (a + b)(a - b) = a^2 - b^2. What he is doing is searching for values of a and b such that a^2 - b^2 = the number he wants to factor. This type of factoring is good for factors that are close to each other for example 79 * 83.

I was going to mention that I initially analyzed the code assuming that's what it was based on (except my post was already long.) The initial multiplcation, which is a squaring, seemed to indicate that. The algebra works out OK that way, except that writing it all out leads to rather more involved expressions then what I presented. If Fermat factoring were the idea, then you would expect to calculate a+b and a-b at the end. And, strangely, nowhere are a+b or a-b calculated. Then I noticed all the expressions looked simpler expressed with the actual factors instead of a+b and a-b.

I don't know if the author started with Fermat factoring, but the only thing remaining in the code in common with it is that it starts with factors that are near the square root and works further away. The idea in this algorithm could be implemented the other way around, starting with a small factor. You really don't need Fermat's idea at all.

I've seen Fermat factoring mentioned on a few sites, but I never saw even a half way decent codiing of it. Apparently, the interest is historical, rather than practical. It is just going to be too slow compared to modern ideas.

Here's how the present algorithm proceeds numerically: Lets factor 39.

Find the integer square root of 39, which is 6. 6 is even, so subtract 1 to get an odd number. There is no sense trying even factors for an odd number.

  39 > 5*5 = 25
( _0: )
We can add 2 to 5 (the larger factor), 7*5 = (5+2)* 5 = 25 + 2*5 = 25 +10 = 35 and
39  >  35 ( skip to _1)

( _0: )
if we were to only add 2 to 7,  9*5 = (7+2)* 5 = 35 + 2*5 = 35+ 10 = 45, and
39 < 45,
so instead add 2 to 7 (the larger factor) and subtract 2 from 5 (the smaller factor).
9*3 = (7+2)* (5-2) = 35+ 2*5 - 2*7 - 4  = 35 - 8 = 27
  Of course 27 will be < 39  because 27 is already < 35

( _0: ) 
So add 2 to 9 (the larger factor).  11* 3 = (9+2)* 3 = 27 + 2*3 = 27 + 6 = 33 and
39 > 33, (go to _1)

( _0: ) 
So add 2 to 11 (the larger factor).  13*3 = (11+2)* 3 = 33 + 2*3 = 27 + 6 = 39 and
39 = 39, (go to _1)

It's possible to interpret this as finding the difference between two squares = 39, but it really doesn't help, and in fact makes the whole thing seem complicated.

All that happens in the loop is that the larger factor goes up by 2 for as long as possible without going over the number.. But when doing that would go over the number, the larger factor goes up 2 AND the smaller factor goes down 2. You keep that up until you hit equality. By adding the difference between the old trial factorization and the new one, you can avoid multiplication.

This is actually using an improvement to Fermat's method made by Gauss, who noted that to find the next perfect square in a series does not require multiplication; it can be accomplished with a simple addition. The difference between any perfect square and the next perfect square is 2 more than the difference to the last perfect square. So 1, 4 ,9, 16, 25... and so on have differences between them of 3, 5, 7, 9...., so keeping a running total of the difference lets you find the next perfect square by adding 11 to 25, as opposed to multiplying 6*6.

The algorithm above works by trying to find x^2 - y^2 = n, where n is the number being factored. But instead of keeping track of x and y, or even x^2 and y^2, it keeps track of an error term that equals x^2 - y^2 - n. If this error term is ever 0, then it has found two factors of n.

Starting with x^2 - n, it subtracts differences to subsequent perfect squares until the error term is <= 0. Then it starts adding differences to subsequent perfect squares until the error term >= 0. It keeps this up until it finds a factor.

As far as a good implementation, here is one written in C that seems to boil the idea down to the essence, taken from http://www.frenchfries.net/paul/src/fermat.cc

Integer factor(Integer n)
{
    Integer r, t, u, v, e;

    t = 0;

    if (n%2 == 0) return 2;
    r = sqrt(n);
    if (issquare(n))
   {
   if (isprime(r)) return r;
   else return factor(r);
   }
    r++;
    u = 2*r + 1; v = 1;                // start with possible candidates
    e = r*r - n;
    while (e != 0)                      // minimize the error term a la Gauss
  {
   while (e<0) {e += u; u+=2;}
   while (e>0) {e -= v; v+=2;}
  }
//    return (u+v-2)/2;              // either one will work
    return (u-v)/2;
}

In this code, e keeps track of x^2 - y^2 - n, while u and v keep track of the difference to the next perfect square of x and y respectively. Once the error term is zero, it returns (u+v-2)/2 because given two numbers, u and v, each of which represents the difference between subsequent perfect squares, then (u+v-2)/2 will give you x+y.  For example, if u=9 and v=11, then (u+v-2)/2 = 9, which is x+y, one of the factors. x is of course 4 (the difference between 4^2 and 5^2 iis 9) and y is 5 (the difference between 5^2 and 6^2 is 11).