Odd GMP Performance

[prime]

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)

[paulunderwood]

Originally Posted by prime

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.

[prime]

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?

[paulunderwood]

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.

[bsquared]

Originally Posted by prime

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.

[prime]

I think you are correct about the python implementation. Sorry for the silly question

[bsquared]

Originally Posted by prime

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.

[paulunderwood]

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).

[prime]

Originally Posted by paulunderwood

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.

[paulunderwood]

Originally Posted by prime

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,

[Viliam Furik]

Originally Posted by prime

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.