User:Thebigh/mysandbox: Difference between revisions
(more) |
m (tweak) |
||
| (22 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
Some FRACTRAN programs in case we ever have a category for it |
|||
The '''Minkowski question-mark function''' converts the continued fraction representation {{math|[a<sub>0</sub>; a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>, ...]}} of a number into a binary decimal representation in which the integer part {{math|a<sub>0</sub>}} is unchanged and the {{math|a<sub>1</sub>, a<sub>2</sub>, ...}} become alternating runs of binary zeroes and ones of those lengths. The decimal point takes the place of the first zero. |
|||
==A+B== |
|||
Thus, {{math|?}}(31/7) = 71/16 because 31/17 has the continued fraction representation {{math|[4;2,3]}} giving the binary expansion {{math|4 + 0.0111<sub>2</sub>}}. |
|||
Input a number of the form 2^a 3^b |
|||
Among its interesting properties is that it maps roots of quadratic equations, which have repeating continued fractions, to rational numbers, which have repeating binary digits. |
|||
<lang fractran> |
|||
2/3 |
|||
</lang> |
|||
The output is 2^(a+b) |
|||
==Empty program== |
|||
The question-mark function is continuous and monotonically increasing, so it has an inverse. |
|||
A list of no fractions does nothing, then immediately stops. |
|||
* Produce a function for {{math|?(x)}}. Be careful: rational numbers have two possible continued fraction representations- choose the one that will give a binary expansion ending with a 1. |
|||
<lang fractran></lang> |
|||
* Produce the inverse function {{math|?<sup>-1</sup>(x)}} |
|||
* Verify that {{math|?(φ)}} = 5/3, where {{math|φ}} is the Greek golden ratio. |
|||
* Verify that {{math|?<sup>-1</sup>(-5/9)}} = (√13 - 7)/6 |
|||
* Verify that the two functions are inverses of each other by showing that {{math|?<sup>-1</sup>(?(x))}}={{math|x}} and {{math|?(?<sup>-1</sup>(y))}}={{math|y}} for {{math|x, y}} of your choice |
|||
==Integer Sequence== |
|||
Don't worry about precision error in the last few digits. |
|||
Given the number 1 as input the following program will, as its (3n-2)th step, produce the number 2^n. |
|||
<lang fractran> 2/3, 9/2, 2/1</lang> |
|||
==Logical operations== |
|||
==header|FreeBASIC== |
|||
It's not so hard to code up all sixteen possible two-input logic gates, so here they are. The input is 2^a 3^b where a,b are zero or one and the output is 5^1 for true and 5^0 for false. Gates that return true when all their inputs are false additionally require the flag 11 to be set as input (ie 2^a*3^b*11)- any FRACTRAN program with the number 1 as input either stops without doing anything or loops forever. |
|||
<lang fractran> |
|||
<lang freebasic>#define MAXITER 151 |
|||
5/6, 1/2, 1/3 AND gate |
|||
5/6, 5/2, 5/3 OR gate |
|||
1/22, 5/11 NOT gate (uses 11 as a halt flag, result of 2^a*11 is 5^not(a)) |
|||
1/6, 5/2, 5/3 XOR gate |
|||
1/66, 5/22, 5/33, 5/11 NAND gate (needs 11 flag) |
|||
5/66, 1/22, 1/33, 5/11 NXOR gate (needs flag) |
|||
1/66, 1/22, 1/33, 5/11 NOR gate (needs flag) |
|||
so much for all the commonly encountered ones, but there's still another eight to go. Most are obscure and of limited utility. |
|||
#define MAXITER 151 |
|||
1/2, 1/3 ZERO gate, returns false regardless of its input |
|||
function minkowski( x as double ) as double |
|||
1/6, 5/2, 1/3 "A and not B", true only if A is true and B is false |
|||
if x>1 or x<0 then return int(x)+minkowski(x-int(x)) |
|||
5/2, 1/3 A , returns the state of A regardless of B |
|||
dim as ulongint p = int(x) |
|||
1/6, 1/2, 5/3 "B and not A", true only if B is true and A is false |
|||
1/2, 5/3 B , returns the state of B regardless of A |
|||
dim as double d = 1, y = p |
|||
1/66, 1/33, 5/11 "A or not B" (needs flag) |
|||
while true |
|||
1/66, 1/22, 5/11 "B or not A" (needs flag) |
|||
5/66, 5/22, 5/33, 5/11 ONE gate, returns true regardless of its input, needs flag |
|||
if y + d = y then exit while |
|||
m = p + r |
|||
if m < 0 or p < 0 then exit while |
|||
n = q + s |
|||
if n < 0 then exit while |
|||
if x < cast(double,m) / n then |
|||
r = m |
|||
s = n |
|||
else |
|||
y = y + d |
|||
p = m |
|||
q = n |
|||
end if |
|||
wend |
|||
return y + d |
|||
end function |
|||
NOT A and NOT B are omitted because the one-input NOT gate is already up there. |
|||
function minkowski_inv( byval x as double ) as double |
|||
</lang> |
|||
if x>1 or x<0 then return int(x)+minkowski_inv(x-int(x)) |
|||
if x=1 or x=0 then return x |
|||
redim as uinteger contfrac(0 to 0) |
|||
dim as uinteger curr=0, count=1, i = 0 |
|||
do |
|||
x *= 2 |
|||
if curr = 0 then |
|||
if x<1 then |
|||
count += 1 |
|||
else |
|||
i += 1 |
|||
redim preserve contfrac(0 to i) |
|||
contfrac(i-1)=count |
|||
count = 1 |
|||
curr = 1 |
|||
x=x-1 |
|||
endif |
|||
else |
|||
if x>1 then |
|||
count += 1 |
|||
x=x-1 |
|||
else |
|||
i += 1 |
|||
redim preserve contfrac(0 to i) |
|||
contfrac(i-1)=count |
|||
count = 1 |
|||
curr = 0 |
|||
endif |
|||
end if |
|||
if x = int(x) then |
|||
contfrac(i)=count |
|||
exit do |
|||
end if |
|||
loop until i = MAXITER |
|||
dim as double ret = 1.0/contfrac(i) |
|||
for j as integer = i-1 to 0 step -1 |
|||
ret = contfrac(j) + 1.0/ret |
|||
next j |
|||
return 1./ret |
|||
end function |
|||
==Sort three variables== |
|||
print minkowski( 0.5*(1+sqr(5)) ), 5./3 |
|||
FRACTRAN's only data type is positive integers. Suppose (a,b,c) are the integers to be sorted. Give the following as input: |
|||
print minkowski_inv( -5./9 ), (sqr(13)-7)/6 |
|||
2^a 3^b 5^c |
|||
print minkowski(minkowski_inv(0.718281828)), minkowski_inv(minkowski(0.1213141516171819)) |
|||
<lang fractran> |
|||
1001/30, 143/6, 143/10, 143/15, 13/2, 13/3, 13/5 |
|||
</lang> |
</lang> |
||
Returns 7^A 11^B 13^C where (A,B,C) are (a,b,c) in ascending order. |
|||
Latest revision as of 11:27, 28 November 2021
Some FRACTRAN programs in case we ever have a category for it
A+B
Input a number of the form 2^a 3^b <lang fractran> 2/3 </lang> The output is 2^(a+b)
Empty program
A list of no fractions does nothing, then immediately stops. <lang fractran></lang>
Integer Sequence
Given the number 1 as input the following program will, as its (3n-2)th step, produce the number 2^n. <lang fractran> 2/3, 9/2, 2/1</lang>
Logical operations
It's not so hard to code up all sixteen possible two-input logic gates, so here they are. The input is 2^a 3^b where a,b are zero or one and the output is 5^1 for true and 5^0 for false. Gates that return true when all their inputs are false additionally require the flag 11 to be set as input (ie 2^a*3^b*11)- any FRACTRAN program with the number 1 as input either stops without doing anything or loops forever.
<lang fractran> 5/6, 1/2, 1/3 AND gate 5/6, 5/2, 5/3 OR gate 1/22, 5/11 NOT gate (uses 11 as a halt flag, result of 2^a*11 is 5^not(a)) 1/6, 5/2, 5/3 XOR gate 1/66, 5/22, 5/33, 5/11 NAND gate (needs 11 flag) 5/66, 1/22, 1/33, 5/11 NXOR gate (needs flag) 1/66, 1/22, 1/33, 5/11 NOR gate (needs flag)
so much for all the commonly encountered ones, but there's still another eight to go. Most are obscure and of limited utility.
1/2, 1/3 ZERO gate, returns false regardless of its input 1/6, 5/2, 1/3 "A and not B", true only if A is true and B is false 5/2, 1/3 A , returns the state of A regardless of B 1/6, 1/2, 5/3 "B and not A", true only if B is true and A is false 1/2, 5/3 B , returns the state of B regardless of A 1/66, 1/33, 5/11 "A or not B" (needs flag) 1/66, 1/22, 5/11 "B or not A" (needs flag) 5/66, 5/22, 5/33, 5/11 ONE gate, returns true regardless of its input, needs flag
NOT A and NOT B are omitted because the one-input NOT gate is already up there. </lang>
Sort three variables
FRACTRAN's only data type is positive integers. Suppose (a,b,c) are the integers to be sorted. Give the following as input: 2^a 3^b 5^c <lang fractran> 1001/30, 143/6, 143/10, 143/15, 13/2, 13/3, 13/5 </lang> Returns 7^A 11^B 13^C where (A,B,C) are (a,b,c) in ascending order.