Babbage problem: Difference between revisions
(Added Smalltalk) |
|||
Line 479: | Line 479: | ||
25264 |
25264 |
||
</pre> |
</pre> |
||
=={{header|Smalltalk}}== |
|||
<lang smalltalk>"We use one variable, called n. Let it initially be equal to 1. Then keep increasing it by 1 for only as long as the remainder after dividing by a million is not equal to 269,696; finally, show the value of n." |
|||
| n | |
|||
n := 1. |
|||
[ n squared \\ 1000000 = 269696 ] whileFalse: [ n := n + 1 ]. |
|||
n</lang> |
|||
{{out}} |
|||
<pre>25264</pre> |
|||
=={{header|x86 Assembly}}== |
=={{header|x86 Assembly}}== |
Revision as of 11:08, 12 August 2016
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
The task is to find out—and to do so, as far as your language allows it, in code that Babbage himself would have been able to read and understand.
For these purposes, Charles Babbage may be taken to be an intelligent person, familiar with mathematics and with the idea of a computer, who has never programmed—in fact, who has never so much as seen a single line of code.
- task aim
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.
ALGOL 68
As wih other samples, we use "simple" forms such as "a := a + 1" instead of "a +:= 1". <lang algol68>COMMENT text between pairs of words 'comment' in capitals are
for the human reader's information and are ignored by the machine
COMMENT
COMMENT Define s to be the integer value 269 696 COMMENT INT s = 269 696;
COMMENT Name a location in the machine's storage area that will be
used to hold integer values. The value stored in the location will change during the calculations. Note, "*" is used to represent the multiplication operator. ":=" causes the location named to the left of ":=" to assume the value computed by the expression to the right. "sqrt" computes an approximation to the square root of the supplied parameter "MOD" is an operator that computes the modulus of its left operand with respect to its right operand "ENTIER" is a unary operator that yields the largest integer that is at most its operand.
COMMENT INT v := ENTIER sqrt( s );
COMMENT the construct: WHILE...DO...OD repeatedly executes the
instructions between DO and OD, the execution stops when the instructions between WHILE and DO yield the value FALSE.
COMMENT WHILE ( v * v ) MOD 1 000 000 /= s DO v := v + 1 OD;
COMMENT print displays the values of its parameters COMMENT print( ( v, " when squared is: ", v * v, newline ) )</lang>
- Output:
+25264 when squared is: +638269696
APL
If at all possible, I would sit down at a terminal with Babbage and invite him to experiment with the various functions used in the program. <lang apl> ⍝ We know that 99,736 is a valid answer, so we only need to test the positive integers from 1 up to there:
N←⍳99736 ⍝ The SQUARE OF omega is omega times omega: SQUAREOF←{⍵×⍵} ⍝ To say that alpha ENDS IN the six-digit number omega means that alpha divided by 1,000,000 leaves remainder omega: ENDSIN←{(1000000|⍺)=⍵} ⍝ The SMALLEST number WHERE some condition is met is found by taking the first number from a list of attempts, after rearranging the list so that numbers satisfying the condition come before those that fail to satisfy it: SMALLESTWHERE←{1↑⍒⍵} ⍝ We can now ask the computer for the answer: SMALLESTWHERE (SQUAREOF N) ENDSIN 269696</lang>
- Output:
25264
AWK
<lang AWK>
- A comment starts with a "#" and are ignored by the machine. They can be on a
- line by themselves or at the end of an executable line.
- A program consists of multiple lines or statements. This program tests
- positive integers starting at 1 and terminates when one is found whose square
- ends in 269696.
- The next line shows how to run the program.
- syntax: GAWK -f BABBAGE_PROBLEM.AWK
BEGIN { # start of program
- this declares a variable named "n" and assigns it a value of zero
n = 0
- do what's inside the "{}" until n times n ends in 269696
do { n = n + 1 # add 1 to n } while (n*n !~ /269696$/)
- print the answer
print("The smallest number whose square ends in 269696 is " n) print("Its square is " n*n)
- terminate program
exit(0)
} # end of program </lang>
Output:
The smallest number whose square ends in 269696 is 25264 Its square is 638269696
BBC BASIC
Clarity has been preferred over all other considerations. The line LET n = n + 1, for instance, would more naturally be written n% += 1, using an integer variable and a less verbose assignment syntax; but this optimization did not seem to justify the additional explanations Professor Babbage would probably need to understand it. <lang bbcbasic>REM Statements beginning 'REM' are explanatory remarks: the machine will ignore them.
REM We shall test positive integers from 1 upwards until we find one whose square ends in 269,696.
REM A number that ends in 269,696 is one that leaves a remainder of 269,696 when divided by a million.
REM So we are looking for a value of n that satisfies the condition 'n squared modulo 1,000,000 = 269,696', or 'n^2 MOD 1000000 = 269696' in the notation that the machine can accept.
LET n = 0
REPEAT
LET n = n + 1
UNTIL n^2 MOD 1000000 = 269696
PRINT "The smallest number whose square ends in 269696 is" n
PRINT "Its square is" n^2</lang>
- Output:
The smallest number whose square ends in 269696 is 25264 Its square is 638269696
C++
<lang Cpp>#include <iostream>
int main( ) {
int current = 0 ; while ( ( current * current ) % 1000000 != 269696 ) current++ ; std::cout << "The square of " << current << " is " << (current * current) << " !\n" ; return 0 ;
}</lang>
- Output:
The square of 25264 is 638269696 !
COBOL
<lang cobol>IDENTIFICATION DIVISION. PROGRAM-ID. BABBAGE-PROGRAM.
- A line beginning with an asterisk is an explanatory note.
- The machine will disregard any such line.
DATA DIVISION. WORKING-STORAGE SECTION.
- In this part of the program we reserve the storage space we shall
- be using for our variables, using a 'PICTURE' clause to specify
- how many digits the machine is to keep free.
- The prefixed number 77 indicates that these variables do not form part
- of any larger 'record' that we might want to deal with as a whole.
77 N PICTURE 99999.
- We know that 99,736 is a valid answer.
77 N-SQUARED PICTURE 9999999999. 77 LAST-SIX PICTURE 999999. PROCEDURE DIVISION.
- Here we specify the calculations that the machine is to carry out.
CONTROL-PARAGRAPH.
PERFORM COMPUTATION-PARAGRAPH VARYING N FROM 1 BY 1 UNTIL LAST-SIX IS EQUAL TO 269696. STOP RUN.
COMPUTATION-PARAGRAPH.
MULTIPLY N BY N GIVING N-SQUARED. MOVE N-SQUARED TO LAST-SIX.
- Since the variable LAST-SIX can hold a maximum of six digits,
- only the final six digits of N-SQUARED will be moved into it:
- the rest will not fit and will simply be discarded.
IF LAST-SIX IS EQUAL TO 269696 THEN DISPLAY N.</lang>
- Output:
25264
D
<lang D>// It's basically the same as any other version. // What can be observed is that 269696 is even, so we have to consider only even numbers, // because only the square of even numbers is even.
import std.math; import std.stdio;
void main( ) {
// get smallest number <= sqrt(269696) int k = cast(int)(sqrt(269696.0));
// if root is odd -> make it even if (k % 2 == 1) k = k - 1;
// cycle through numbers while ((k * k) % 1000000 != 269696) k = k + 2;
// display output writefln("%d * %d = %d", k, k, k*k);
}</lang>
- Output:
25264 * 25264 = 638269696
Elixir
<lang elixir>defmodule Babbage do
def problem(n) when rem(n*n,1000000)==269696, do: n def problem(n), do: problem(n+2)
end
IO.puts Babbage.problem(0)</lang> or <lang elixir>Stream.iterate(2, &(&1+2)) |> Enum.find(&rem(&1*&1, 1000000) == 269696) |> IO.puts</lang>
- Output:
25264
Haskell
<lang Haskell>--calculate the squares of integer , testing for the last 6 digits findBabbageNumber :: Integer findBabbageNumber = head $ filter myCondition [1..]
where myCondition :: Integer -> Bool myCondition n = mod ( n ^ 2 ) 1000000 == 269696
--print out the result main :: IO ( ) main = do
let babbageNumber = findBabbageNumber let squareOfNumber = babbageNumber ^ 2 putStr $ show babbageNumber putStr " ^ 2 equals " putStr $ show squareOfNumber putStrLn " !"</lang>
- Output:
25264 ^ 2 equals 638269696 !
J
The key to understandability is a mix of hopefully adequate notation and some level of verifiability.
So let's break the implementation into some named pieces and present enough detail that a mathematician can verify that the result is both consistent and reasonable:
<lang J> square=: ^&2
modulo1e6=: 1000000&| trythese=: i. 1000000 NB. first million nonnegative integers which=: I. NB. position of true values which 269696=modulo1e6 square trythese NB. right to left <-
25264 99736 150264 224736 275264 349736 400264 474736 525264 599736 650264 724736 775264 849736 900264 974736</lang>
The smallest of these values is 25264.
Java
<lang java>public class Test {
public static void main(String[] args) {
// let n be zero int n = 0;
// repeat the following action do {
// increase n by 1 n++;
// while the modulo of n times n is not equal to 269696 } while (n * n % 1000_000 != 269696);
// show the result System.out.println(n); }
}</lang>
25264
Perl
<lang Perl>#!/usr/bin/perl use strict ; use warnings ;
my $current = 0 ; while ( ($current ** 2 ) % 1000000 != 269696 ) {
$current++ ;
} print "The square of $current is " . ($current * $current) . " !\n" ;</lang>
- Output:
The square of 25264 is 638269696 !
Perl 6
This could certainly be written more concisely. Extra verbiage is included to make the process more clear. <lang perl6># For all positives integers from 1 to Infinity for 1 .. Inf -> $integer {
# calculate the square of the integer my $square = $integer²; # print the integer and square and exit if the square modulo 1000000 is equal to 269696 print "{$integer}² equals $square" and exit if $square % 1000000 == 269696;
}</lang>
- Output:
25264² equals 638269696
Processing
<lang java>// Lines that begin with two slashes, thus, are comments: they // will be ignored by the machine.
// First we must declare a variable, n, suitable to store an integer:
int n;
// Each statement we address to the machine must end with a semicolon.
// To begin with, the value of n will be zero:
n = 0;
// Now we must repeatedly increase it by one, checking each time to see // whether its square ends in 269,696.
// We shall do this by seeing whether the remainder, when n squared // is divided by one million, is equal to 269,696.
do {
n = n + 1;
} while (n * n % 1000000 != 269696);
// To read this formula, it is necessary to know the following // elements of the notation: // * means 'multiplied by' // % means 'modulo', or remainder after division // != means 'is not equal to'
// Now that we have our result, we need to display it.
// println is short for 'print line'
println(n);</lang>
- Output:
25264
Python
<lang python># Lines that start by # are a comments:
- they will be ingnored by the machine
n=0 # n is a varible and its value is 0
- we will increase its value by one untill
- its square ends in 269,696
while n**2%1000000!=269696:
- n**2 -> n squared
- % -> 'modulo' or remainer after division
- != -> not equal to
n=n+1 # increase n by 1
print(n) # prints n </lang>
- Output:
25264
REXX
If this were a computer program to be shown to a computer programming novice (albeit a very
intelligent polymath novice), the computer program would also have a lot more comments,
notes, and accompanying verbiage which would/could/should explain:
- what a (computer program) comment looks like
- what a computer is
- what a computer program is
- how a computer stores numbers and such
- what are variables and how to store stuff in them
- how the do loop works (initial value, incrementation, etc)
- how an assignment = operator works
- how a comparison == operator works
- how an if statement works
- what a (computer program) statement is
- what the * operator is and how it does multiplication
- what the + operator is and how it does addition
- what the // operator is and how it does division remainder
- what the right BIF does
-
whowhat a BIF is and how it returns a value - how/when the then cause gets executed (after an if)
- explain how/why an end statement is needed for a do loop
- explain how a leave statement works
- ··· the say is probably the only statement that is self-explanatory
examine the right-most 6 digits of square
<lang rexx>/*REXX program finds the lowest (positive) integer whose square ends in 269,696. */
/*operator * is multiplication. */ do j=2 by 2 /*start J at two, increment by two. */ if right(j*j, 6)==269696 then leave /*is six right-most digits our target? */ end /*this signifies the end of the DO loop*/
say "The smallest integer whose square ends in 269,696 is: " j</lang> output
The smallest integer whose square ends in 269,696 is: 25264
examine remainder after dividing by 1 million
<lang rexx>/*REXX program finds the lowest (positive) integer whose square ends in 269,696. */
/*operator // is division remainder.*/ do j=2 by 2 /*start J at two, increment by two. */ if j*j // 1000000 == 269696 then leave /*is square mod 1-million our target ? */ end /*this signifies the end of the DO loop*/
say "The smallest integer whose square ends in 269,696 is: " j</lang> output is identical as the 1st REXX version.
examine only numbers ending in 4 or 6
<lang rexx>/*REXX program finds the lowest (positive) integer whose square ends in 269,696. */
/*we'll only examine integers that are */ /* ending in four or six. */
do j=4 by 10 /*start J at four, increment by ten.*/ k=j /*set K to J's value. */ if right(k*k, 6)==269696 then leave /*examine the right-most six digits. */
k=j+2 /*set K to J+2 value. */ if right(k*k, 6)==269696 then leave /*examine the right-most six digits. */ end /*this signifies the end of the DO loop*/
say "The smallest integer whose square ends in 269,696 is: " k</lang>
output is identical as the 1st REXX version.
start with smallest possible number
<lang rexx>/*REXX ----------------------------------------------------------------
- The solution must actually be larger than sqrt(269696)=519.585
- --------------------------------------------------------------------*/
z=0 Do i=524 By 10 Until z>0
If right(i*i,6)==269696 then z=i Else Do j=i+2 if right(j*j,6)==269696 then z=j End End
Say "The smallest integer whose square ends in 269696 is:" z Say ' 'z'**2 =' z**2</lang>
- Output:
The smallest integer whose square ends in 269696 is: 25264 25264**2 = 638269696
Ring
<lang ring> n = 0 while pow(n,2) % 1000000 != 269696
n = n + 1
end
see "The smallest number whose square ends in 269696 is : " + n + nl see "Its square is : " + pow(n,2) </lang> Output:
The smallest number whose square ends in 269696 is : 25264 Its square is : 638269696
Ruby
<lang ruby>n = 0 n = n + 2 until (n*n).modulo(1000000) == 269696 puts n </lang>
Sidef
<lang ruby>var n = 0 while (n*n % 1000000 != 269696) {
n += 2
} say n</lang>
- Output:
25264
Smalltalk
<lang smalltalk>"We use one variable, called n. Let it initially be equal to 1. Then keep increasing it by 1 for only as long as the remainder after dividing by a million is not equal to 269,696; finally, show the value of n." | n | n := 1. [ n squared \\ 1000000 = 269696 ] whileFalse: [ n := n + 1 ]. n</lang>
- Output:
25264
x86 Assembly
AT&T syntax
<lang asmatt># 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.</lang>
- Output:
25264
XLISP
<lang scheme>; The computer will evaluate expressions written in -- possibly nested -- parentheses, where the first symbol gives the operation and any subsequent symbols or numbers give the operands.
- For instance, (+ (+ 2 2) (- 7 5)) evaluates to 6.
- We define our problem as a function
(define (try n)
- We are looking for a value of n that leaves 269,696 as the remainder when its square is divided by a million.
- The symbol * stands for multiplication.
(if (= (remainder (* n n) 1000000) 269696)
- If this condition is met, the function should give us the value of n
n
- If not, it should try n+1
(try (+ n 1))))
- We supply our function with 1 as an initial value to test, and ask the computer to print the final result.
(print (try 1))</lang>
- Output:
25264
zkl
<lang zkl>// The magic number is 269696, so, starting about its square root, // find the first integer that, when squared, its last six digits are the magic number. // The last digits are found with modulo, represented here by the % symbol const N=269696; [500..].filter1(fcn(n){ n*n%0d1_000_000 == N })</lang>
- Output:
25264