Comparators.fractran

# Comparators in FRACTRAN

## Greater Than

INPUT (n): 2^a * 3^b * 5^isGreater
OUTPUT:    5^isGreater

r2: a // first number
r3: b // second number
r5: isGreater // boolean; starts off at 1


### The Program

#### Pseudocode

while true {
    if (r2 >= 1 && r3 >= 1) {
        decrement a and b
    } else if (r3 >= 1 && r5 >= 1) {
        decrement b and isGreater
    } else if (r2 >= 1) {
        decrement a
    } else if (r3 >= 1) {
        decrement b
    } else {
        break
    }
}

#### FRACTRAN

(
    1 / 6,
    1 / 15,
    1 / 2,
    1 / 3
)


### Analysis

This is essentially a subtraction algorithm with a state to hold the greater
than boolean. Once one of the values hits zero, we check to see if the remaining
value is the second value. If so, we flip the isGreater flag to false.


### Examples

#### Example 1

We will test that 5 > 2 is true. Our initial value (n) should be
2^5 * 3^2 * 5^1. Our result should be r5 == 1, which means true.

r2: 5
r3: 2
r5: 1
n: 2^5 * 3^2 * 5^1

Decrement both values until one reaches zero.
A: (2^5 * 3^2 * 5^1) * (1 / 2 * 3)
n: 2^4 * 3^1 * 5^1

Decrement both values until one reaches zero.
A: (2^4 * 3^1 * 5^1) * (1 / 2 * 3)
n: 2^3 * 5^1

Zero out remaining values.
C: (2^3 * 5^1) * (1 / 2)
n: 2^2 * 5^1

Zero out remaining values.
C: (2^2 * 5^1) * (1 / 2)
n: 2^1 * 5^1

Zero out remaining values.
C: (2^1 * 5^1) * (1 / 2)
n: 5^1

HALT

#### Example 2

We will test that 1 > 2 is true. Our initial value (n) should be
2^1 * 3^2 * 5^1. Our result should be r5 == 0, which means false.

r2: 1
r3: 2
r5: 1
n: 2^1 * 3^2 * 5^1

Decrement both values until one reaches zero.
A: (2^1 * 3^2 * 5^1) * (1 / 2 * 3)
n: 3^1 * 5^1

Remove isGreater flag
B: (3^1 * 5^1) * (1 / 15)
n: 1 or 5^0

HALT


## Less Than

INPUT (n): 2^a * 3^b * 5^isLess
OUTPUT:    5^isLess

r2: a // first number
r3: b // second number
r5: isLess // boolean; starts off at 1


### The Program

#### Pseudocode

while true {
    if (r2 >= 1 && r3 >= 1) {
        decrement a and b
    } else if (r2 >= 1 && r5 >= 1) {
        decrement b and isLess
    } else if (r2 >= 1) {
        decrement a
    } else if (r3 >= 1) {
        decrement b
    } else {
        break
    }
}

#### FRACTRAN

(
    1 / 6,
    1 / 10,
    1 / 2,
    1 / 3
)


### Analysis

This is the same as above, but we change which variable we test at the end, from
the first to the second.


### Examples

#### Example 1

We will test that 2 < 3 is true. Our initial value (n) should be
2^2 * 3^3 * 5^1. Our result should be r5 == 1, which means true.

r2: 2
r3: 3
r5: 1
n: 2^2 * 3^3 * 5^1

Decrement both values until one reaches zero.
A: (2^2 * 3^3 * 5^1) * (1 / 2 * 3)
n: 2^1 * 3^2 * 5^1

Decrement both values until one reaches zero.
A: (2^1 * 3^2 * 5^1) * (1 / 2 * 3)
n: 3^1 * 5^1

Zero out remaining values.
D: (3^1 * 5^1) * (1 / 3)
n: 5^1

HALT

#### Example 2

We will test that 3 < 2 is true. Our initial value (n) should be
2^3 * 3^2 * 5^1. Our result should be r5 == 0, which means false.

r2: 3
r3: 2
r5: 1
n: 2^3 * 3^2 * 5^1

Decrement both values until one reaches zero.
A: (2^3 * 3^2 * 5^1) * (1 / 2 * 3)
n: 2^2 * 3^1 * 5^1

Decrement both values until one reaches zero.
A: (2^2 * 3^1 * 5^1) * (1 / 2 * 3)
n: 2^1 * 5^1

Remove isLess flag
B: (2^1 * 5^1) * (1 / 10)
n: 1 or 5^0

HALT


## Equal To

INPUT (n): 2^a * 3^b + 5^isEqual
OUTPUT:    5^isEqual

r2: a // first number
r3: b // second number
r5: isEqual // boolean; starts off at 1


### The Program

#### Pseudocode

while true {
    if (r2 >= 1 && r3 >= 1) {
        decrement a and b
    } else if (r2 >= 1 && r5 >= 1) {
        decrement a and isEqual
    } else if (r3 >= 1 && r5 >= 1) {
        decrement b and isEqual
    } else if (r2 >= 1) {
        decrement a
    } else if (r3 >= 1) {
        decrement b
    } else {
        break;
    }
}

#### FRACTRAN

(
    1 / 6,
    1 / 10,
    1 / 15,
    1 / 2,
    1 / 3
)


### Analysis

This works the same as the previous function for "greater than", but checks both
variables to set the flag. If either variable holds a value, then the flag is
set to false.


### Example

#### Example 1

We will test that 3 == 2. Our initial value (n) should be 2^3 * 3^2 * 5^1. Our
result should be r5 == 0, or false.

r2: 3
r3: 2
r5: 1
n: 2^3 * 3^2 * 5^1

Decrement both values until one reaches zero.
A: (2^3 * 3^2 * 5^1) * (1 / 2^1 * 3^1)
n: 2^2 * 3^1 * 5^1

Decrement both values until one reaches zero.
A: (2^2 * 3^1 * 5^1) * (1 / 2^1 * 3^1)
n: 2^1 * 5^1

Remove isEqual flag
B: 2^1 * 5^1 * (1) / 2^1 * 5^1
n: 1

HALT

#### Example 2

We will test that 2 == 2. Our initial value (n) should be 2^2 * 3^2 * 5^1. Our
result should be r5 == 1, or true.

r2: 1
r3: 1
r5: 1
n: 2^1 * 3^1 * 5^1

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

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

HALT