* FRACTRAN interpreter written by Viktors Berstis
* FRACTRAN - one of the most compact programming languages. A John Conway discovery.
* A FRACTRAN program is simply a list of rational fractions
* The Fractran computer tries multiplying the accumulator by the
* fractions in the list until one gets an integer result.
* Then the process repeats. The accumulator starts with 2 in it.
* The computer is extremely inefficient and needs to handle very large integers.
* The demo program here computes a sequence of all prime numbers.
* The answers occur when the accumulator is a power of 2, and the exponent is
* the prime number found. You will be lucky to get past 5 unless you implement
* long integer arithmetic with strings.
* A FRACTRAN program (not shown), about three times larger, can implement a
* universal turing machine.
* Hint for those trying to figure out how this works:
* Look at the prime factorization of all of the numbers involved
Num = ARRAY('14') ; Den = ARRAY('14')
* Fractran program to calculate all prime numbers:
* Numerators ; Denominators
Num< 1> = 17 ; Den< 1> = 91
Num< 2> = 78 ; Den< 2> = 85
Num< 3> = 19 ; Den< 3> = 51
Num< 4> = 23 ; Den< 4> = 38
Num< 5> = 29 ; Den< 5> = 33
Num< 6> = 77 ; Den< 6> = 29
Num< 7> = 95 ; Den< 7> = 23
Num< 8> = 77 ; Den< 8> = 19
Num< 9> = 1 ; Den< 9> = 17
Num<10> = 11 ; Den<10> = 13
Num<11> = 13 ; Den<11> = 11
Num<12> = 15 ; Den<12> = 2
Num<13> = 1 ; Den<13> = 7
Num<14> = 55 ; Den<14> = 1
* Starting value for the accumulator:
Acc = 2
* The above is a 14 fraction program which computes all of the prime numbers
* When the accumulater (Acc) is a power of two, the exponent is another prime
&ERRLIMIT = 1
LOOP J = 1
TEST s = Num * Acc :F(OVERFLOW)
t = Den
J = NE(REMDR(s,t)) J + 1 :S(TEST)
Acc = s / t
* OUTPUT = Acc DIFFER("uncomment to see intermediate computations")
L2 = LOG2(Acc)
OUTPUT = EQ(L2,CONVERT(L2,"INTEGER")) Acc ' = Accumulator, prime = ' L2 :S(LOOP)
:(LOOP)
OVERFLOW OUTPUT = 'Attempt overflow accumulator calculating ' Num ' * ' Acc
END