mersenneforum.org > Math another mersenne prime test
 Register FAQ Search Today's Posts Mark Forums Read

 2006-10-19, 22:17 #1 jocelynl   Sep 2002 2×131 Posts another mersenne prime test 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. Code:  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
 2006-10-19, 23:52 #2 jocelynl   Sep 2002 2·131 Posts here is a revised one Code:  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 Last fiddled with by jocelynl on 2006-10-19 at 23:58
 2006-10-20, 00:03 #3 ewmayer ∂2ω=0     Sep 2002 República de California 37·313 Posts 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?
 2006-10-20, 00:44 #4 jocelynl   Sep 2002 2×131 Posts Sorry to have wasted your precious time. this was my very last post to this forum and won't ever come back. JOSS
2006-10-20, 01:51   #5
ewmayer
2ω=0

Sep 2002
República de California

37×313 Posts

Quote:
 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.

2006-10-20, 01:59   #6
Wacky

Jun 2003
The Texas Hill Country

44116 Posts

Quote:
 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.

2006-10-20, 03:04   #7
ewmayer
2ω=0

Sep 2002
República de California

101101001111012 Posts

Quote:
 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)2/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?

2006-10-20, 16:10   #8
akruppa

"Nancy"
Aug 2002
Alexandria

2,467 Posts

Quote:
 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

Last fiddled with by akruppa on 2006-10-20 at 19:36 Reason: not hobgoblin either

2006-10-20, 19:36   #9
ewmayer
2ω=0

Sep 2002
República de California

37·313 Posts

Quote:
 Originally Posted by akruppa Not like an orge or troll at all... hobgoblin, tops.
There you have it - a personal "Eiger sanction" from Alex.

 Similar Threads Thread Thread Starter Forum Replies Last Post dabaichi News 571 2020-10-26 11:02 paulunderwood Miscellaneous Math 18 2017-01-26 20:33 spkarra Math 21 2015-01-23 18:13 allasc Math 33 2011-05-20 22:48 illman-q Miscellaneous Math 33 2004-09-19 05:02

All times are UTC. The time now is 12:12.

Tue Jan 19 12:12:08 UTC 2021 up 47 days, 8:23, 0 users, load averages: 1.89, 1.83, 1.81