Added `gcd` function to stdlib.

[vvhitespace] / stdlib / math.pvvs

#ifndef VVS_STDLIB_MATH
#define VVS_STDLIB_MATH

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ Name:
@   random (10000)
@ Description:
@   Returns a kinda-random number.
@   Before using for the first time, seed heap[0] with a value.
@ Call Stack:
@   empty
@ Return Stack:
@   random number  <-- TOS
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
NSSVTSSSSN              | Mark: 10000 (random)

@ Generate the next seed value
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.
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

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ Name:
@   abs (10001)
@ Description:
@   Returns the absolute value of its argument
@ Call Stack:
@   signed number  <-- TOS
@ Return Stack:
@   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
NSSVSSSTSSSTSSSSSSSSN   | Mark: 00010001 00000000
SSTTN                   | PUSH -1
TSSN                    | MULTIPLY
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