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

22·227 Posts

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.


Hart's OLF:
danaj is offline   Reply With Quote