From: Aaron Taylor <ataylor@subgeniuskitty.com>
Date: Thu, 12 Dec 2019 01:03:23 +0000 (-0800)
Subject: Added `gcd` function to stdlib.
X-Git-Url: http://git.subgeniuskitty.com/vvhitespace/.git/commitdiff_plain/37372ed0cccf20298fdefc4c3d1153eb58407e45

Added `gcd` function to stdlib.
---

diff --git a/stdlib/README.md b/stdlib/README.md
index 99f3e69..8427f53 100644
--- a/stdlib/README.md
+++ b/stdlib/README.md
@@ -42,6 +42,7 @@ header comment for each function to learn the call and return stack.
          010xxx - math functions
           10000 ----- random                        (math.pvvs)
           10001 ----- absolute value                (math.pvvs)
+          10010 ----- greatest common divisor       (math.pvvs)
          011xxx - heap functions
           11000 ----- memset                        (heap.pvvs)
           11001 ----- memcpy                        (heap.pvvs)
diff --git a/stdlib/math.pvvs b/stdlib/math.pvvs
index 3876c6e..742522e 100644
--- a/stdlib/math.pvvs
+++ b/stdlib/math.pvvs
@@ -72,4 +72,64 @@ SNN                     | DROP
 SSSSN                   | PUSH 0
 NTN                     | RTS
 
+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
+@ Name:
+@   gcd (10010)
+@ Description:
+@   Returns greatest common divisor of X and Y.
+@ Call Stack:
+@   Y
+@   X  <-- TOS
+@ Return Stack:
+@   gcd(X,Y)  <-- TOS
+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
+#include <stack.pvvs>
+NSSVTSSTSN              | Mark: 10010 (gcd)
+
+@ Since 1 > -1, transform problem into gcd(abs(X),abs(Y)).
+SNT                     | SWAP
+NSTTSSSTN               | JSR > 10001 (abs)
+SNT                     | SWAP
+NSTTSSSTN               | JSR > 10001 (abs)
+
+@ Verify neither operand is zero.
+SNT                     | SWAP
+SNS                     | DUP
+NTSSSSTSSTSSSSSSSSSN    | BRZ > 00010010 00000000 (gcd:zero input)
+SNT                     | SWAP
+SNS                     | DUP
+NTSSSSTSSTSSSSSSSSSN    | BRZ > 00010010 00000000 (gcd:zero input)
+
+@ Verify X != Y and sort X,Y so the smaller is TOS.
+SNS                     | DUP
+SSSTTN                  | PUSH 3
+NSTTTSSN                | JSR > 1100 (deepdup)
+SNT                     | SWAP
+TSST                    | SUBTRACT
+@ TOS> Y-X, X, Y
+NTTSSSTSSTSSSSSSSSTN    | BMI > 00010010 00000001 (gcd:swap inputs)
+NSNSSSTSSTSSSSSSSTSN    | JMP > 00010010 00000010 (gcd:main loop)
+NSSVSSSTSSTSSSSSSSSTN   | MARK: 00010010 00000001 (gcd:swap inputs)
+SNT                     | SWAP
+
+@ Main gcd loop.
+@ Euclidean algorithm.
+NSSVSSSTSSTSSSSSSSTSN   | MARK: 00010010 00000010 (gcd:main loop)
+SNS                     | DUP
+SSSTTN                  | PUSH 3
+NSTTSTSN                | JSR > 1010 (stackrotate)
+TSTT                    | MODULO
+SNS                     | DUP
+NTSSSSTSSTSSSSSSSTTN    | BRZ > 00010010 00000011 (gcd:loop termination)
+NSNSSSTSSTSSSSSSSTSN    | JMP > 00010010 00000010 (gcd:main loop)
+NSSVSSSTSSTSSSSSSSTTN   | MARK: 00010010 00000011 (gcd:loop termination)
+SNN                     | DROP
+NTN                     | RTS
+
+@ At least one operand was zero.
+@ Since we define gcd(a,0) = a, return the other operand.
+NSSVSSSTSSTSSSSSSSSSN   | MARK: 00010010 00000000 (gcd:zero input)
+SNN                     | DROP
+NTN                     | RTS
+
 #endif
diff --git a/stdlib_tests/5003_gcd.pvvs b/stdlib_tests/5003_gcd.pvvs
new file mode 100644
index 0000000..84be3cf
--- /dev/null
+++ b/stdlib_tests/5003_gcd.pvvs
@@ -0,0 +1,41 @@
+@ Verify gcd(0,0) = 0
+SSSSN           | PUSH 0
+SSSSN           | PUSH 0
+NSTTSSTSN       | JSR > 10010 (math:gcd)
+NSTTTTTSTN      | JSR > 111101 (debug:printsignednumber)
+
+@ Verify gcd(4,0) = 4
+SSSSN           | PUSH 0
+SSSTSSN         | PUSH 4
+NSTTSSTSN       | JSR > 10010 (math:gcd)
+NSTTTTTSTN      | JSR > 111101 (debug:printsignednumber)
+
+@ Verify gcd(0,4) = 4
+SSSTSSN         | PUSH 4
+SSSSN           | PUSH 0
+NSTTSSTSN       | JSR > 10010 (math:gcd)
+NSTTTTTSTN      | JSR > 111101 (debug:printsignednumber)
+
+@ Verify gcd(6,9) = 3
+SSSTSSTN        | PUSH 9
+SSSTTSN         | PUSH 6
+NSTTSSTSN       | JSR > 10010 (math:gcd)
+NSTTTTTSTN      | JSR > 111101 (debug:printsignednumber)
+
+@ Verify gcd(-6,9) = 3 
+SSSTSSTN        | PUSH 9
+SSTTTSN         | PUSH -6
+NSTTSSTSN       | JSR > 10010 (math:gcd)
+NSTTTTTSTN      | JSR > 111101 (debug:printsignednumber)
+
+@ Verify gcd(-9,6) = 3
+SSTTSSTN        | PUSH -9
+SSSTTSN         | PUSH 6
+NSTTSSTSN       | JSR > 10010 (math:gcd)
+NSTTTTTSTN      | JSR > 111101 (debug:printsignednumber)
+
+
+NNN             | DIE
+
+#include <math.pvvs>
+#include <debug.pvvs>
diff --git a/stdlib_tests/vv_test.py b/stdlib_tests/vv_test.py
index bd6aeca..b4f0cd0 100755
--- a/stdlib_tests/vv_test.py
+++ b/stdlib_tests/vv_test.py
@@ -39,6 +39,7 @@ tests = [
         ['4001_strlen', '', '+11'],
         ['5001_abs', '', '+1+1+0+0'],
         ['5002_random', '', ''],
+        ['5003_gcd', '', '+0+4+4+3+3+3'],
         ['6001_printstackstring', '', 'test'],
         ['6002_printheapstring', '', 'test'],
         ['6003_printnumbersign', '', '+-'],