Fractran machine!

[François Pinard]

Hi, people.  Here is a Fractran machine, with a demo program.  Try it to
discover what it does.  You might prefer to read the code and guess? :-)


# Versions: Pascal in 1985, C++ in 1989, Python in 2000.

"""\
Interpreter for the Fractran machine.

The Fractran machine (probably invented by John Conway) holds an accumulator,
which is an integer of unlimited length.  It also holds a finite program
expressed as a list of rational numbers, or fractions.

Each computation cycle works as follow.  Find the first fraction for which
the denominator exactly divides the accumulator.  If there is no such
fraction, the machine halts.  Multiply the accumulator by this fraction.
Also, whenever the result is an exact power of two, output the exponent.
"""

def main():
    fractran = Fractran()
    fractran.load_program((17, 91),
                          (78, 85),
                          (19, 51),
                          (23, 38),
                          (29, 33),
                          (77, 29),
                          (95, 23),
                          (77, 19),
                          (1, 17),
                          (11, 13),
                          (13, 11),
                          (15, 14),
                          (15, 2),
                          (55, 1))
    fractran.load_accumulator(2)
    try:
        fractran.run()
    finally:
        fractran.status()

class Fractran:

    def load_program(self, *fractions):
        self.program = []
        for numerator, denominator in fractions:
            self.program.append((long(numerator), long(denominator)))

    def load_accumulator(self, accumulator):
        self.accumulator = long(accumulator)

    def run(self):
        count = self.step_count = 0
        accumulator = self.accumulator
        while 1:
            count = count + 1
            for numerator, denominator in self.program:
                quotient, remainder = divmod(accumulator, denominator)
                if remainder == 0:
                    accumulator = quotient * numerator
                    break
            if remainder != 0:
                break
            if accumulator & accumulator - 1 == 0:
                print ('Printing %d after %d steps'
                       % (length(accumulator)-1, count))
            self.step_count = count
            self.accumulator = accumulator

    def status(self):
        print 'Stopping after %d steps' % self.step_count
        print '  with accumulator =', self.accumulator

def length(number):
    count = 0
    while number > 256:
        count = count + 8
        number = number >> 8
    while number > 0:
        count = count + 1
        number = number >> 1
    return count

if __name__ == '__main__':
    main()

-- 
François Pinard   http://www.iro.umontreal.ca/~pinard