This repository has been archived by the owner on Jul 24, 2022. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathDivision.fractran.txt
170 lines (127 loc) · 4.2 KB
/
Division.fractran.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
# 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