Loading ...
Sorry, an error occurred while loading the content.

Lehman

Expand Messages
  • djbroadhurst
    ... 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 =
    Message 1 of 2 , Feb 1 4:48 AM
    • 0 Attachment
      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))))
      David
    • Phil Carmody
      ... 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
      Message 2 of 2 , Feb 1 5:28 AM
      • 0 Attachment
        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.