Babbage problem: Difference between revisions
Content deleted Content added
Cyril Nocton (talk | contribs) →Wrapper: Nil. |
|||
Line 3,575: | Line 3,575: | ||
The smallest number whose square ends in 269696 is : 25264 |
The smallest number whose square ends in 269696 is : 25264 |
||
Its square is : 638269696 |
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> |
</pre> |
||