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

Re: {Spam?} [PrimeNumbers] faster than the APR algorithm

Expand Messages
  • Bill Bouris
    Paul I d like to know who made you the spam-master! I believe that if I use the word prime, primality, or even list a few primes that it cannot be consider- ed
    Message 1 of 33 , May 22, 2010
    • 0 Attachment
      Paul

      I'd like to know who made you the spam-master!
      I believe that if I use the word prime, primality, or
      even list a few primes that it cannot be consider-
      ed spam... lol

      Here's how it works... and yes it's a QBasic alg.
      I am computing two T-sequences... a T-3 and T-4
      at the same time.

      First, it computes the necessary term numbers
      for each sequence, simultaneously, and then it
      computes the value of each term.  For example...

      N= 15; the terms are T15, T8, T7, T4, T3, T2, T1 & T0
      for both sequences, the same, and then it computes...

      the T-3 terms values...
      T0= 2, T1= 3, T2= 3^2 -2 = 7 mod 15, T3= 3*7 -3 = 3 mod 15,
      T4= T2^2 -2 = 2 = 15, T5= T2*T3 -3 = 3, etc.

      the T-4 term values are computed the same, except...
      T0= 2, T1= 4, etc.; I didn't invent it, but it's faster than
      using the "extremely" bulky APR algorithm.

      There's nothing wrong with a '70's program, it's simple
      to read, and very, very easily translated into another
      language... any language... I don't care who reads it;
      my 50-line program is a ton easier to implement than
      the several 100 lines of the APR algorithm and is far
      less contrived and/or convoluted.  The bottom line is
      that if T15 for both the T-3 and T-4 sequences equal 3 & 4,
      respectively, then the number is prime; 231 is the only
      composite that gives a mis-read; the two curves cross
      there.

      If you've ever looked at the APR algorithm, you'd know
      that it is certainly twisted and absolutely ridiculous to
      calculate; most mathematicians would insist that an
      algorithm be elegant is some fashion as well as be the
      fastest; the APR algorithm isn't elegant.  I spoke to
      Carl Pomerance, once, and he wasn't very happy with
      his own algorithm... "it doesn't tell me the factors"...
      his words exactly!

      Bill


      ----- Original Message ----
      From: Paul Leyland <paul@...>
      To: leavemsg1 <leavemsg1@...>
      Cc: primenumbers@yahoogroups.com
      Sent: Fri, May 21, 2010 10:34:52 AM
      Subject: Re: {Spam?} [PrimeNumbers] faster than the APR algorithm

      On Fri, 2010-05-21 at 15:28 +0000, leavemsg1 wrote:

      > I believe that this algorithm proves primality faster than the
      > APR algorithm, not compositeness, but primality; if both this
      > T-sequence algorithm and the APR algorithm were written in the
      > same language and had the same FFT's and CPU available, then I
      > believe the T-sequence would beat it; assuming that variables
      > were computed on the fly... i.e. no stored values allowed.

      Bunch of code omitted.

      > Bill, hoping that someone would comment on it other than DjBrst

      Wish granted.

      Paul, hoping that you would comment on how it works instead of expecting
      us to decipher some turgid code which looks as if it was written in the
      early 1970s.  Some kind of BASIC if my age-addled memory doesn't
      deceive me.
    • mikeoakes2
      ... You did very much what I did. I nearly fell off the chair when I averaged everything out and saw 0.57... :-) ... Not very. Would you buy an appeal to
      Message 33 of 33 , May 27, 2010
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
        >
        > I tried 1/n^c:
        >
        > v=[1237.1, 328.7, 105.4, 28.01, 6.22 , 1.510, 0.439, 0.0939];
        > print(vector(8,k,-log(v[k]/10^6)/(k+4)/log(10)));
        >
        > [0.5815, 0.5805, 0.5682, 0.5691, 0.5785, 0.5821, 0.5780, 0.5856]
        >
        > and then A/n^c, using the first datum to remove A:
        >
        > print(vector(7,k,-log(v[k+1]/v[1])/k/log(10)));
        >
        > [0.5756, 0.5348, 0.5484, 0.5747, 0.5827, 0.5750, 0.5885]
        >
        > In both cases c =~ Euler looks rather convincing,
        > given the statistics. Well spotted, Sir!

        You did very much what I did.
        I nearly fell off the chair when I averaged everything out and saw 0.57... :-)

        > How strongly are you committed to A = 1, for the average,
        > given the variability of the overall factor with a?

        Not very.
        Would you buy an appeal to Occam's razor, mon vieux?

        Mike
      Your message has been successfully submitted and would be delivered to recipients shortly.