23965Re: Lehman factorization algorithm, theoretical comparison with SQUFOF
- Jan 1, 2012It turns out William B. Hart in a preprint
implemented his own heuristic factoring algorithm
which he calls "one line factoring algorithm" because it is very simple.
Except actually it isn't that simple when you try to optimize its performance.
It heuristically runs in O(N^(1/3)) time, except it can and will fail on some N.
Hart then points out that a good way to implement Lehman's algorithm involving
"turning the loops inside out" in the part of the search space where Lehman's inner loop
only does 1 iteration... basically coincides with his "one line" algorithm in that part of the search space.
If this is done, Hart finds that Lehman runs in essentially exactly
the same average time as his "one line" method, but is better in the worst case since Lehman always succeeds while the "one line" method can fail.
And then he finds that Lehman is competitive with Pari's built in factorer for N<=42 bits long, and is superior to Pari from 26 to 41 bits. Above 41 Pari (apparently using SQUFOF)
is better. Below 26, Pari is usually better, but never by as much as a factor of 2,
and it is probably just since Pari implemented trial division better than Hart did.
this programming work by Hart totally confirms my theoretical analysis last post
where I predicted the Lehman/SQUFOF crossover would be at 42 bits; he finds
it is 41 bits.
Hart also finds a better way to code Lehman that reduces loop-boundary overhead.
- << Previous post in topic