# Division in FRACTRAN

## The Program

INPUT (n): 2^a * 3^b
OUTPUT:    5^a / b, 7^a % b

r2: Dividend
r3: Divisor
r5: Quotient
r7: Remainder
r11-r13: State Alpha One and Two // starts with Alpha One at 1
r17-r19: State Beta One and Two

### Pseudocode

From the [FRACTRAN Wikipedia](https://en.wikipedia.org/wiki/FRACTRAN)

while true {
    // STATE ALPHA - subtract divisor from dividend; increment quotient if
    // divisor is fully used
    if (dividend >= 1 && divisor >= 1 && State Alpha One >= 1) {
        decrement dividend, divisor, and State Alpha One
        increment remainder and State Alpha Two++
    } else if (State Alpha Two >= 1) {
        decrement State Alpha Two
        increment State Alpha One
    // Once dividend or divisor hits 0...
    } else if (divisor >= 1 && State Alpha One >= 1) {
        decrement divisor and State Alpha One
    } else if (State Alpha One >= 1) {
        decrement State Alpha One
        increment quotient and State Beta One
    // STATE BETA - Replenish divisor from remainder
    } else if (remainder >= 1 && State Beta One >= 1) {
        decrement remainder and State Beta One
        increment divisor and State Beta Two
    } else if (State Beta Two >= 1) {
        decrement State Beta Two
        increment State Beta One
    // if remainder is zero...
    } else if (State Beta One >= 1) {
        decrement State Beta One
        increment State Alpha One
    // Deplete divisor until empty
    } else if (divisor >= 1) {
        decrement divisor
    }
}

### FRACTRAN

(
    7 * 13 / 2 * 3 * 11,
    11 / 13,
    1 / 3 * 11,
    5 * 17 / 11,
    3 * 19 / 7 * 17,
    17 / 19,
    11 / 17,
    1 / 3
)


## Analysis

There are two states: State Alpha and State Beta.

- State Alpha: the default starting state, composed of fractions A, B, C, and D.
    This is where we perform our "subtractions" on the dividend.
- State Beta: composed of fractions E, F, and G. This state is where we
    reset our values for the subtraction.

Fraction H, the last fraction, is for clean up, zeroing out our remaining vars.


## Examples

### Example 1

We will test is that 5 / 2 == 2 remainder 1. Our initial value (n) should be
2^5 * 3^2 * 11^1. Our result should be 5^2 * 7^1.

r2: 5
r3: 2
r11: 1
n: 2^5 * 3^2 * 11^1

Begin Program:

State Alpha: Subtract divisor from dividend
A: (2^5 * 3^2 * 11^1) * (7 * 13 / 2 * 3 * 11)
n: 2^4 * 3^1 * 7^1 * 13^1

B: (2^4 * 3^1 * 7^1 * 13^1) * (11 / 13)
n: 2^4 * 3^1 * 7^1 * 11^1

A: (2^4 * 3^1 * 7^1 * 11^1) * (7 * 13 / 2 * 3 * 11)
n: 2^3 * 7^2 * 13^1

B: (2^3 * 7^2 * 13^1) * (11 / 13)
n: 2^3 * 7^2 * 11^1

Increment quotient, exit State Alpha
D: (2^3 * 7^2 * 11^1) * (5 * 17 / 11)
n: 2^3 * 5^1 * 7^2 * 17^1

State Beta: Reset divisor and remainder
E: (2^3 * 5^1 * 7^2 * 17^1) * (3 * 19 / 7 * 17)
n: 2^3 * 3^1 * 5^1 * 7^1 * 19^1

F: (2^3 * 3^1 * 5^1 * 7^1 * 19^1) * (17 / 19)
n: 2^3 * 3^1 * 5^1 * 7^1 * 17^1

E: (2^3 * 3^1 * 5^1 * 7^1 * 17^1) * (3 * 19 / 7 * 17)
n: 2^3 * 3^2 * 5^1 * 19^1

F: (2^3 * 3^2 * 5^1 * 19^1) * (17 / 19)
n: 2^3 * 3^2 * 5^1 * 17^1

Exit State Beta
G: (2^3 * 3^2 * 5^1 * 17^1) * (11 / 17)
n: 2^3 * 3^2 * 5^1 * 11^1

State Alpha: Subtract divisor from dividend
A: (2^3 * 3^2 * 5^1 * 11^1) * (7 * 13 / 2 * 3 * 11)
n: 2^2 * 3^1 * 5^1 * 7^1 * 13^1

B: (2^2 * 3^1 * 5^1 * 7^1 * 13^1) * (11 / 13)
n: 2^2 * 3^1 * 5^1 * 7^1 * 11^1

A: (2^2 * 3^1 * 5^1 * 7^1 * 11^1) * (7 * 13 / 2 * 3 * 11)
n: 2^1 * 5^1 * 7^2 * 13^1

B: (2^1 * 5^1 * 7^2 * 13^1) * (11 / 13)
n: 2^1 * 5^1 * 7^2 * 11^1

Increment quotient, exit State Alpha
D: (2^1 * 5^1 * 7^2 * 11^1) * (5 * 17 / 11)
n: 2^1 * 5^2 * 7^2 * 17^1

State Beta: Reset divisor and remainder
E: (2^1 * 5^2 * 7^2 * 17^1) * (3 * 19 / 7 * 17)
n: 2^1 * 3^1 * 5^2 * 7^1 * 19^1

F: (2^1 * 3^1 * 5^2 * 7^1 * 19^1) * (17 / 19)
n: 2^1 * 3^1 * 5^2 * 7^1 * 17^1

E: (2^1 * 3^1 * 5^2 * 7^1 * 17^1) * (3 * 19 / 7 * 17)
n: 2^1 * 3^2 * 5^2 * 19^1

F: (2^1 * 3^2 * 5^2 * 19^1) * (17 / 19)
n: 2^1 * 3^2 * 5^2 * 17^1

Exit State Beta
G: (2^1 * 3^2 * 5^2 * 17^1) * (11 / 17)
n: 2^1 * 3^2 * 5^2 * 11^1

State Alpha: Subtract divisor from dividend
A: (2^1 * 3^2 * 5^2 * 11^1) * (7 * 13 / 2 * 3 * 11)
n: 3^1 * 5^2 * 7^1 * 13^1

B: (3^1 * 5^2 * 7^1 * 13^1) * (11 / 13)
n: 3^1 * 5^2 * 7^1 * 11^1

Dividend is empty
C: (3^1 * 5^2 * 7^1 * 11^1) * (1 / 3 * 11)
n: 5^2 * 7^1

HALT