mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > gophne

Reply
 
Thread Tools
Old 2017-12-28, 15:16   #45
gophne
 
Feb 2017

3×5×11 Posts
Default

Quote:
Originally Posted by jnml View Post
Moar stats

Code:
~/src/tmp/main> go build && time ./main
False negatives:       43
False positives:   338664
Correct results:  4011894
Prime exponents:  4350601 (tests performed)
Last exponent:   74207297

real	0m4.821s
user	0m4.814s
sys	0m0.008s
~/src/tmp/main>
Hi jnml

Can you give me an example of a false negative please that you have found -the target congruant for the algorithm always being 1/2*(n+1)

Last fiddled with by gophne on 2017-12-28 at 15:17 Reason: correcting formula for target congruant 1/2*(n+1)
gophne is offline   Reply With Quote
Old 2017-12-28, 15:22   #46
gophne
 
Feb 2017

A516 Posts
Default

Quote:
Originally Posted by jnml View Post
Moar stats

Code:
~/src/tmp/main> go build && time ./main
False negatives:       43
False positives:   338664
Correct results:  4011894
Prime exponents:  4350601 (tests performed)
Last exponent:   74207297

real	0m4.821s
user	0m4.814s
sys	0m0.008s
~/src/tmp/main>
Hi jnml

How far are you able to test the "divisor" using this algorithm, using your software, and how long does it take? My hunch is that it would be limited due to the exponential relationship between the dividend and the divisor in the algorithm?
gophne is offline   Reply With Quote
Old 2017-12-28, 15:26   #47
jnml
 
Feb 2012
Prague, Czech Republ

132 Posts
Default

Quote:
Originally Posted by gophne View Post
Can you give me an example of a false negative please that you have found -the target congruant for the algorithm always being 1/2*(n+1)
Code:
package main

import (
	"fmt"

	"github.com/cznic/mathutil"
	"github.com/cznic/mathutil/mersenne"
)

func main() {
	var tests, ok, falsePos, falseNeg int
	var negs []uint32
	n := uint32(2)
	for n <= mersenne.Knowns[48] {
		n, _ = mathutil.NextPrime(n)
		_, prime := mersenne.Known[n]
		conj := (mathutil.ModPowUint32(2, n, n+2)-1)%((n+1)/2) == 0
		tests++
		switch {
		case prime == conj:
			ok++
		case prime:
			falseNeg++
			negs = append(negs, n)
		default:
			falsePos++
		}
	}
	fmt.Printf("False negatives: %8d\n", falseNeg)
	fmt.Printf("False positives: %8d\n", falsePos)
	fmt.Printf("Correct results: %8d\n", ok)
	fmt.Printf("Prime exponents: %8d (tests performed)\n", tests)
	fmt.Printf("Last exponent:   %8d\n", n)
	fmt.Println("False negatives:")
	for _, v := range negs {
		fmt.Printf("\tM_%d\n", v)
	}
}
Run

Code:
~/src/tmp/main> go build && time ./main
False negatives:       43
False positives:   338664
Correct results:  4011894
Prime exponents:  4350601 (tests performed)
Last exponent:   74207297
False negatives:
	M_7
	M_13
	M_19
	M_31
	M_61
	M_89
	M_127
	M_607
	M_1279
	M_2203
	M_2281
	M_3217
	M_4253
	M_4423
	M_9689
	M_9941
	M_11213
	M_19937
	M_21701
	M_23209
	M_44497
	M_86243
	M_110503
	M_132049
	M_216091
	M_756839
	M_859433
	M_1257787
	M_1398269
	M_2976221
	M_3021377
	M_6972593
	M_13466917
	M_20996011
	M_24036583
	M_25964951
	M_30402457
	M_32582657
	M_37156667
	M_42643801
	M_43112609
	M_57885161
	M_74207281

real	0m5.063s
user	0m5.059s
sys	0m0.000s
~/src/tmp/main>
jnml is online now   Reply With Quote
Old 2017-12-28, 15:30   #48
jnml
 
Feb 2012
Prague, Czech Republ

2518 Posts
Default

Quote:
Originally Posted by gophne View Post
How far are you able to test the "divisor" using this algorithm, using your software, and how long does it take? My hunch is that it would be limited due to the exponential relationship between the dividend and the divisor in the algorithm?
I don't understand the question, sorry. Perhaps please try to reformulate your method/algorithm in a more universally comprehensible math notation. Chances are I completely misunderstood your description. Anyway, the test for a single exponent using your method as-I-understood-it takes about a microsecond in Go and could be maybe made about twice faster in assembly, I guess.

Last fiddled with by jnml on 2017-12-28 at 15:31 Reason: s/the your/your/
jnml is online now   Reply With Quote
Old 2017-12-28, 15:45   #49
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by gophne View Post
Hi jnml

How far are you able to test the "divisor" using this algorithm, using your software, and how long does it take? My hunch is that it would be limited due to the exponential relationship between the dividend and the divisor in the algorithm?
Want to see real crazy? Check out my blog area for more.

