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