Babbage problem: Difference between revisions
→{{header|RPL}}
Cyril Nocton (talk | contribs) (→Wrapper: Nil.) |
|||
Line 3,575:
The smallest number whose square ends in 269696 is : 25264
Its square is : 638269696
</pre>
=={{header|RPL}}==
Whoever trying to make easy-to-understand RPL code faces 3 main roadblocks:
# data handling relies on a stack, even if variables can also be used
# syntax is postfixed - which makes sense with stack-based operations
# comments cannot be freely inserted within the code
Mr Babbage was a great mathematician and, having worked on the task, he must know that the solution s is a multiple of 8, since
s^2 = n.10^6 + 269696 = 64 * (15625.n + 4214)
and that it is greater than the square root of 269696. A simple but efficient algorithm is then to test all multiples of 8 from 512, which is the multiple just below the square root of 269696, up to the solution. In the worst case, the loop would end at 99736..
But without some previous training, even a very clever man like Mr. Babbage would have some difficulty to decipher such an algorithm within the uncommented RPL code to solve the task:
≪ 512 '''DO''' 8 + '''UNTIL''' DUP n SQ 1E6 MOD 269696 == '''END''' ≫
To better answer the task, it is then needed to adopt a coding style closer to the one used by Mr. Babbage (and Mrs. Lovelace) to program the Analytic Engine (AE).
Such programs were actually tables, one line figuring one program step, the left columns (the 'Mill' = the CPU) describing the arithmetic operations to perform from registers to registers, called 'variables' and named v0..vn, represented by the columns on the right (the 'Store' = the RAM). Due to this syntax, it was not possible in the same instruction to use a variable both as an operand and a destination, i.e. <code>x = x + y </code> could not be directly coded.
Operations were restricted to <code>+-*/</code>. What seems today basic like <code>x^y</code> or <code>MOD(x)</code> was not wired in the AE. And don't even think about a function calculating the square root...
Branch instructions were not available : AE's human operator, in charge of initializing the variables and turning the crank (= both the CPU clock and the power supply), had also to analyze the results and react accordingly, thus assuming the responsibility of properly executing all the <code>IF..THEN..ELSE</code> and <code>DO..UNTIL</code> that algorithms would require.
The following program mimics Mr. Babbage's programming way, inspired by these [https://collection.sciencemuseumgroup.org.uk/documents/aa110000065%20on%20solving%20two%20simultaneous%20equations| notes on solving two simultaneous equations] kept by the Science Museum Group Collection.
After a short initialisation sequence affecting values to some column variables, the « Mill » calls 2 variables line after line, performs an arithmetic operation and put back the result in a specific column variable of the « Store ». Once the calculation sequence is completed, the AE operator shall take a decision, according to the value of column v4;
{{works with|Halcyon Calc|4.2.7}}
{| class="wikitable"
! Code for Mr. Babbage
! Comments for Rosetta Coders
|-
|
≪ 512 0 8 1000000 269696
'v0' 'v10' 'v11' 'v12' 'v13'
→STORE
'''DO'''
''Mill Store''
v0 v11 + 'v1' °END
v1 v10 + 'v0' °END
v0 v1 * 'v2' °END
v2 v12 / 'v3' °END
v3 v12 * 'v4' °END
v2 v4 - 'v3' °END
v3 v13 - 'v4' °END
'''UNTIL''' v4 IS°NIL END
PRINT v4
≫
|
Store the starting values of n and constants
into each variable below
Let's start turning the crank
v1 = v0 + v11 = n + 8
v0 = v1 + 0 = n + 8 // the only way to copy a register into another
v2 = v0 x v1 = n^2
v3 = v2 % v12 = n^2 % 10000
v4 = v3 * v12 = (n^2 % 10000)*10000
v3 = v2 - v4 = n^2 mod 10000
v4 = v3 - v13 = (n^2 mod 10000) - 269696
Exit condition
Babbage's machine had a printer!
|}
Some words have been especially created to improve Babbage-readability: <code>→STORE</code> stores values in the appropriate variables, <code>IS°NIL</code> compares stack content to zero, <code>°END</code> actually stores stack content into the variable named just before; <code>Mill</code> <code>Store</code> and <code>PRINT</code> do absolutely nothing and are actually one-word comments:
≪ 6 2 '''FOR''' n n ROLL SWAP STO -1 '''STEP''' ≫ '→STORE' STO
≪ 0 == ≫ 'IS°NIL' STO
≪ SWAP IP SWAP STO ≫ '°END' STO
≪ ≫ 'Mill' STO
≪ ≫ 'Store' STO
≪ ≫ 'PRINT' STO
{{out}}
<pre>
1: 25264
</pre>
| |||