(27S,17B,..) FACTOR revisited

[Werner]

In the 'Step-by-Step Solutions' - Technical Applications manual for the HP-27S and HP-19B, on page 52 is an equation to find all prime factors of a number:

Code:

FACTOR:FACT=0xL(E:N)+
IF(MOD(N:2)=0:0xL(E:2):
IF(MOD(N:3)=0:0xL(E:3):
IF(MOD(N:5)=0:0xL(E:5):
IF(MOD(N:7)=0:0xL(E:7):
 L(J:0)+
 Σ(D:11:SQRT(N):2:
  IF(G(J)=1:0:
  IF(L(C:MOD(D-10:30))=1 OR G(C)=3 OR G(C)=7 OR G(C)=9 OR G(C)=13 OR G(C)=19 OR G(C)=21 OR G(C)=27:
  IF(MOD(G(E):D)=0:0xL(J:1)xL(E:D):0)
  :0)
))))))
+G(E)
+L(J:0)xL(N:N/G(E))

This equation is quite slow: it loops over every odd number, comparing it to 8 numbers in each loop.
It is better simplified like this, testing only 2 out of three odd numbers:
(it can be improved still factoring out the 5's, making the equation quite a bit larger)

Code:

FACTR1:FACT=0xL(E:N)x
IF(MOD(N:2)=0:L(E:2):
IF(MOD(N:3)=0:L(E:3):
Σ(D:5:SQRT(N):6:
IF(G(E)<N:0:
IF(MOD(N:D)=0:L(E:D):
IF(MOD(N:D+2)=0:L(E:D+2):0
))))))+
G(E)+0xL(N:N/G(E))

Still, it takes ages for large numbers, even to find a small factor, because it must
always do the full loop 5..SQRT(N).
Since we cannot exit a loop (save with an error, but then execution stops altogether),
I tried to find a way to speed this up.
In the following equation, I have converted the inner loop into two nested loops. The innermost loop doubles in size each iteration, and is skipped if a factor has been found in the meantime.

Code:

FACTR2:FACT=0xL(E:N)x
IF(MOD(N:2)=0:L(E:2):
IF(MOD(N:3)=0:L(E:3):
L(A:L(B:5))+
L(Q:SQRT(N))+
Σ(L:1:-INT(-LN(IP((G(Q)+7)/6))/LN(2)):1:
IF(G(E)<N:0:
Σ(D:G(A):G(B):6:
IF(G(E)<N:0:
IF(MOD(N:D)=0:L(E:D):
IF(MOD(N:D+2)=0:L(E:D+2):0
))))+
L(A:G(B)+6)+
L(B:MIN(G(B)*2+7:G(Q)))
))))+
G(E)+0xL(N:N/G(E))

seems to work ;-) BTW it also works in Plus42, but there the speed is not really an issue ;-)
Let's look at the speed improvements. Bear in mind that the original FACTOR is still slower than FACTR1

Code:

take 9999997 = 7*1428571

        F-1     F-2
      7 18.7     2
1428571 16.2    18.3

take 99999997 = 1297*77101

        F-1     F-2
   1297 65      21.8
  77101  4.2     5.7

take 19*109*1009*10009 = 20915196751

        F-1     F-2
    19  (725)    2.5
   109   164     4.3
  1009    25    19.7
 10009     2.2   3.5

the value between brackets is an estimate

So, to find small factors is many times faster, as the factors grow that difference becomes smaller, and there's a slight overhead for the last factor, or when N is prime to begin with.

Cheers, Werner