another mersenne prime test

[jocelynl]

Here is another Mersenne prime test.
I don't know about the speed I only tested it in UBasic upto n=4423 it works fine.

  15   M=2
   20   M=nxtprm(M)
   30   N=2^M-1
   40   B=3
   50   C=2
   60   B=modpow(B,N\C,N)
   70   C+=1
   74   if C<4 then 60
   75   if B=1 then print M;"is prime":goto 20
   80   goto 20

Joss

[jocelynl]

here is a revised one

   15   M=2
   20   M=nxtprm(M)
   30   N=2^M-1
   40   N2=sft(N,-1)
   50   B=modpow(3,N2,N)
   54   N3=sft(N-N2,-1)
   55   B=modpow(B,N3,N)
   75   if B=1 then print "2^";M;"-1 is prime":goto 20
   80   goto 20

Can anyone try this in C++ to see if there's any speed difference at higher m values I really don't see any below 4000.

Joss

[ewmayer]

It would help if you posted in some kind of pseudocode that doesn't require knowledge of specific UBasic (or whatever) syntax. Anyway, had you bothered to actually *analyze* your algorithm, you'd see that it amounts to taking a Mersenne number N = M(p), then raising the seed B=3 to some "magic" obfuscated power which (using that \ is UBasic for "integer divide") equals

pow = floor(N/2) * floor(N/3).

E.g. for M(p) with p=3 this works out to floor(7/2) * floor(7/3) = 3*2 = 6. For general odd p, it simply amounts to an obfuscated way or writing N-1. Thus, this is nothing more than a base-3 Fermat pseudoprime test.

May I politely suggest you actually read up on your basic number theory?

[jocelynl]

Sorry to have wasted your precious time.
this was my very last post to this forum and won't ever come back.

JOSS

[ewmayer]

Originally Posted by jocelynl

Sorry to have wasted your precious time.

If this were a first-time post along these lines I would've been more patient, but in your case it's at least the 4th or 5th such thing. At some point you've gotta expect that other people will get tired at you basically asking them to do your homework for you. And yes, some of us *do* value our time, and get annoyed at having to to spend it debunking one bogus New! Improved!!! I-Don't-Know-Why-It-Works-But-It-Seems-Really-Fast-For-Exponents-Below-5000!!! thread after another.

Given the time you've spent around here and the fact that you clearly know enough about UBasic to even code such a test, there's simply no good excuse not to do a little bit of digging and ask yourself "hmm - I wonder why it works?" before starting a thread claiming to have found a new Mersenne primality test.

[Wacky]

Originally Posted by jocelynl

Sorry to have wasted your precious time.
this was my very last post to this forum and won't ever come back.

JOSS

Joss,

Your failure to return will be of no loss to most of us.

[SOAPBOX]
As for "wasting your precious time", your should take Dr. Mayer's suggestions and, in any forum,:

(1) unless you are discussing the efficiency of code for an algorithm that has been established to be efficient, please avoid implementation details. Discuss proposed algorithms in "pseudo-code" that is implementation independent and easier for everyone to understand. Most of us do not stay current on thirty or forty, or more, implentation languages that are still around. (I can still run IPL-V. But I DARE you to understand those old programs :) )

(2) analyze the "complexity" of your proposed algorithm and be prepared to compare it to other established algorithms.

In these circles, you need to make AN ATTEMPT to justify why your proposal has merit. If you think that it does, but cannot make the justification, it is quite permissible to show that you have made an effort to do so, isolate the "sticking points", and ask for assistance in resolving them.
[/SOAPBOX]

You might be surprised, but even "the worst ogre" here is actually helpful when he is approached appropriately. Lesser trolls are even more approachable.

(For the record, ewmayer was polite in his response. Beware the ogre!)

Richard

PS: I am not "the worst ogre" mentioned above.

[ewmayer]

Originally Posted by ewmayer

it amounts to taking a Mersenne number N = M(p), then raising the seed B=3 to some "magic" obfuscated power which (using that \ is UBasic for "integer divide") equals

pow = floor(N/2) * floor(N/3).

E.g. for M(p) with p=3 this works out to floor(7/2) * floor(7/3) = 3*2 = 6. For general odd p, it simply amounts to an obfuscated way or writing N-1. Thus, this is nothing more than a base-3 Fermat pseudoprime test.

Actually, I was too hasty -- it's even worse than I initially thought. The power actually being computed here is (N-1)²/6, which (except for N=7, where this equals N-1) is quadratic in N. E.g. for N=31, we're raising the initial seed tp the 150th power, rather than the 30th power required by the Fermat pseudoprime test.

I'll leave it as a homework exercise for the interested (and non-indolent) reader to answer the following:

a) Just how much slower is this (in an asymptotic large-N sense) than the Fermat PRP test? (Hint: it's slower, but not quadratically slower).

b) Since this computes a power which is actually a multiple of N-1, is this in fact an even weaker pseudoprime test than the Fermat pseudoprime test?

[akruppa]

Originally Posted by Wacky

You might be surprised, but even "the worst ogre" here is actually helpful when he is approached appropriately. Lesser trolls are even more approachable.

If you're talking about the one I think you're talking about, I have to add here that I was really amazed by the almost stoic calm he has shown in a very recent crank/nutjob thread.

Not like an orge or troll at all... half-orc, tops.

Alex

[ewmayer]

Originally Posted by akruppa

Not like an orge or troll at all... hobgoblin, tops.

There you have it - a personal "Eiger sanction" from Alex.