Is the function isprime deterministic?

6 visualizaciones (últimos 30 días)
Rafael S.T. Vieira
Rafael S.T. Vieira el 20 de Jun. de 2020
Editada: Rafael S.T. Vieira el 22 de Jun. de 2020
I was playing with primes, and I was happy to verify that
primes(uint32(2^32))
works. However, I wanted to test a huge prime, and found that (2ˆ64)-59 is prime according to SageMath and Wolfram Alpha. However MATLAB function is prime returns false.
isprime(uint64(2^64)-59)
Which one is right? The documentation of the function isprime seems to suggest that it is deterministic, but it would be nice to say it explicitly. Anyone would, please, confirm it?
  1 comentario
Rafael S.T. Vieira
Rafael S.T. Vieira el 20 de Jun. de 2020
Editada: Rafael S.T. Vieira el 20 de Jun. de 2020
Deterministic means that it tests all viable numbers up to x to know if x is prime or not. A non-deterministic algorithm might use some heuristic as the Miller-Rabin primality test.

Iniciar sesión para comentar.

Respuesta aceptada

John D'Errico
John D'Errico el 20 de Jun. de 2020
Editada: John D'Errico el 20 de Jun. de 2020
Your problem is that number is NOT represented in MATLAB as you think it is. MATLAB CANNOT represent a number as a double exactly when the integer is larger than 2^53-1. Double precision is limited in that respect. And yes, I know you THINK you created the number 2^64-59 as a uint64. You did not.
So, YES, I believe it can be shown that isprime is deterministic within the limits of double precision. However, NO, if you throw numbers at it that are too large, then it will fail. The biggest reason why isprime failed for you was that you created it as a double precision number, AND only then converted to uint64. 2^64 is NOT a number you can trust, because it is created as a double.
There is another problem, even more serious. Can you even compute 2^64, and store it in a uint64 variable? NO!
uint64(2)^64
ans =
uint64
18446744073709551615
>> intmax('uint64')
ans =
uint64
18446744073709551615
Should 2^64 be an odd number? Of course not, yet as you see, 2^64 overflows even a uint64 variable.
Instead, use sym, which her will be quite efficient.
isprime(sym(2)^64-59)
ans =
logical
1
See that I created 2 as a symbolic number, only then raising it to a power.
If I did not have the symbolic toolbox, I could have done this - subtly avoiding any overflows, because I recognize that intmax('uint64') is just 2^64-1.
isprime(intmax('uint64') - 58)
ans =
logical
1
Now it works. the symbolic toolbox isprime is MUCH faster, although I expect it is really best called isprobable prime for large integers, since it will be based on a multiple set of calls to a MIller-Rabin test, and possibly other tricks. I recall looking up the basis of the mathematica isprime test, which is similar. A true test for primality that cannot be fooled is more difficult to achieve, and will be MUCH slower running most of the time.
By the way, what number did you test to see if it was prime?
uint64(2^64) - 59
ans =
uint64
18446744073709551556
intmax('uint64') - 58
ans =
uint64
18446744073709551557
You should see clearly why MATLAB thought the former version was not prime. After all, most even numbers are not prime. Almost all of them, in fact.
  9 comentarios
Walter Roberson
Walter Roberson el 21 de Jun. de 2020
John, you talked specifically about representing as a double, but that was pretty much irrelevant.
uint64(2^64) is calculated as double(2)^double(64) resulting in a exact double 0x43f0000000000000 . The uint64() operator is then applied to that, but the exact double is more than the maximum uint64 so it saturates.
You talk about "Double precision is limited in that respect. And yes, I know you THINK you created the number 2^64-59 as a uint64. You did not. " . Most anyone is going to understand you as indicating that the result of the user's uint64(2^64)-59 is a double instead of uint64. The reason why the result is not 2^64-59 has nothing to do with double precision .
Rafael S.T. Vieira
Rafael S.T. Vieira el 22 de Jun. de 2020
Editada: Rafael S.T. Vieira el 22 de Jun. de 2020
Thanks, Walter Roberson and Steven Lord. The function is indeed deterministic, and I was mistaken in my calculations.

Iniciar sesión para comentar.

Más respuestas (0)

Productos


Versión

R2020a

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by