

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.




 
 
/* ARM assembly Raspberry PI  */
/*  program babbage.s   */
 
/************************************/
/* Constantes                       */
/************************************/
.equ STDOUT, 1     @ Linux output console
.equ EXIT,   1     @ Linux syscall
.equ WRITE,  4     @ Linux syscall
 
/*********************************/
/* Initialized data              */
/*********************************/
.data
sMessResult:           .ascii "Result = "
sMessValeur:           .fill 11, 1, ' '            @ size => 11
szCarriageReturn:      .asciz "\n"
 
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss  
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                                             @ entry of program 
 
    ldr r4,iNbStart                               @ start number = 269696
    mov r5,#0                                     @ counter multiply
    ldr r2,iNbMult                                @ value multiply = 1 000 000
    mov r6,r4
1:
    mov r0,r6
    bl squareRoot                                 @ compute square root
    umull r1,r3,r0,r0
    cmp r3,#0                                     @ overflow ?
    bne 100f                                      @ yes -> end
    cmp r1,r6                                     @ perfect square
    bne 2f                                        @ no -> loop
    ldr r1,iAdrsMessValeur
    bl conversion10                               @ call conversion decimal
    ldr r0,iAdrsMessResult
    bl affichageMess                              @ display message
    b 100f                                        @ end
2:
    add r5,#1                                     @ increment counter
    mul r3,r5,r2                                  @ multiply by 1 000 000
    add r6,r3,r4                                  @ add start number
    b 1b
 
100:                                              @ standard end of the program 
    mov r0, #0                                    @ return code
    mov r7, #EXIT                                 @ request to exit program
    svc #0                                        @ perform the system call
 
iAdrsMessValeur:          .int sMessValeur
iAdrszCarriageReturn:     .int szCarriageReturn
iAdrsMessResult:          .int sMessResult
iNbStart:                 .int 269696
iNbMult:                  .int 1000000
/******************************************************************/
/*     compute squareRoot                                       */ 
/******************************************************************/
/* r0 contains n          */
/* r0 return result or -1 */
squareRoot:
    push {r1-r5,lr}                     @ save  registers
    cmp r0,#0
    beq 100f                            @ if zero -> end
    movlt r0,#-1                        @ if negatif return - 1
    blt 100f
    cmp r0,#4                           @ if <  4 return 1
    movlt r0,#1
    blt 100f
                                        @ start
    clz r2,r0                           @ number of zeros on the left
    rsb r2,#32                          @ so many useful numbers right
    bic r2,#1                           @ to have an even number of digits
    mov r3,#0b11                        @ mask for extract 2 bits 
    lsl r3,r2
    mov r1,#0                           @ init résult with 0
    mov r4,#0                           @ raz remainder area
 
1:                                      @ begin loop
    and r5,r0,r3                        @ extract 2 bits with mask
    add r4,r5,lsr r2                    @ shift right and addition with remainder 
    lsl r5,r1,#1                        @ multiplication by 2 
    lsl r5,#1                           @ shift left one bit
    orr r5,#1                           @ bit right = 1 
    lsl r1,#1                           @ shift left one bit
    subs r4,r5                          @ sub remainder 
    addmi r4,r4,r5                      @ if negative restaur register
    addpl r1,#1                         @ else add 1 
    subs r2,#2                          @ decrement number bits
    movmi r0,r1                         @ if end return result
    bmi 100f
    lsl r4,#2                           @ no -> shift left remainder 2 bits
    lsr r3,#2                           @ and shift right mask 2 bits 
    b 1b                                @ and loop
 
100:
    pop {r1-r5,lr}                      @ restaur registers 
    bx lr                               @return
/******************************************************************/
/*     display text with size calculation                         */ 
/******************************************************************/
/* r0 contains the address of the message */
affichageMess:
    push {r0,r1,r2,r7,lr}                          @ save  registres
    mov r2,#0                                      @ counter length 
1:                                                 @ loop length calculation 
    ldrb r1,[r0,r2]                                @ read octet start position + index 
    cmp r1,#0                                      @ if 0 its over 
    addne r2,r2,#1                                 @ else add 1 in the length 
    bne 1b                                         @ and loop 
                                                   @ so here r2 contains the length of the message 
    mov r1,r0                                      @ address message in r1 
    mov r0,#STDOUT                                 @ code to write to the standard output Linux 
    mov r7, #WRITE                                 @ code call system "write" 
    svc #0                                         @ call systeme 
    pop {r0,r1,r2,r7,lr}                           @ restaur des  2 registres */ 
    bx lr                                          @ return  
/******************************************************************/
/*     Converting a register to a decimal unsigned                */ 
/******************************************************************/
/* r0 contains value and r1 address area   */
/* r0 return size of result (no zero final in area) */
/* area size => 11 bytes          */
.equ LGZONECAL,   10
conversion10:
    push {r1-r4,lr}                                 @ save registers 
    mov r3,r1
    mov r2,#LGZONECAL
1:                                                  @ start loop
    bl divisionpar10U                               @ unsigned  r0 <- dividende. quotient ->r0 reste -> r1
    add r1,#48                                      @ digit
    strb r1,[r3,r2]                                 @ store digit on area
    cmp r0,#0                                       @ stop if quotient = 0 
    subne r2,#1                                     @ else previous position
    bne 1b                                          @ and loop
                                                    @ and move digit from left of area
    mov r4,#0
2:
    ldrb r1,[r3,r2]
    strb r1,[r3,r4]
    add r2,#1
    add r4,#1
    cmp r2,#LGZONECAL
    ble 2b
                                                      @ and move spaces in end on area
    mov r0,r4                                         @ result length 
    mov r1,#' '                                       @ space
3:
    strb r1,[r3,r4]                                   @ store space in area
    add r4,#1                                         @ next position
    cmp r4,#LGZONECAL
    ble 3b                                            @ loop if r4 <= area size
 
100:
    pop {r1-r4,lr}                                    @ restaur registres 
    bx lr                                             @return
 
/***************************************************/
/*   division par 10   unsigned                    */
/***************************************************/
/* r0 dividende   */
/* r0 quotient    */
/* r1 remainder   */
divisionpar10U:
    push {r2,r3,r4, lr}
    mov r4,r0                                          @ save value
    ldr r3,iMagicNumber                                @ r3 <- magic_number    raspberry 1 2
    umull r1, r2, r3, r0                               @ r1<- Lower32Bits(r1*r0) r2<- Upper32Bits(r1*r0) 
    mov r0, r2, LSR #3                                 @ r2 <- r2 >> shift 3
    add r2,r0,r0, lsl #2                               @ r2 <- r0 * 5 
    sub r1,r4,r2, lsl #1                               @ r1 <- r4 - (r2 * 2)  = r4 - (r0 * 10)
    pop {r2,r3,r4,lr}
    bx lr                                              @ leave function 
iMagicNumber:  	.int 0xCCCCCCCD
 