mod gives incorrect result

Hi Mr/Miss,

I am Eda Nur Dagasan. I am a master's student. I am writing from Turkey. I use mod(x,y) function for my Matlab project. But I have a problem with mod(x,y) function. When I use mod(146^23,187) process, a result of this process is wrong. When I do this (mod(146^23,187) ) process with a calculator, the result is 5, but ı use mod(x,y) function the result is 141 and this result is wrong. I attached screenshots about this problem. Could you help me?

Answer 1

[James Tursa]

See this thread:

https://www.mathworks.com/matlabcentral/answers/338182-how-to-get-mod-of-large-numbers

[Guillaume]

"The result does not change."

Then you haven't understood at all the answer provided in that link.

[Eda Nur Dagasan]

Sorry. I have commented on the wrong place. I used your method and it works. Thanks for your attention.

Answer 2

[Guillaume]

See my comment to Kalyan's answer for why your naive attempt doesn't work, and learn about floating point numbers so that you can understand that attempting to compute 146^23 accurately is absurd.

Despite your statement, the link provided by James does resolve your problem. A simple implementation of modular exponentiation produces the correct result:

b = 146; e = 23;  m = 187;

%basic implementation of modular exponentiation:
c = 1;
for ee = 1:e
    c = mod(b*c, m);
end

does result in

>> c
c =
     5

Answer 3

[KALYAN ACHARJYA]

May be the issue with Largest number in Matlab, Experts can elaborate more in this case

>> 146^23
ans =
   6.0272e+49

If you do with smaller number, you get the correct results in both cases (Matlab and Calculator)

Matlab:

>> mod(10,3)
ans =
     1

Calculator:

Again:

Calculator:

mod(1000, 7) = 6.0

Matlab:

>> mod(1000, 7)
ans =
     6

[Guillaume]

@Kalyan, you've got the right idea but looking at the wrong limit. intmax is completely irrelevant here, it only applies to variables of integer types (the way you use it, int32 only).

The relevant limit is flintmax. The largest consecutive integer that can be represented as a double.

@Eda, due to the way floating point numbers are stored on a computer, it's not possible to store accurately every integers above flintmax (~9e15). The gap between integers that can be stored gets bigger and bigger as the magnitude grows. slightly above 9e15, odd integers gets rounded to the nearest even integer. For numbers around 146^23, the gap between numbers is about 1e34.

So you get the mod of the nearest representable integer to 146^23. This is not particular to matlab, you'd get the same problem in any language which uses floating point numbers.

If you're planning to work with numbers of that magnitude you could work with symbolics, but symbolic are very slow since processors only have hardware to manipulate floating point and integers up to 64 bits (~2e19 max value).

However, as pointed out by James, there are algorithms to compute the mod of the power of very large numbers efficiently without ever having to compute the actual numbers. A basic search for modular exponentiation would find them.

[KALYAN ACHARJYA]

@ Guillaume Thanks for the nice explanation!