Azzera filtri
Azzera filtri

How can I differentiate between powermod(a,b,c) and mod(a^b,c)

5 visualizzazioni (ultimi 30 giorni)
Please I need a help.
I'm trying to calculate the modular exponent of 104^45 mod 181 using matlab. I tried it using mod(104^45,181) and the answer was 16 and I used powermod(104,45,181) and the answer was 19. I need the answer of 19 but I cannot understand what is the difference of using mod(104^45,181) or powermod(104,45,181) and why they gave me different results.

Risposta accettata

Walter Roberson
Walter Roberson il 17 Set 2020
104^45 exceeds 2^53, which is the largest number for which double precision is able to distinguish between adjacent integers. 2^53+1 and 2^53+2 are stored the same way in double precision.
So taking mod() of such a large number is going to be inaccurate, because double precision is not storing the actual number, just the closest approximation it can get.
powermod computes in a way that avoids the overflow problem.

Più risposte (1)

Stephen23
Stephen23 il 17 Set 2020
Modificato: Stephen23 il 17 Set 2020
>> 104^45
ans =
5.8412e+90
is well above flintmax, so it is very unlikely to exactly represent the integer that you think it does. Basically you are operating outside the range of values for which binary floating point numbers can return exact results.
Out of curiosity, lets have a look at its exact value:
>> sprintf('%.0f',val)
ans =
5841175681461396100000000000000000000000000000000000000000000000000000000000000000000000000
>> num2strexact(val)
ans =
5.841175681461396139743188451945227599878334793277611533585380091992728127111004870833864704e90
Hmm... according to some online tools I tried just now, the actual value would be:
5841175681461396078978021080682091600471472844189578473133182011317053645880726656567476224
You can see that the floating point number is correct to around 16 significant figures, just as we would expect. But any digits after that are just noise and have no sgnificant meaning.

Community Treasure Hunt

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

Start Hunting!

Translated by