mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2021-03-08, 15:04   #1
prime
 
Mar 2021

22 Posts
Default Odd GMP Performance

This C++ program https://pastebin.com/y2u9AYRW takes over 7 mins (before I terminated) to run the mpz_probab_prime_p function.

This python implementation(using pypy) can do this in 20 seconds

for i in tqdm(a):
if all(i % j for j in range(2, ((2**i)-1))):
print(i)

Is there something that I am missing? Also these are very large numbers ~(10^10000000)

Last fiddled with by prime on 2021-03-08 at 15:42 Reason: added info
prime is offline   Reply With Quote
Old 2021-03-08, 16:12   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×11×167 Posts
Default

Quote:
Originally Posted by prime View Post
This C++ program https://pastebin.com/y2u9AYRW takes over 7 mins (before I terminated) to run the mpz_probab_prime_p function.

This python implementation(using pypy) can do this in 20 seconds

for i in tqdm(a):
if all(i % j for j in range(2, ((2**i)-1))):
print(i)

Is there something that I am missing? Also these are very large numbers ~(10^10000000)
These numbers are too large for prime searching with GMP. To do one PRP test takes ~30M mults of 10M digits by 10M digits (and mod reductions) without a very fast FFT as is used by GWNUM library which is part of George Woltman's p95 source code. If you want to crunch such big numbers use GWNUM. Look at the files gwnum.h (and giants.h) for more info. We are only too pleased to answer any queries you might have.

Last fiddled with by paulunderwood on 2021-03-08 at 16:13
paulunderwood is offline   Reply With Quote
Old 2021-03-08, 16:25   #3
prime
 
Mar 2021

416 Posts
Default

I have a few questions. Why does the python implementation seem to work at a reasonable(I think) speed? Also does GWNUM have the same license agreement as Prime95, where if you find a Mersenne prime you share the winnings?(this is not of much concern to me, just wondering) Also do gpus excel at these types of tasks?

Last fiddled with by prime on 2021-03-08 at 16:35 Reason: spelling
prime is offline   Reply With Quote
Old 2021-03-08, 16:41   #4
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×11×167 Posts
Default

I don't know Python. I can't make heads nor tails of it. Someone else will chip in.

Yes GWNUM does have that license agreement about world record primes. If you don't want to get your hands dirty then OpenPFGW may be an option for you. It makes life easy, compared to writing your own GWNUM code

GPUs running gpuOwl for Mersenne is very fast, particularly on AMD Radeon V II. For example that card takes a day to crunch a current wavefront test (107M bits long) whereas Prime95 on a fast CPU would take a week or two.

Last fiddled with by paulunderwood on 2021-03-08 at 17:04
paulunderwood is offline   Reply With Quote
Old 2021-03-08, 17:16   #5
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×32×191 Posts
Default

Quote:
Originally Posted by prime View Post
This C++ program https://pastebin.com/y2u9AYRW takes over 7 mins (before I terminated) to run the mpz_probab_prime_p function.

This python implementation(using pypy) can do this in 20 seconds

for i in tqdm(a):
if all(i % j for j in range(2, ((2**i)-1))):
print(i)

Is there something that I am missing? Also these are very large numbers ~(10^10000000)
Is there something we are missing? In the all statement looks like you are asking it to trial divide i by every value between 2 and 2^i -1, which is not only clearly computationally impossible for anything but trivially small i, but also is always false for i > 1. So you are comparing apples to battleships.

Last fiddled with by bsquared on 2021-03-08 at 17:19
bsquared is offline   Reply With Quote
Old 2021-03-08, 17:27   #6
prime
 
Mar 2021

22 Posts
Default

I think you are correct about the python implementation. Sorry for the silly question
prime is offline   Reply With Quote
Old 2021-03-08, 17:40   #7
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

343810 Posts
Default

Quote:
Originally Posted by prime View Post
I think you are correct about the python implementation. Sorry for the silly question
No worries. The GMP function mpz_probab_prime_p performs the Baillie–PSW primality test followed by some Miller-Rabin tests. There are probably python implementations of those things around the web, if you would like to compare the speed of mpz_probab_prime_p with something equivalent in python. I would not recommend jumping to 10^10000000 right away! Start with smaller numbers and work your way up to understand how things scale.
bsquared is offline   Reply With Quote
Old 2021-03-08, 17:51   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

E5A16 Posts
Default

For Python: https://pypi.org/project/labmath/ for example has various tests including bpsw and fermat_prp.

Once you have tried out 10k digit numbers be amazed by the speed of OpenPFGW (which like LLR and Prime95 is based in GWNUM).

Last fiddled with by paulunderwood on 2021-03-08 at 17:55
paulunderwood is offline   Reply With Quote
Old 2021-03-08, 17:56   #9
prime
 
Mar 2021

22 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
For Python: https://pypi.org/project/labmath/ for example has various tests including bpsw

Once you have tried out 10k digit numbers be amazed by the speed of OpenPFGW (which like LLR and Prime95 is based in GWNUM).
How long does a number that is ~2^100000000 (near the world record) usually take on a fast cpu with prime95? Just curious on the timescale. Also I am not really interested in python.

Last fiddled with by prime on 2021-03-08 at 17:57
prime is offline   Reply With Quote
Old 2021-03-08, 18:01   #10
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·11·167 Posts
Default

Quote:
Originally Posted by prime View Post
How long does a number that is ~2^100000000 (near the world record) usually take on a fast cpu with prime95? Just curious on the timescale. Also I am not really interested in python.
A week or two for Mersenne. Other forms take longer because they are not so simple in form and there is a special "transform" for Mersenne numbers,
paulunderwood is offline   Reply With Quote
Old 2021-03-08, 22:13   #11
Viliam Furik
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

457 Posts
Default

Quote:
Originally Posted by prime View Post
How long does a number that is ~2^100000000 (near the world record) usually take on a fast cpu with prime95? Just curious on the timescale. Also I am not really interested in python.
If you use one of the AMD Ryzen processors, e.g. Ryzen 9 3900X (12 cores, 64 MiB of L3 cache -> high-speed on-die memory), it gets to a matter of about 3 days.

If you would use some similar CPU, with more cores, the time needed would obviously get even shorter.
Viliam Furik is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
32-80 core performance aurashift Hardware 91 2015-04-24 05:23
64-bit performance of v25.6 James Heinrich PrimeNet 11 2008-04-24 01:42
64 bit performance? zacariaz Hardware 1 2007-05-10 13:08
LLR performance on k and n robert44444uk 15k Search 1 2006-02-09 01:43
Performance battlemaxx Prime Sierpinski Project 4 2005-06-29 20:32

All times are UTC. The time now is 06:51.

Thu May 13 06:51:04 UTC 2021 up 35 days, 1:31, 1 user, load averages: 1.84, 1.73, 1.69

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.