Browse Groups

• ... It s a tough call. Lehman s method isn t really a single method, it s a combination of what is effectively an O(f(p)) method and a O(g(N)) method. In order
Feb 1, 2002 1 of 2
View Source
On Fri, 01 February 2002, "djbroadhurst" wrote:
> Phil:
> > if you throw a few trivial improvements into Fermat,
> > it's not too shabby on the just-over-word-size range
> So is there a range where Lehman's method (CP 5.1.2)
> is best? This is trial div up to n^(1/3)
> and then Fermat with multipliers up to n^(1/3).
> #ops = O(n^(1/3)*(log(log(n))))

It's a tough call.
Lehman's method isn't really a single method, it's a combination of what is effectively an O(f(p)) method and a O(g(N)) method.
In order to be a fair comparison, you'd have to compare it with all such pairs of algorithms.
I've not analysed the multiplier effectiveness in terms of decreased search-space, but to be honest, my gut-feel is still to prefer the Legendre symbol (effectively constant-factor, often around 10-20:1) boost.
If we are putting or finding limits to the size of N, which we are, then constant factors are hugely important.

It would be nice to implement _all_ algorithms, using a common virtual machine (JavaScript or Java both would work), and to count the operations for each one over a wide sample-set.

I have already done this for something which is a bit like SQUFOF which was quite fun.

Actually, does anyone know the name of that algorithm? It is just like SQUFOF, but without the clever (Shank's?) hack that means you don't need to calculate with full-size numbers as you go, and stick entirely with half-sized numbers.

It seems like it could be a pregenitor to SQUFOF, but I have no idea who may have been behind it. Maybe it was Shank's version 0.9 before he realised the hack?

Phil

Don't be fooled, CRC Press are _not_ the good guys.
They've taken Wolfram's money - _don't_ give them yours.
http://mathworld.wolfram.com/erics_commentary.html

Find the best deals on the web at AltaVista Shopping!
http://www.shopping.altavista.com
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.