Talk:Babbage problem: Difference between revisions
Content added Content deleted
(→64-bit integer arithmetic: can all calculate mod 10^6 with 32 bit) |
(→64-bit integer arithmetic: paper-and-pencil method does not deliver in ascending order) |
||
| Line 48: | Line 48: | ||
:There is no need to use 64 bit, as we are only interested in the residues modulo m=10^6, and in modular arithmetic we can just do every addition, subtraction and multiplication modulo m. Thus we can write x = 99,736 = 99 * 1000 + 736; it follows that x² = 99² *1 000² + 2*99*736*1000 + 736². As the first term is 0 mod 10^6, only the last two remain. For the middle term, 99*2*736*1000 = 99*1,472,000 = 99*472,000 = 46,728,000 = 728,000 mod 10^6, thus x² = 728,000 + 541,696 = 1,269,696 = 269,696 mod 10^6. None of the numbers exceeds 31 bits. Of course, as many programming languages do silently calculate mod 2^31, the problem will not be seen. --[[User:Rainglasz|Rainglasz]] ([[User talk:Rainglasz|talk]]) 21:08, 1 December 2018 (UTC) |
:There is no need to use 64 bit, as we are only interested in the residues modulo m=10^6, and in modular arithmetic we can just do every addition, subtraction and multiplication modulo m. Thus we can write x = 99,736 = 99 * 1000 + 736; it follows that x² = 99² *1 000² + 2*99*736*1000 + 736². As the first term is 0 mod 10^6, only the last two remain. For the middle term, 99*2*736*1000 = 99*1,472,000 = 99*472,000 = 46,728,000 = 728,000 mod 10^6, thus x² = 728,000 + 541,696 = 1,269,696 = 269,696 mod 10^6. None of the numbers exceeds 31 bits. Of course, as many programming languages do silently calculate mod 2^31, the problem will not be seen. --[[User:Rainglasz|Rainglasz]] ([[User talk:Rainglasz|talk]]) 21:08, 1 December 2018 (UTC) |
||
:As Babbage did use paper and pencil (this takes less than an hour for the calculations once you have found the method), the results come not necessarily in ascending order, and he probably stopped at the first number that solved his problem, not suspecting that there was a second (smaller) solution with the same number of digits, although he -- as a trained mathematician -- had naturally specified ''smallest integer'' in his problem statement. |
|||
== Thoughts on Babbage's point of view == |
== Thoughts on Babbage's point of view == |
||