What does Memory allocation mean?

I use Linux Mint 21.2 and my machine is Intel Core i-7 6700 3.4GHZ.

I wrote a prime test in Python, and I checked it with large numbers.

It is like many tests, a variation of little Fermat, so I do some modular exponentiation like powmod(3, n-1, n).

I could testify that n = k * 2^k+1 is prime for k = 6679881.
This is no surprise since it is already proven prime.
My test needed 124 hours for this number with 2.010.852 digits.

Now I wanted to check the Fermat number, F_33, which is n = 2^(2^k)+1 with k = 33.
This number has ~2.500.000 digits.

If I run it, after some minutes, I get the following error:

NU MP: Cannot allocate memory (size=549755818000)
bash: line 1: 19354 Aborted 
(core dumped)

Do I have a chance to run this test?

Asked By: Lereu

||

You’re trying to use 512GB of RAM. Either you optimize your program or you rent a server.

I don’t think swap could help you.

Answered By: Artem S. Tashkinov

It’s pretty much impossible that you would live to see the result, even if you could continue; you can’t, because what this error is telling you is that you ran out of ram.

Why I say you won’t ever see the end:

Let’s compare complexities:

n = k * 2^k+1 is prime for k = 6679881

6,679,881 is roughly 2²³ (in fact, that’s a safe upper bound) so your n≈22²³+ 6679881≈22²³

n = 2^(2^k)+1 with k = 33

Let’s divide that by the rough magnitude of your previous n to get a feeling for how many times later this problem is.

22³³ / 22²³ = 22³³-2²³ ≈ 22³³

In other words, your larger n is so much more complicated to check for primeness that the hour you wait off do irrelevant compared to the exponent of your new problem, it doesn’t even appear.

Answered By: sina bala
Categories: Answers Tags: , ,
Answers are sorted by their score. The answer accepted by the question owner as the best is marked with
at the top-right corner.