Matlab wrong modulo result when divident rises to power
Just wondering ... I tried to do the (111 ^ 11) mod143 operation manually (using the multiplication and square method) and I got the result 67. I also checked that this is correct in many online tools. However, when connecting Matlab:
mod(111^11,143)
gives 127! Is there a specific reason for this? I didn't find anything in the documentation ...
source to share
The value 111^11
(about 3.1518e+022
) exceeds the maximum number that is guaranteed to be represented exactly as double
, which is 2^53
(about 9.0072e+015
). Thus, the result is spoiled by insufficient numerical precision.
To achieve the correct result, use symbolic computation:
>> syms x y z
>> r = mod(x^y, z);
>> subs(r, [x y z], [111 11 143])
ans =
67
Alternatively, for this particular operation (modulo a large number, expressed as the product of small numbers), you can easily compute using the following fact (where ∗
denotes the product):
mod (a * b, z) = mod (mod (a, z) * mod (b, z), z)
That is, you can apply the modulo operation to the factors of your large number, and the end result will not change. If you choose coefficients small enough that they can be represented exactly as double
, you can perform the calculation numerically without losing precision.
For example: using the decomposition 111 ^ 11 = 111 ^ 4 * 111 ^ 4 * 111 ^ 3, since all factors are small enough, gives the correct result:
>> mod((mod(111^4, 143))^2 * mod(111^3, 143), 143) ans = 67
Similarly, using 111 ^ 2 and 111 as factors,
>> mod((mod(111^2, 143))^5 * mod(111, 143), 143) ans = 67
source to share
from matlab site it is recommended to use powermod(b, e, m)
(b ^ e mod m)
"If b and m are numbers, the modular cardinality of b ^ e mod m can also be calculated directly by calling b ^ e mod m. However, powermod(b, e, m)
it avoids the overhead of calculating the intermediate result be and calculates the modular cardinality much more efficiently."
source to share