@ Name:
@ random (10000)
@ Description:
-@ Returns a kinda-random number.
-@ Before using for the first time, seed heap[0] with a value.
+@ Returns a pseudo-random number.
+@ Before using for the first time, seed heap[0] with a non-zero value.
+@ This PRNG was taken from: https://en.wikipedia.org/wiki/Xorshift
@ Call Stack:
@ empty
@ Return Stack:
@ random number <-- TOS
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
+#include <logic.pvvs>
NSSVTSSSSN | Mark: 10000 (random)
-@ Generate the next seed value
+@ Fetch seed from heap[0].
SSSSN | PUSH 0 (ptr)
TTT | LOAD
-SSSTSSSSSTTTSSSTTSSTSSTTTSSTTSTTSTN | PUSH 1103515245
-TSSN | MULTIPLY
-SSSTTSSSSSSTTTSSTN | PUSH 12345
-TSSS | ADD
-@ Store the next seed value but keep a copy on the stack.
+@ Set TOS ^= TOS << 13
+SNS | DUP
+SSSTTSTN | PUSH +13
+NSTTSTTSTN | JSR > 101101 (lshift)
+NSTTSTSTTN | JSR > 101011 (xor)
+
+@ Set TOS ^= TOS >> 7
+SNS | DUP
+SSSTTTN | PUSH +7
+NSTTSTTSSN | JSR > 101100 (rshift)
+NSTTSTSTTN | JSR > 101011 (xor)
+
+@ Set TOS ^= TOS << 17
+SNS | DUP
+SSSTSSSTN | PUSH +17
+NSTTSTTSTN | JSR > 101101 (lshift)
+NSTTSTSTTN | JSR > 101011 (xor)
+
+@ Store a copy of the new seed at heap[0] and return.
SNS | DUP
SSSSN | PUSH 0 (ptr)
SNT | SWAP
TTS | STORE
-
-@ Calculate the random number and return.
-SSSTSSSSSSSSSSSSSSSSN | PUSH 65536
-TSTS | DIVIDE
-SSSTSSSSSSSSSSSSSSSN | PUSH 32768
-TSTT | MODULO
NTN | RTS
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ abs(signed number) <-- TOS
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
NSSVTSSSTN | Mark: 10001 (absolute value)
+
+@ Catch -(2^63) as a special case since its absolute value will overflow
+@ a twos-complement 64-bit word. Return zero as though the absolute value
+@ overflowed to the bottom of the non-negative integers rather than
+@ overflowing back to the most negative integer.
+SNS | DUP
+SSTTSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSN | -(2^63)
+TSST | SUBTRACT
+NTSSSSTSSSTSSSSSSTSN | BRZ > 00010001 00000010
+
+@ Handle all the other numbers.
SNS | DUP
NTTSSSTSSSTSSSSSSSSN | BMI > 00010001 00000000
NSNSSSTSSSTSSSSSSSTN | JMP > 00010001 00000001
NSSVSSSTSSSTSSSSSSSTN | Mark: 00010001 00000001
NTN | RTS
+@ Special case: Push 0 and return.
+NSSVSSSTSSSTSSSSSSTSN | Mark: 00010001 00000010
+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