Anonymous user
Talk:Babbage problem: Difference between revisions
→computer program comments: Reply
(→64-bit integer arithmetic: paper-and-pencil method does not deliver in ascending order) |
imported>PauliKL (→computer program comments: Reply) |
||
| (5 intermediate revisions by 3 users not shown) | |||
Line 26:
It's a good thing that Charles Babbage, being English, understands ..., er, ... ''English'' --- otherwise all of our computer programming languages' comments would be for naught. Ay, what? Jolly good show! -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 09:56, 13 April 2016 (UTC)
:One requirement in the task is that the code should be well documented and commented. Still, many implementations do not have comments at all. [[User:PauliKL|PauliKL]] ([[User talk:PauliKL|talk]]) 10:37, 13 October 2023 (UTC)
==Pictures==
Line 49 ⟶ 51:
: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. --[[User:Rainglasz|Rainglasz]] ([[User talk:Rainglasz|talk]]) 09:02, 4 December 2018 (UTC)
== Thoughts on Babbage's point of view ==
Line 125 ⟶ 127:
More in-depth information on the AE can be found on my website [http://rclab.de/rclab/analyticalengine/]. Other examples are in the document on the AE Game [https://rclab.de/rclab/analyticalengine/visualae], but I currently do not think it would be useful to add the AE as a programming language.
--[[User:Rainglasz|Rainglasz]] ([[User talk:Rainglasz|talk]]) 16:57, 1 December 2018 (UTC)
==Efficiency==
The task calls for an efficient solution. If n<sup>2</sup> ends in 6 then n must end in 4 or 6 which eliminates 80% of the values of n being tested by many (I don't want to say all in case a solution has done this but I couldn't see one) of the solutions being offered. This logic can be extended but I'll settle for the easy 80%.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 18:09, 21 December 2022 (UTC)
:The worst case is 25,264 iterations (sometimes -519), but of course yields the easiest to understand solution, slightly better half that (even only, sometimes -262), slightly better (ends in 4 or 6, as per F# and several others) is 5,057 iterations, slightly better (multiples of 8) 3,158 iterations, even better (prefix*1e6+269696) 638 iterations, and my own Phix/proper method (and I think Tcl.2 and Unix shell.2) builds candidate lists and gets there in just 193 iterations, and could even be cut down to 131. The XPL0 entry suggests it could be done in 100 tests but that entry is certainly not coded like that. There is also a comment at the end of the Python entry suggesting it could be reduced to just 25 iterations. The whole range of possible solutions seems to be represented, from keeping it dirt simple to things (and I don't mean yours) that I simply cannot imagine Mr Babbage would stand any chance of ''ever'' comprehending! --[[User:Petelomax|Petelomax]] ([[User talk:Petelomax|talk]]) 02:05, 22 December 2022 (UTC)
:PS should I mark your F# entry as incorrect, or are you going to fix it? 😀 --[[User:Petelomax|Petelomax]] ([[User talk:Petelomax|talk]]) 11:03, 22 December 2022 (UTC)
| |||