Talk:Babbage problem: Difference between revisions
Content added Content deleted
m (→Thoughts on Babbage's point of view: signature added) |
(→64-bit integer arithmetic: can all calculate mod 10^6 with 32 bit) |
||
| Line 46: | Line 46: | ||
Hopefully Mister Babbage you guessed wrong! The solution of your problem is 25264 and not 99736. Hopefully because half of the languages examples would have been wrong. Because the square of 25264 (638,269,696) needs only the 32-bit integer type but the square of 99736 (9,947,269,696) needs the 64-bit integer type! And a lot of languages have problems with it. --[[User: PatGarrett|PatGarrett]] ([[User talk: PatGarrett|talk]]) 19:47, 11 February 2017 (UTC) |
Hopefully Mister Babbage you guessed wrong! The solution of your problem is 25264 and not 99736. Hopefully because half of the languages examples would have been wrong. Because the square of 25264 (638,269,696) needs only the 32-bit integer type but the square of 99736 (9,947,269,696) needs the 64-bit integer type! And a lot of languages have problems with it. --[[User: PatGarrett|PatGarrett]] ([[User talk: PatGarrett|talk]]) 19:47, 11 February 2017 (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) |
|||
== Thoughts on Babbage's point of view == |
== Thoughts on Babbage's point of view == |
||