# How to get mod of large numbers?

14 visualizaciones (últimos 30 días)
Mohsin Shah el 1 de Mayo de 2017
Comentada: Mohsin Shah el 2 de Mayo de 2017
I have this calculation: c=(5652)^42.(23)^77mod5929, when i use scientific calculator I get c=4624 an when I do this by MATLAB mod command it gives 0...why?
##### 0 comentariosMostrar -2 comentarios más antiguosOcultar -2 comentarios más antiguos

Iniciar sesión para comentar.

Steven Lord el 1 de Mayo de 2017
If you compute (5652^42)*(23^77) to use the naive approach for computing this quantity, the resulting number is much greater than flintmax. If we look at the spacing between that number and the next largest number, we see that the spacing is (much) greater than 5929.
>> x = (5652^42)*(23^77)
x =
2.78954779454946e+262
>> eps(x)
ans =
3.49595995098571e+246
>> (x + 5929) == x
ans =
logical
1
As Sean stated in this answer from a while ago, you could use Symbolic Math Toolbox. Or you could use one of the algorithms described in this Wikipedia page to perform these computations with numbers no greater than 5652^2.
##### 1 comentarioMostrar -1 comentarios más antiguosOcultar -1 comentarios más antiguos
Mohsin Shah el 2 de Mayo de 2017
Thank you so much

Iniciar sesión para comentar.

### Más respuestas (1)

John D'Errico el 1 de Mayo de 2017
Editada: John D'Errico el 1 de Mayo de 2017
Because MATLAB works in double precision.
5652^42 * 23^77
ans =
2.78954779454946e+262
This is a number with 263 decimal digits, so far beyond the precision available to a double. A double can represent no integer exactly that is larger than 2^53. And 2^53 is just not very large in this context.
You can either use a tool (like my VPI toolbox or the symbolic toolbox)
vpi(5652)^42 * vpi(23)^77
ans =
27895477945494593633174830929266408591443695665432884022901567138564930227891230414671987539540619495363075575420684353178819655415398533495806892010942366092828416772086484568033389306894581602342651519614654523921262520198453838046500944165540916333162855923712
mod(ans,5929)
ans =
4624
Or, you can recognize that you can use mod in a loop. Thus, this law applies:
mod(a*b,n) = mod(mod(a,n)*mod(b,n),n)
So you can compute the mod of a power (or a product of powers) in a simple loop, while never exceeding the limits imposed by double precision.
##### 1 comentarioMostrar -1 comentarios más antiguosOcultar -1 comentarios más antiguos
Mohsin Shah el 2 de Mayo de 2017
Thank you so much

Iniciar sesión para comentar.

### Categorías

Más información sobre Number Theory en Help Center y File Exchange.

### Community Treasure Hunt

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

Start Hunting!

Translated by