View Single Post
Old 2017-02-27, 18:04   #4
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

22·227 Posts
Default

While it isn't so useful for very large inputs, there is still a use in implementations for fast methods on small inputs. E.g. yafu uses a heavily tuned Fermat-Lehman for numbers under ~42 bits and SQUFOF for larger 64-bit inputs (this used to be true, I haven't checked in a few years). I use Hart's OLF to factor composites of 22-28 bits. Micro-optimizations make a big difference at this level.

Like your method, Hart's OLF uses an integer square root and a perfect square test for each loop. Note that the latter is much faster than a square root in most cases and the performance of your perfect square detection method will make a noticeable difference for algorithms like SQUFOF.

Fermat-Lehman: http://www.ams.org/journals/mcom/197...63-2/home.html

Hart's OLF: http://wstein.org/home/wstein/www/ho...linefactor.pdf
danaj is offline   Reply With Quote