Talk:Babbage problem
task clarification
I can only assume that a positive integer is meant to be found, otherwise finding the smallest negative integer would be pointless.
How about:
-99,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,999,025,264
(Of course, there are smaller numbers!)
And, in the hinterlands of the Rosetta Code coders, it was heard:
Oh yeah? my googolplex thingy is bigger than your googolplex thingy. So there!
-- Gerard Schildberger (talk) 01:17, 13 April 2016 (UTC)
- I've clarified the wording so it now asks for the smallest positive integer. The reference in the Hollingdale and Tootill book only says 'smallest number': but the fact Babbage thought 99736 was the answer makes it clear it was a positive integer he was after. (Hope I'm doing this right—I'm quite new to Rosetta Code.) --Edmund (talk) 05:52, 13 April 2016 (UTC)
computer program comments
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! -- 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. PauliKL (talk) 10:37, 13 October 2023 (UTC)
Pictures
Can we not limit ourselves to a picture of the Analytical Engine, two pictures is a bit much. Fwend (talk) 10:35, 13 April 2016 (UTC)
- Three pictures may be a bit much, two is just right. It's hard to get 1.5 pictures for an average. Just ignore the 2nd picture and not look at it. It's not hurting anything (with the right-justified image). This Rosetta Code task is more about Charles Babbage understanding the computer programs than his analytical engine. I only included the image of the engine because I thought it looked interesting. -- Gerard Schildberger (talk) 11:21, 13 April 2016 (UTC)
- It's crowding the BBC BASIC entry, at least on my screen. Also in other tasks we don't include pictures of the people who invented algorithms either. What is special about Babbage is not his mug but the Analytical Engine. Anyway, we could also move the BBC BASIC entry down, but it would leave a rather large gap. Fwend (talk) 11:27, 13 April 2016 (UTC)
- As for (user) Fwend's screen crowding, that concern/issue will go away as the TOC (table-of-contents) grows larger. This is a pretty simple task as far as Rosetta Code tasks (problems) go. As for who invented what, the picture of Charles Babbage is there as he (or rather, his comprehensibility/understandability) is the main focus of the Rosetta Code task (as we are writing/creating computer code so that he can comprehend and understand the code) --- as far as I can tell, that requirement is a first for Rosetta Code. His picture (or as it was said, his mug) wasn't included because of what he invented. I never assumed or thought that Charles Babbage invented this (or these) particular algorithm(s), we (the programmers et al) are creating the algorithms ourselves, hoping that the clarity and/or simplicity of the computer programming code will be understandable by Babbage (who has never seen a computer or computer program, except possibly for a Jacquard loom). However, I'm sure that Charles Babbage was intelligent enough to only try integers that ended in the decimal digits four or six. -- Gerard Schildberger (talk) 20:59, 13 April 2016 (UTC)
Upgrading from draft task?
Would anybody object if I upgraded this from a draft to a "proper" task? It now has solutions in 20+ programming languages, and there seems to be a reasonable degree of clarity about what it requires. Edmund (talk) 14:18, 20 August 2016 (UTC)
64-bit integer arithmetic
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. --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. --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. --Rainglasz (talk) 09:02, 4 December 2018 (UTC)
Thoughts on Babbage's point of view
To wish that example programs might be easily understood by Babbage himself is a good idea. As he was a trained and capable mathematician, who tend to write as terse as possible, verbosity is not necessary at all.
Furthermore, as he has planned his whole life to build a programmable computer, the Analytical Engine (AE), its concepts should be the starting point.
The AE could only combine two variables by addition, subtraction, multiplication and division (including delivery of the remainder), and send the result to a third variable, not necessarily different from one of the inputs, i.e. allow statements of the form
V1 + V2 -> V3
If the contents of a variable had to be copied, zero had to be added, and the result sent to the new variable.
A large number of variables was planned to be available, and variables were seldomly overwritten, except in loops. Although variables were numbered, this was just a name, not an index; so using single-letter variable names like in mathematics should be fine. But identifieres, i.e. words of letters, were not a concept obvious to him; remember that mathematicians often do not use a multiplication symbol.
As a variable could only be overwritten if it was zero before -- a complication we should leave out here --, all not-initialised variables can be assumed to be reset to zero at start time.
Loops were mentioned in his talk in Milan and the report extended by Ada Lovelace, but never detailled. Nevertheless, simple loops are fine. Note however, that Jaquard cards never used loops, and repeating pattern were created by repeating cards, so loops should only be used where indispensible, not when elegant.
In contrast to Alan Turing, subroutines or functions were not present in the AE, so the examples should refrain from using functions.
As in all early machines, multiplication, although provided by hardware in the AE, was time consuming, even if simple multiplications with 2, 3, 4 or 10 etc were rather quick. Thus, Babbage would never had enumerated square numbers by multiplication, but by using a binominal formula as in my example below.
No text output was availble; only tabular output of rows and columns of numbers. So an example should just print numbers. And of course, to check the lower digits, a division by a power of 10 would be used, no tricky string manipulations.
This leads to my proposal in AWK (without header comments):
# Use x² = (x-1)² + 2x - 1 to enumerate the squares
# The variable x contains 2x in the loop
# Because of 500² = 250000, start at 500
BEGIN {
x = 500
y = x * x
x = 2 * x
do {
x = x + 2
y = y + x
y = y - 1
z = y % 1000000
z = z - 269696
} while (z != 0)
x = x / 2
print x, y
}
More in-depth information on the AE can be found on my website [1]. Other examples are in the document on the AE Game [2], but I currently do not think it would be useful to add the AE as a programming language. --Rainglasz (talk) 16:57, 1 December 2018 (UTC)
Efficiency
The task calls for an efficient solution. If n2 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%.--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! --Petelomax (talk) 02:05, 22 December 2022 (UTC)
- PS should I mark your F# entry as incorrect, or are you going to fix it? 😀 --Petelomax (talk) 11:03, 22 December 2022 (UTC)