Calkin-Wilf sequence: Difference between revisions
Added solution for Little Man Computer
No edit summary |
(Added solution for Little Man Computer) |
||
Line 1,101:
83116//51639 is the 123456789-th term of the sequence.
</pre>
=={{header|Little Man Computer}}==
Runs in a home-made simulator, which is mostly compatible with Peter Higginson's online simulator. Only, for better control of the output format, I've added an instruction OTX (extended output). To run the code in PH's simulator, replace OTX and its parameter with OUT and no parameter.
===Find first n terms===
{{trans|Pascal}}
<lang Little Man Computer>
// Little Man Computer, for Rosetta Code.
// Displays terms of Calkin-Wilf sequence up to the given index.
// The chosen algorithm calculates the i-th term directly from i
// (i.e. not using any previous terms).
input INP // get number of terms from user
BRZ exit // exit if 0
STA max_i // store maximum index
LDA c1 // index := 1
next_i STA i
// Write index followed by '->'
OTX 3 // non-standard: minimum width 3, no new line
LDA asc_hy
OTC
LDA asc_gt
OTC
// Find greatest power of 2 not exceeding i,
// and count the number of binary digits in i.
LDA c1
STA pwr2
loop2 STA nrDigits
LDA i
SUB pwr2
SUB pwr2
BRP double
BRA part2 // jump out if next power of 2 would exceed i
double LDA pwr2
ADD pwr2
STA pwr2
LDA nrDigits
ADD c1
BRA loop2
// The nth term a/b is calculated from the binary digits of i.
// The leading 1 is not used.
part2 LDA c1
STA a // a := 1
STA b // b := 1
LDA i
SUB pwr2
STA diff
// Pre-decrement count, since leading 1 is not used
dec_ct LDA nrDigits // count down the number of digits
SUB c1
BRZ output // if all digits done, output the result
STA nrDigits
// We now want to compare diff with pwr2/2.
// Since division is awkward in LMC, we compare 2*diff with pwr2.
LDA diff // diff := 2*diff
ADD diff
STA diff
SUB pwr2 // is diff >= pwr2 ?
BRP digit_1 // binary digit is 1 if yes, 0 if no
// If binary digit is 0 then set b := a + b
LDA a
ADD b
STA b
BRA dec_ct
// If binary digit is 1 then update diff and set a := a + b
digit_1 STA diff
LDA a
ADD b
STA a
BRA dec_ct
// Now have nth term a/b. Write it to the output.
output LDA a // write a
OTX 1 // non-standard: minimum width 1; no new line
LDA asc_sl // write slash
OTC
LDA b // write b
OTX 11 // non-standard: minimum width 1; add new line
LDA i // have we done maximum i yet?
SUB max_i
BRZ exit // if yes, exit
LDA i // if no, increment i and loop back
ADD c1
BRA next_i
exit HLT
// Constants
c1 DAT 1
asc_hy DAT 45
asc_gt DAT 62
asc_sl DAT 47
// Variables
i DAT
max_i DAT
pwr2 DAT
nrDigits DAT
diff DAT
a DAT
b DAT
// end
</lang>
{{out}}
<pre>
1->1/1
2->1/2
3->2/1
4->1/3
5->3/2
6->2/3
7->3/1
8->1/4
9->4/3
10->3/5
11->5/2
12->2/5
13->5/3
14->3/4
15->4/1
16->1/5
17->5/4
18->4/7
19->7/3
20->3/8
</pre>
===Find index of a given term===
{{trans|Pascal}}
The numbers in part 2 of the task are too large for LMC, so the demo program just confirms the example, that 9/4 is the 35th term.
<lang Little Man Computer>
// Little Man Computer, for Rosetta Code.
// Calkin-Wilf sequence: displays index of term entered by user.
INP // get numerator from user
BRZ exit // exit if 0
STA num
STA a // initialize a := numerator
INP // get denominator from user
BRZ exit // exit if 0
STA den
STA b // initialize b := denominator
LDA c0 // initialize index := 0
STA index
LDA c1 // initialize power of 2 := 1
STA pwr2
// Build binary digits of the index
loop LDA a // is a = b yet?
SUB b
BRZ break // if yes, break out of loop
BRP a_gt_b // jump if a > b
// If a < b then b := b - a, binary digit is 0
LDA b
SUB a
STA b
BRA double
// If a > b then a := a - b, binary digit is 1
a_gt_b STA a
LDA index
ADD pwr2
STA index
// In either case, on to next power of 2
double LDA pwr2
ADD pwr2
STA pwr2
BRA loop
// Out of loop, add leading binary digit 1
break LDA index
ADD pwr2
STA index
// Output the result
LDA num
OTX 1 // non-standard: minimum width = 1, no new line
LDA asc_sl
OTC
LDA den
OTX 1
LDA asc_lt // write '<-' after fraction
OTC
LDA asc_hy
OTC
LDA index
OTX 11 // non-standard: minimum width = 1, add new line
exit HLT
// Constants
c0 DAT 0
c1 DAT 1
asc_sl DAT 47
asc_lt DAT 60
asc_hy DAT 45
// Variables
num DAT
den DAT
a DAT
b DAT
pwr2 DAT
index DAT
// end
</lang>
{{out}}
<pre>
9/4<-35
</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
| |||