Talk:Babbage problem: Difference between revisions
→Efficiency
(Efficiency) |
|||
Line 129:
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 is 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)
| |||