(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 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)

say "= test_1"

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

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

        \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


# Convert x to bn.
    is_bn x x;
    is_str x (bn_from_dec x);
    is_num x (bn_from_dec; num_str x);

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.


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


The script output is:

= test_1
n = 100000000
x = 741127760240477
y = 124589395178877
add = 55419354
sub = 65061600
mul = 50804329

= test_2