mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2006-10-19, 22:17   #1
jocelynl
 
Sep 2002

10616 Posts
Default 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
jocelynl is offline   Reply With Quote
Old 2006-10-19, 23:52   #2
jocelynl
 
Sep 2002

4068 Posts
Default

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
jocelynl is offline   Reply With Quote
Old 2006-10-20, 00:03   #3
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

9,833 Posts
Default

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?
ewmayer is online now   Reply With Quote
Old 2006-10-20, 00:44   #4
jocelynl
 
Sep 2002

2×131 Posts
Default

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

JOSS
jocelynl is offline   Reply With Quote
Old 2006-10-20, 01:51   #5
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

9,833 Posts
Default

Quote:
Originally Posted by jocelynl View Post
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.
ewmayer is online now   Reply With Quote
Old 2006-10-20, 01:59   #6
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

2·541 Posts
Default

Quote:
Originally Posted by jocelynl View Post
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.
Wacky is offline   Reply With Quote
Old 2006-10-20, 03:04   #7
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

9,833 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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?
ewmayer is online now   Reply With Quote
Old 2006-10-20, 16:10   #8
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

246410 Posts
Default

Quote:
Originally Posted by Wacky View Post
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
akruppa is offline   Reply With Quote
Old 2006-10-20, 19:36   #9
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

9,833 Posts
Default

Quote:
Originally Posted by akruppa View Post
Not like an orge or troll at all... hobgoblin, tops.
There you have it - a personal "Eiger sanction" from Alex.
ewmayer is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
(M48) NEW MERSENNE PRIME! LARGEST PRIME NUMBER DISCOVERED! dabaichi News 571 2020-10-26 11:02
Another way to PRP test Mersenne numbers paulunderwood Miscellaneous Math 18 2017-01-26 20:33
How do I test if it is a mersenne prime on GIMPS? spkarra Math 21 2015-01-23 18:13
New test for Mersenne prime allasc Math 33 2011-05-20 22:48
The 40th known Mersenne prime, 220996011-1 is not PRIME! illman-q Miscellaneous Math 33 2004-09-19 05:02

All times are UTC. The time now is 00:23.

Sat Nov 28 00:23:46 UTC 2020 up 78 days, 21:34, 3 users, load averages: 1.44, 1.30, 1.20

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.