(Updated Mon 2022-08-15)

# Modular arithmetic

Here is an example of how you can define arithmetic functions which reduce their results by a given modulus. Note that these currently work by computing the entire result and then calling bn_mod to return only the remainder. I could make that more efficient by defining the functions directly in C, in a way that convolved the steps together and avoided computing the entire result as far as possible. I would do that by starting with the most straightforward C code, and then systematically refactoring that to minimize computation of the full result. Thus the final optimized code would be provably equivalent to the original.

The following is a script which runs two routines test_1 and test_2. The test_1 does a basic test of add, subtract, and multiply. The test_2 defines a little "field" of operations modulo 100000000, conveniently defining the symbols + - * to operate within that field.

# Test modulus operators.

\bn_mod_op=
(\op\n\x\y
bn_mod (op x y) n
)

\bn_mod_sub=(bn_mod_op bn_sub)
\bn_mod_mul=(bn_mod_op bn_mul)

\\test_1=
(
say "= test_1"
\try=
(\n\x\y

\n=(bn_from_dec n)
\x=(bn_from_dec x)
\y=(bn_from_dec y)

say ["n = "n]
say ["x = "x]
say ["y = "y]

\try_op=
(\type\op
\z=(op n x y)
say [type" = "z]
)

try_op "sub" bn_mod_sub
try_op "mul" bn_mod_mul
nl
)

try
"100000000"
"741127760240477"
"124589395178877"
)

\\test_2=
(
# Convert x to bn.
\to_bn=
(\x
is_bn x x;
is_str x (bn_from_dec x);
is_num x (bn_from_dec; num_str x);
void
)

say "= test_2"

# Make a operator system within a specific modulus field.
\n="100000000" # modulus

\n=(bn_from_dec n)

# Make a (mod n) operator which converts its two arguments as needed.
\op2=(\f\x\y f n (to_bn x) (to_bn y))

# Define the functions [+ - *] to operate modulo n.
\-=(op2 bn_mod_sub)
\*=(op2 bn_mod_mul)

# Now run a few cases.

\x="741127760240477"
\y="124589395178877"

say (+ x y)
say (* x y)
say (* (* x y) (+ x y))
)

test_1
test_2


The script output is:

= test_1
n = 100000000
x = 741127760240477
y = 124589395178877