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

Re: Lehman factorization algorithm, implementation

Expand Messages
  • Ben Buhrow
    ... No problem with the code changes... As I reported to you earlier, here are the results of my tests with pseudo-primes drawn from a random size distribution
    Message 1 of 3 , Jan 4, 2012
    • 0 Attachment
      --- In primenumbers@yahoogroups.com, "WarrenS" <warren.wds@...> wrote:
      >
      >
      > For Ben Buhrow's better SQUFOF implementation inside YAFU,
      > Lehman is better than SQUFOF for 38 bits or less?
      > Not sure, Buhrow will probably report eventually.
      >
      > Sorry I keep changing the code on you, Ben. Members of this yahoogroup may also
      > mess with the code... await their reports.
      >

      No problem with the code changes...

      As I reported to you earlier, here are the results of my tests with pseudo-primes drawn from a random size distribution (100,000 factorizations, all returning a valid proper factor):

      (apologies for any ascii table mangling that may occur - cut n' paste into excel for easier visiblity)

      input size (bits) lehman (best: Tune = 4)
      max min avg squfof with td
      27 9 23.6309 0.3297 0.1622
      28 10 25.6174 0.3766 0.1952
      31 10 27.611 0.4439 0.2475
      32 11 29.6272 0.5386 0.3286
      34 14 31.6133 0.6701 0.4588
      36 17 33.6196 0.8577 0.6684
      38 19 35.6104 1.125 0.9971
      40 19 37.6182 1.5139 1.51
      42 22 39.6124 2.0288 2.3293

      Crossover with inputs of average size ~39 bits.


      And here are the results with pseudo-primes forced to be hard (pseudo-primes with strict size):


      input size (bits) lehman lehman
      max min avg squfof with td no td
      26 25 25.62 0.3623 0.1563 0.1283
      28 27 27.62 0.4261 0.2003 0.1604
      31 29 29.62 0.5148 0.2754 0.2218
      32 31 31.61 0.6392 0.3923 0.3128
      34 33 33.61 0.8168 0.5861 0.4716
      36 35 35.61 1.075 0.8839 0.7214
      38 37 37.61 1.4317 1.3573 1.1124
      40 39 39.61 1.9774 2.0998 1.7396
      42 41 41.61 2.649 3.2967 2.7487

      Crossover with inputs of average size ~41 bits.

      The crossover is higher because one can get away with running Lehman without TD. With TD the crossover is still around 39 bits.


      Great work, and thanks for providing the code for inclusion into YAFU.

      cheers,
      - ben.
    Your message has been successfully submitted and would be delivered to recipients shortly.