* 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