Matlab Calculates mod(2^1000,10^23) wrong

Hello,

I was trying to write an algorithm for something and I figured out that matlab calculates these equation wrong: mod(2^1000,10^x) where x>22. Not sure if this mistake occurs in all x which is bigger then 22, I just tested until 30. Do you guys have same problem?

Answer 1

[Rik]

If you want this much precision, maybe you should use a different method. 2^1000 is a 301 digit number. It will take at least 1000 bits (125 bytes), Matlab doesn't have such a data type, so this code will not work almost by definition.

Answer 2

[James Tursa]

To expand on what Rik has posted ...

IEEE double precision numbers only have about 16-17 equivalent decimal digits of precision. Even though MATLAB can store high powers of 2 exactly (e.g., MATLAB stores 2^1000 exactly), if you do arithmetic with it that needs to get at the 1's digit like a mod() function, you are way overboard with the available precision for that. MATLAB can store 10^22 exactly but can't store 10^23 exactly. E.g., using double precision:

>> num2strexact(2^1000)
ans =
1.0715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376e301
>> num2strexact(10^22)
ans =
1e22
>> mod(2^1000,10^22)
ans =
     0   <-- WRONG!!!  You can simply inspect the string above to see this.

Using the Symbolic Toolbox vpa() function:

>> digits 500
>> vpa(2)^1000
ans =
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376.0
>> vpa(10)^22
ans =
10000000000000000000000.0
>> n = floor(vpa(2)^1000/vpa(10)^22)
n =
1071508607186267320948425049060001810561404811705533607443750388370351051124936122493198378815695858127594672917553146825187145285692314043598457757469857480393456777482423098542107460506237114187795418215304647498358194126739876755916554394607706291457119647768654216766042983165
>> vpa(2)^1000 - n*vpa(10)^22
ans =
2624386837205668069376.0   <-- CORRECT!

So, even though IEEE double can store 2^1000 and 10^22 exactly, it can't do the mod function correctly down to the 1's digit. You need another tool to do the calculation with that level of precision. See also these FEX submissions by John D'Errico:

https://www.mathworks.com/matlabcentral/fileexchange/36534-hpf-a-big-decimal-class

https://www.mathworks.com/matlabcentral/fileexchange/22725-variable-precision-integer-arithmetic

num2strexact can be found here:

https://www.mathworks.com/matlabcentral/fileexchange/22239-num2strexact--exact-version-of-num2str-

Answer 3

[Walter Roberson]

https://www.mathworks.com/help/symbolic/powermod.html

https://www.mathworks.com/matlabcentral/fileexchange/22725-variable-precision-integer-arithmetic