Last fiddled with by science_man_88 on 2017-12-28 at 15:53
science_man_88 is offline   Reply With Quote
Old 2017-12-28, 15:51   #50
gophne
 
Feb 2017

3×5×11 Posts
Default

Quote:
Originally Posted by jnml View Post
FTR: IIUC, the algorithm fails as soon as for M_7.


127 = 1 \pmod 9

but

(7+1)/2 = 4.

Some more evaluation (in Go):

Code:
package main

import (
	"fmt"

	"github.com/cznic/mathutil"
	"github.com/cznic/mathutil/mersenne"
)

func main() {
	fails := 0
	n := uint32(2)
	for n <= mersenne.Knowns[48] {
		n, _ = mathutil.NextPrime(n)
		if (mathutil.ModPowUint32(2, n, (n+2))-1)%((n+1)/2) == 0 {
			if _, ok := mersenne.Known[n]; ok {
				fmt.Printf("M_%d really is prime\n", n)
			} else {
				fails++
			}
		}
	}
	fmt.Printf("False positives: %d\n", fails)
}
Running it:

Code:
~/src/tmp/main> go build && time ./main
M_3 really is prime
M_5 really is prime
M_17 really is prime
M_107 really is prime
M_521 really is prime
False positives: 338664

real	0m4.744s
user	0m4.735s
sys	0m0.004s
~/src/tmp/main>
Hi jnml

Using the algorithm (sagemath), I get positive result for M3, M5 & M17. I could not test beyound M29 (dividend) due to unknown run time).

e.g. M3 (2^7-1)

#1......a=2^7-1..................Divisor under test~127....n-2
#2......b=(2^7-1)-2.............n~125
#3......c=1/2*(b+1).............Target Congruant~63
#4......d=2^b-1...................Dividend~42,535,295,865,117,307,932,921,825,928,971,026,431
#5.......e=d mod a..............Congruant~63
#6.......c==e.......................True~127(divisor) is Prime
gophne is offline   Reply With Quote
Old 2017-12-28, 15:52   #51
jnml
 
Feb 2012
Prague, Czech Republ

A916 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
Check out y blog area for more
Please clarify, I would love to understand what you're saying, but I don't.
jnml is online now   Reply With Quote
Old 2017-12-28, 15:54   #52
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts
Default

Quote:
Originally Posted by jnml View Post
Please clarify, I would love to understand what you're saying, but I don't.
http://www.mersenneforum.org/forumdisplay.php?f=140
science_man_88 is offline   Reply With Quote
Old 2017-12-28, 15:57   #53
gophne
 
Feb 2017

3×5×11 Posts
Default

Hi njml

I get positive results for M7,M13,M19,M31 using sagemath code (see example post #50). I could not test higher because of unknown run time.
gophne is offline   Reply With Quote
Old 2017-12-28, 16:04   #54
jnml
 
Feb 2012
Prague, Czech Republ

132 Posts
Default

Quote:
Originally Posted by gophne View Post
Using the algorithm (sagemath), I get positive result for M3, M5 & M17. I could not test beyound M29 (dividend) due to unknown run time).

e.g. M3 (2^7-1)

#1......a=2^7-1..................Divisor under test~127....n-2
#2......b=(2^7-1)-2.............n~125
#3......c=1/2*(b+1).............Target Congruant~63
#4......d=2^b-1...................Dividend~42,535,295,865,117,307,932,921,825,928,971,026,431
#5.......e=d mod a..............Congruant~63
#6.......c==e.......................True~127(divisor) is Prime
Before digging further we should agree on notation. I used this one:

2^7-1 = M_7 = M4

meaning M_n is 2^n-1 and Mn = nth Mersenne Prime as listed at https://en.wikipedia.org/wiki/Mersen...ersenne_primes.

Using this notation, your method correctly detects eg. M_3, M_5 and M_{17}, but fails to detect for e.g. M_7, M_{13} and M_{19}.

I don't know sagemath, nonetheless, it might be useful to show the sagemath code as an alternative to the proper description in math-notation.
jnml is online now   Reply With Quote
Old 2017-12-28, 16:05   #55
jnml
 
Feb 2012
Prague, Czech Republ

A916 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
Thanks, I do understand now
jnml is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
gpuOwL: an OpenCL program for Mersenne primality testing preda GpuOwl 2686 2021-01-14 21:32
GQQ: a "deterministic" "primality" test in O(ln n)^2 Chair Zhuang Miscellaneous Math 21 2018-03-26 22:33
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!" wildrabbitt Miscellaneous Math 11 2015-03-06 08:17
"New primality proving test from Alex Petrov" ewmayer Math 11 2007-04-23 19:07
P-1 B1/B2 selection with "Test=" vs "Pfactor=" James Heinrich Software 2 2005-03-19 21:58

All times are UTC. The time now is 14:19.

Tue Jan 26 14:19:00 UTC 2021 up 54 days, 10:30, 0 users, load averages: 2.38, 2.65, 2.88

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.