(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