

Charles Babbage, looking ahead to the sorts of problems his Analytical Engine would be able to solve, gave this example:

 What is the smallest positive integer whose square ends in the digits 269,696?

— Babbage, letter to Lord Bowden, 1837; see Hollingdale and Tootill, Electronic Computers, second edition, 1970, p. 125.

He thought the answer might be 99,736, whose square is 9,947,269,696; but he couldn't be certain.



Task[edit]
The task is to find out if Babbage had the right answer — and to do so, as far as your language allows it, in code that Babbage himself would have been able to read and understand.
As Babbage evidently solved the task with pencil and paper, a similar efficient solution is preferred.

For these purposes, Charles Babbage may be taken to be an intelligent person, familiar with mathematics and with the idea of a computer; he has written the first drafts of simple computer programmes in tabular form. [Babbage Archive Series L].



Motivation
The aim of the task is to write a program that is sufficiently clear and well-documented for such a person to be able to read it and be confident that it does indeed solve the specified problem.




# What is the lowest number whose square ends in 269,696?
 
# At the very end, when we have a result and we need to print it, we shall use for the purpose a program called PRINTF, which forms part of a library of similar utility programs that are provided for us. The codes given here will be needed at that point to tell PRINTF that we are asking it to print a decimal integer (as opposed to, for instance, text):
 
.data
decin: .string "%d\n\0"
 
# This marks the beginning of our program proper:
 
.text
.global main
 
main:
 
# We shall test numbers from 1 upwards to see whether their squares leave a remainder of 269,696 when divided by a million.
 
# We shall be making use of four machine 'registers', called EAX, EBX, ECX, and EDX. Each can hold one integer.
 
# Move the number 1,000,000 into EBX:
 
        mov    $1000000, %ebx
 
# The numbers we are testing will be stored in ECX. We start by moving a 1 there:
 
        mov    $1,       %ecx
 
# Now we need to test whether the number satisfies our requirements. We shall want the computer to come back and repeat this sequence of instructions for each successive integer until we have found the answer, so we put a label ('next') to which we can refer.
 
next:
 
# We move (in fact copy) the number stored in ECX into EAX, where we shall be able to perform some calculations upon it without disturbing the original:
 
        mov    %ecx,     %eax
 
# Multiply the number in EAX by itself:
 
        mul    %eax
 
# Divide the number in EAX (now the square of the number in ECX) by the number in EBX (one million). The quotient -- for which we have no use -- will be placed in EAX, and the remainder in EDX:
 
        idiv   %ebx
 
# Compare the number in EDX with 269,696. If they are equal, jump ahead to the label 'done':
 
        cmp    $269696,  %edx
        je     done
 
# Otherwise, increment the number in ECX and jump back to the label 'next':
 
        inc    %ecx
        jmp    next
 
# If we get to the label 'done', it means the answer is in ECX.
 
done:
 
# Put a reference to the codes for PRINTF into EAX:
 
        lea    decin,    %eax
 
# Now copy the number in ECX, which is our answer, into an area of temporary storage where PRINTF will expect to find it:
 
        push   %ecx
 
# Do the same with EAX -- giving the code for 'decimal integer' -- and then call PRINTF to print the answer:
 
        push   %eax
        call   printf
 
# The pieces of information we provided to PRINTF are still taking up some temporary storage. They are no longer needed, so make that space available again:
 
        add    $8,       %esp
 
# Place the number 0 in EAX -- a conventional way of indicating that the program has finished correctly -- and return control to whichever program called this one:
 
        mov    $0,       %eax
        ret
 
# The end.