;---------------------------------------------------------------------------- ; prime.src ; David Boozer ; 1 November 2007 (modified, add documentation, rearrange code) ;---------------------------------------------------------------------------- ; ; The structure of the tape is as follows: ; ; +-----+---+-----+---+-----+ ; | d | 0 | n | 0 | x | ; +-----+---+-----+---+-----+ ; ; Initially d is the input, n and x are zero. ; ; During the calculation d holds the potential divisor and x is used ; as a scratchpad. ; ; Return 11 for prime, 1 for composite ; ; Algorithm: ; ; 1. copy d, which contains the input, to n ; 2. copy n, which contains the input, to x ; 3. erase leftmost 1 of d ; 4. subtract d from x by marking d and removing 1's from rhs of x ; 5. repeat 4 until x=0 ; 6. check marking on d to see if d divides input, if not, goto 3 ; ; bugs: crashes for 0, misidentifies 1 as prime ;---------------------------------------------------------------------------- copy_input_to_n: 000 0 --> 000 0 R 000 1 --> 001 0 R 001 0 --> 002 0 R 001 1 --> 001 1 R 002 0 --> 003 1 L 002 1 --> 002 1 R 003 0 --> 004 0 L 003 1 --> 003 1 L 004 0 --> jmp 1 R > copy_n_to_x 004 1 --> 005 1 L 005 0 --> 000 1 R 005 1 --> 005 1 L ;---------------------------------------------------------------------------- copy_n_to_x: 000 0 --> 000 0 R 000 1 --> 001 0 R 001 0 --> 002 0 R 001 1 --> 001 1 R 002 0 --> 003 1 L 002 1 --> 002 1 R 003 0 --> 004 0 L 003 1 --> 003 1 L 004 0 --> jmp 1 L > initialize 004 1 --> 005 1 L 005 0 --> 000 1 R 005 1 --> 005 1 L ;---------------------------------------------------------------------------- initialize: 000 0 --> 001 0 L 000 1 --> 000 1 L 001 0 --> nop 001 1 --> 002 0 L 002 0 --> jmp 0 R > subtract_d_from_x 002 1 --> 002 1 L ;---------------------------------------------------------------------------- subtract_d_from_x: ; repeatedly subtract d from x until x is zero 000 0 --> 010 0 R 000 1 --> 001 0 R ; mark d 001 0 --> jmp 0 R > input_prime ; exit (d=0, so input is prime) 001 1 --> 002 1 R 002 0 --> 003 0 R 002 1 --> 002 1 R 003 0 --> 003 0 R 003 1 --> 004 1 R 004 0 --> 005 0 R 004 1 --> 004 1 R 005 0 --> 006 0 L 005 1 --> 005 1 R 006 0 --> jmp 0 L > check_if_d_divides_input ; x=0 006 1 --> 007 0 L 007 0 --> 008 0 L 007 1 --> 007 1 L 008 0 --> 009 0 L 008 1 --> 008 1 L 009 0 --> 000 1 L ; unmark d 009 1 --> 009 1 L 010 0 --> 011 0 L ; one subtraction of d has been completed 010 1 --> 010 1 R 011 0 --> nop 011 1 --> 003 0 R ;---------------------------------------------------------------------------- check_if_d_divides_input: ; x is now zero, check marking on d to see if d divides input 000 0 --> 001 0 L 000 1 --> 000 1 L 001 0 --> jmp 0 L > input_composite ; d divides input 001 1 --> 002 1 L 002 0 --> 003 1 R 002 1 --> 002 1 L 003 0 --> jmp 0 R > copy_n_to_x ; d does not divide input 003 1 --> 003 1 R ;---------------------------------------------------------------------------- input_composite: 000 0 --> 001 0 R 000 1 --> 000 0 L 001 0 --> 001 0 R 001 1 --> 002 0 R 002 0 --> hlt 1 R 002 1 --> 002 0 R ;---------------------------------------------------------------------------- input_prime: 000 0 --> 000 0 R 000 1 --> 001 0 R 001 0 --> 002 0 R 001 1 --> 001 0 R 002 0 --> 002 0 R 002 1 --> 003 0 R 003 0 --> 004 1 R 003 1 --> 003 0 R 004 0 --> hlt 1 R 004 1 --> nop