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

Re: LLRP4 Version 3.3 now available !

Expand Messages
  • pminovic
    Jean, Thank you for the new version in almost no time! I tried to test Kynea numbers. It s working but it s slower than pfgw. Two examples are given below. Now
    Message 1 of 6 , Dec 1, 2004
    • 0 Attachment
      Jean,
      Thank you for the new version in almost no time!

      I tried to test Kynea numbers. It's working but it's slower
      than pfgw. Two examples are given below. Now I'm testing k*2^n+1.

      (2^110614+1)*2^110616-1 = (2^110615+1)^2 - 2 is prime! Time :
      929.038 sec. [LLR 3.3, 2.4 GHz P4]

      (2^110615+1)^2-2 is 3-PRP! (767.4431s+0.0228s) [pfgw, 2.2 GHz P4]

      --------------------
      (2^240067+1)*2^240069-1 = (2^240068+1)^2 - 2 is not prime. Res64:
      A06A1D3A94955672 Time : 4842.764 sec. [LLR-3.3, 2.4GHz P4]

      (2^240065+1)^2-2 is composite: [1FA6F8AA16DC1765] (3412.6447s+0.0320s)
      [pfgw, 2.4GHz P4]

      Regards,
      Predrag
    • Paul Underwood
      ... The way to speed up searching Carol/Kynea numbers is through modular reduction. When reducing over 2^n+-2^k-1 ( k
      Message 2 of 6 , Dec 1, 2004
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, "pminovic" <pminovic@y...> wrote:
        >
        > Jean,
        > Thank you for the new version in almost no time!
        >
        > I tried to test Kynea numbers. It's working but it's slower
        > than pfgw. Two examples are given below. Now I'm testing k*2^n+1.
        >
        > (2^110614+1)*2^110616-1 = (2^110615+1)^2 - 2 is prime! Time :
        > 929.038 sec. [LLR 3.3, 2.4 GHz P4]
        >
        > (2^110615+1)^2-2 is 3-PRP! (767.4431s+0.0228s) [pfgw, 2.2 GHz P4]
        >
        > --------------------
        > (2^240067+1)*2^240069-1 = (2^240068+1)^2 - 2 is not prime. Res64:
        > A06A1D3A94955672 Time : 4842.764 sec. [LLR-3.3, 2.4GHz P4]
        >
        > (2^240065+1)^2-2 is composite: [1FA6F8AA16DC1765] (3412.6447s+0.0320s)
        > [pfgw, 2.4GHz P4]
        >
        The way to speed up searching Carol/Kynea numbers is through modular
        reduction. When reducing over 2^n+-2^k-1 ( k<70% of n ingeneral ) we
        can use additions and shifts only; There is no need for general
        modular reduction. Maybe we need a new library from George Woltman...

        Paul
      • Jean PennĂ©
        Thank you for your tests ! I am not surprised if LLPP4 deterministic test is slower than pfgw PRP one, because the Computing U0 loop is more time consuming
        Message 3 of 6 , Dec 1, 2004
        • 0 Attachment
          Thank you for your tests !

          I am not surprised if LLPP4 deterministic test is slower than pfgw PRP
          one, because the "Computing U0" loop is more time consuming than the
          LL loop... Is the deterministic pfgw test also faster ?

          Second question : with composite candidates, you found different
          residues with pfgw and with LLRP4, it may be normal, or it may be
          still an LLR bug...

          Regards,

          Jean


          --- In primenumbers@yahoogroups.com, "pminovic" <pminovic@y...> wrote:
          >
          > Jean,
          > Thank you for the new version in almost no time!
          >
          > I tried to test Kynea numbers. It's working but it's slower
          > than pfgw. Two examples are given below. Now I'm testing k*2^n+1.
          >
          > (2^110614+1)*2^110616-1 = (2^110615+1)^2 - 2 is prime! Time :
          > 929.038 sec. [LLR 3.3, 2.4 GHz P4]
          >
          > (2^110615+1)^2-2 is 3-PRP! (767.4431s+0.0228s) [pfgw, 2.2 GHz P4]
          >
          > --------------------
          > (2^240067+1)*2^240069-1 = (2^240068+1)^2 - 2 is not prime. Res64:
          > A06A1D3A94955672 Time : 4842.764 sec. [LLR-3.3, 2.4GHz P4]
          >
          > (2^240065+1)^2-2 is composite: [1FA6F8AA16DC1765] (3412.6447s+0.0320s)
          > [pfgw, 2.4GHz P4]
          >
          > Regards,
          > Predrag
        • pminovic
          ... PRP ... This is true, it takes about 50 minutes to compute U0, I ll append the lresults.txt file tomorrow. ... No! To prove primality of a PRP using pfgw
          Message 4 of 6 , Dec 1, 2004
          • 0 Attachment
            > I am not surprised if LLPP4 deterministic test is slower than pfgw
            PRP
            > one, because the "Computing U0" loop is more time consuming than the
            > LL loop...

            This is true, it takes about 50 minutes to compute U0, I'll
            append the lresults.txt file tomorrow.

            > Is the deterministic pfgw test also faster ?

            No! To prove primality of a PRP using "pfgw -tp" is very slow.
            Again I don't have exact timings handy but I think at least an
            hour in comparison to less than 18 minutes to find that
            (2^110615+1)^2-2 is 3-PRP.

            > Second question : with composite candidates, you found different
            > residues with pfgw and with LLRP4, it may be normal, or it may be
            > still an LLR bug...

            The input is different too, n=240068 and n=240065. The survival
            rate of Kynea (and Carol) is high and there are so many
            candidates to test that I simply cannot afford to process the
            same number twice :-)) Will try the same number later using
            smaller exponents.

            BTW, testing k*2^n+1, n~180,000, both the new LLR and PRP3
            could process one number in almost exactly the same time, about
            66 sec on 2.4GHz P-4.

            Regards,
            Predrag
          • Ken Davis
            The following is posted on behalf of Jean Penne who sent his reply to primenumbers-owner instead of primenumbers by mistake. Cheers Ken ... pfgw ... the
            Message 5 of 6 , Dec 1, 2004
            • 0 Attachment
              The following is posted on behalf of "Jean Penne" who sent his reply
              to "primenumbers-owner" instead of "primenumbers" by mistake.
              Cheers
              Ken
              --- In primenumbers@yahoogroups.com, "pminovic" <pminovic@y...>
              wrote:
              >
              > > I am not surprised if LLPP4 deterministic test is slower than
              pfgw
              > PRP
              > > one, because the "Computing U0" loop is more time consuming than
              the
              > > LL loop...
              >
              > This is true, it takes about 50 minutes to compute U0, I'll
              > append the lresults.txt file tomorrow.
              >

              Thanks by advance !

              > > Is the deterministic pfgw test also faster ?
              >
              > No! To prove primality of a PRP using "pfgw -tp" is very slow.
              > Again I don't have exact timings handy but I think at least an
              > hour in comparison to less than 18 minutes to find that
              > (2^110615+1)^2-2 is 3-PRP.
              >

              I am also not surprised : Deterministic pfgw pays for its more
              general algorithms than those of LLR.

              > > Second question : with composite candidates, you found different
              > > residues with pfgw and with LLRP4, it may be normal, or it may be
              > > still an LLR bug...
              >
              > The input is different too, n=240068 and n=240065. The survival
              > rate of Kynea (and Carol) is high and there are so many
              > candidates to test that I simply cannot afford to process the
              > same number twice :-)) Will try the same number later using
              > smaller exponents.
              >

              My fault ! I did'nt see the inputs were different...

              > BTW, testing k*2^n+1, n~180,000, both the new LLR and PRP3
              > could process one number in almost exactly the same time, about
              > 66 sec on 2.4GHz P-4.
              >

              Again, I am not surprised, PRP3 and LLRP4 use exactly the same code
              to do squarings, the only difference is that, for Proth deterministic
              tests, LLR computes the base "a" for each number, although PRP3 sets
              always "a" = 3, but all that is done outside the loops.

              Regards,
              Jean
            Your message has been successfully submitted and would be delivered to recipients shortly.