forked from algorithm-archivists/algorithm-archive
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy patheuclidian_algorithm.piet
146 lines (125 loc) · 4.53 KB
/
euclidian_algorithm.piet
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
This file describes the path that the Piet program takes in a more human readable form.
Two functions are implemented:
- GCD with subtraction
- GCD with the modulo operator
-------------------
SUBTRACTION
-------------------
Pseudo code:
function gcd(a, b)
while a ≠ b
if a > b
a := a − b;
else
b := b − a;
return a;
Piet code:
COMMAND STATE OF STACK
in(number) A // Take A as an input
duplicate AA // Start to take the absolute value of A
push 1 1AA
duplicate 11AA
subtract 0AA
greater 0/1A // 1 if A > 0, 0 if A <= 0
not 1/0A // 0 if A > 0, 1 if A <= 0
push 1 1 1/0 A
push 3 31 1/0 A
subtract -2 1/0 A
multiply -2/0 A
push 1 1 -2/0 A
add -1/1 A
multiply A // A should now be an absolute value
in(number) BA // Take B as an input
duplicate BBA // Start to take the absolute value of B
push 1 1BBA
duplicate 11BBA
subtract 0BBA
greater 0/1BA // 1 if B > 0, 0 if B <= 0
not 1/0BA // 0 if B > 0, 1 if B <= 0
push 1 1 1/0 BA
push 3 31 1/0 BA
subtract -2 1/0 BA
multiply -2/0 BA
push 1 1 -2/0 BA
add -1/1 BA
multiply BA // B should now be an absolute value
// Start of the main loop while a ≠ b
duplicate BBA
push 3 3BBA
push 2 23BBA
roll ABB
duplicate AABB
push 4 4AABB
push 1 14AABB
roll ABBA
subtract 0/x BA
not 1/0 BA // 1 if a = b and 0 if a ≠ b
not 0/1 BA // 1 if a ≠ b and 0 if a = b
pointer BA // If a ≠ b, the DP should change one clockwise, otherwise, go straight ahead.
// Go left if a ≠ b (DP changed one clockwise)
duplicate BBA
push 3 3BBA
push 2 23BBA
roll ABB
duplicate AABB
push 4 4AABB
push 1 14AABB
roll ABBA
push 2 2ABBA
push 1 12ABBA
roll BABA
greater 0/1 BA // A > B; 1 if true; 0 if false
pointer BA // If A > B, DP goes one clockwise, otherwise, DP stays the same.
// If A > B (DP has changed 1 clockwise)
duplicate BBA
push 3 3BBA
push 1 13BBA
roll BAB
subtract AB // A = A - B
push 2 2AB
push 1 12AB
roll BA
// Go back to start of loop
// If B > A (DP stayed the same)
push 2 2BA
push 1 12BA
roll AB
duplicate AAB
push 3 3AAB
push 1 13AAB
roll ABA
subtract BA // B = B - A
// Go back to start of loop
// Go down if a = b (end of while loop)
pop A
out(number) - // Print out A when done.
---------------------------------------------------------------------------
-------------------
MODULO
-------------------
Pseudo code:
function gcd(a, b)
while b ≠ 0
t := b;
b := a mod b;
a := t;
return a;
Piet code:
COMMAND STATE OF STACK
in(number) A
in(number) BA
// Start of loop
duplicate BBA
not 0/1 BA
not 1/0 BA
pointer BA
// Go down if b ≠ 0
duplicate TBA
push 3 3TBA
push 1 13TBA
roll BAT
mod BA // b = a mod b; a = t
// Go back to the start of the loop
// Go right if b = 0
pop A
out(number) - // Print out A when done.