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

Lehman factorization algorithm, implementation

Expand Messages
  • WarrenS
    http://dl.dropbox.com/u/3507527/LehmanClean.c is my C code for Lehman factorization algorithm. Perhaps you amazing coders all will be able to improve it
    Message 1 of 3 , Jan 4, 2012
    • 0 Attachment
      http://dl.dropbox.com/u/3507527/LehmanClean.c

      is my C code for Lehman factorization algorithm.
      Perhaps you amazing coders all will be able to improve it further.
      Or find bugs. Or something.

      Ben Buhrow says he is going to put some version of it into YAFU,
      and his tests seemed to indicate it beats SQUFOF for factoring N below about 38 bits,
      although:
      1. I keep changing the code on him
      2. the crossover point depends on your distribution of N, which computer you are on,
      which tuning parameters you pick, and on how much trial factorization
      you want to do (if you know your N are "hard" you can omit
      Lehman's trial factorization step since you know it will never do anything).
    • WarrenS
      I reposted a new code version to same place: http://dl.dropbox.com/u/3507527/LehmanClean.c (But the big comment at start now out of date.) What happened was
      Message 2 of 3 , Jan 4, 2012
      • 0 Attachment
        I reposted a new code version to same place:

        http://dl.dropbox.com/u/3507527/LehmanClean.c

        (But the big comment at start now out of date.)

        What happened was this. I dawned on me that I could OMIT 90% of
        the trial dividing in Lehman, then, if needed, put the missing 90% back at the
        end of the process (but usually not needed).
        This is a huge win.

        As a result, the average Lehman run time for factoring hard 43-bit N, which according to
        my old measurements was 190 usec, now drops to 96 usec.

        There is now a new argument "CutFrac" to the procedure governing this.
        Basically, including trial division now hurts you only about 10% as much as it used
        to.

        Lehman is now superior to my SQUFOF implementation for hard N with 42 bits or less,
        and maybe also for 43 bits.

        For Ben Buhrman's better SQUFOF implementation inside YAFU,
        Lehman is better than SQUFOF for 38 bits or less?
        Not sure, Buhrman 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.
      • 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 3 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.