Calkin-Wilf sequence: Difference between revisions
Content added Content deleted
No edit summary |
(Added solution for Little Man Computer) |
||
Line 1,101: | Line 1,101: | ||
83116//51639 is the 123456789-th term of the sequence. |
83116//51639 is the 123456789-th term of the sequence. |
||
</pre> |
</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}}== |
=={{header|Mathematica}} / {{header|Wolfram Language}}== |