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_add=(bn_mod_op bn_add)
\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 "add" bn_mod_add
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_add)
\-=(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 add = 55419354 sub = 65061600 mul = 50804329 = test_2 55419354 50804329 93583466