I want to show that 17^21 + 19^21 is divisible by 36 by actual computation of the integers and getting the remainder by division. Is it possible in MATLAB?
4 次查看(过去 30 天)
显示 更早的评论
I want to show that 17^21 + 19^21 is divisible by 36 by actual computation of the integers and getting the remainder and quotient by division. Is it possible in MATLAB? I know to prove by algebra. But I want to compute the actual values. My machine is 64 bit. uint64 saturates for these numbers and you dont get the exact values.
3 个评论
John D'Errico
2015-10-1
@Jon - Sorry, but you are simply wrong here. Those numbers overflow the precision available to a double.
Jon
2015-10-2
Technically nothing I stated was wrong, but I concede I had no business answering this question. Nice answer below.
回答(2 个)
John D'Errico
2015-10-1
Jon was wrong in his comment. Why? I'll show the true answer using my vpi toolbox.
vpij(17)^21 + vpij(19)^21
ans =
783301429606381938554583636
See that the number is large. Larger than you can store in a double. The limit of a double to represent a number as a flint (a floating point number that represents an exact integer, and does so with no error) is 2^53 - 1.
log2((17)^21 + (19)^21)
ans =
89.34
In fact, the above shows the number is too large to be stored in a uint64, which would be limited to 64 bits.
Is it divisible by 36? Yes. Again, my vpi toolbox gives a result that you can trust.
mod(vpi(17)^21 + vpi(19)^21,36)
ans =
0
Can we know this is true using only arithmetic based on doubles? Yes. It is not even that terribly difficult, just a short loop.
m17 = 1;
m19 = 1;
for i = 1:21
m17 = mod(m17*17,36);
m19 = mod(m19*19,36);
end
mod(m17 + m19,36)
ans =
0
So clearly this is quite doable using only small integers and a short loop, all of which numbers fit easily into a double. In fact, we could have done the computation using uint16 integers, since nothing in that computation could possibly ever be larger than 18*19+16*17=614.
Had the exponent been larger, it is actually possible to do the computation efficiently in O(log2( p)), where p is the exponent. Of course, the loop I wrote above is only O( p), so not as good if p were immensely large.
0 个评论
Walter Roberson
2015-10-1
John D'Errico will probably mention his Variable Precision Integer package from the File Exchange.
You can also proceed using the Symbolic Toolbox:
S = sym(17)^21 + sym(19)^21;
mod(S, 36)
1 个评论
John D'Errico
2015-10-1
编辑:John D'Errico
2015-10-1
:)
Or its successor, vpij. But you can also do it using uint16 integers.
另请参阅
产品
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!