++egcd
Extended Euclidean algorithm
Produces d, the
greatest common divisor
of a and b. Also produces u and v such that au + bv = GCD(a, b).
Accepts
a is an atom.
b is an atom.
Produces
d, the greatest common divisor, is an atom.
u, the coefficient of a, is a signed integer.
v, the coefficient of b, is a signed integer.
Source
++ egcd
|= [a=@ b=@]
=+ si
=+ [c=(sun a) d=(sun b)]
=+ [u=[c=(sun 1) d=--0] v=[c=--0 d=(sun 1)]]
|- ^- [d=@ u=@s v=@s]
?: =(--0 c)
[(abs d) d.u d.v]
=+ q=(fra d c)
%= $
c (dif d (pro q c))
d c
u [(dif d.u (pro q c.u)) c.u]
v [(dif d.v (pro q c.v)) c.v]
==
Examples
> (egcd 11 2)
[d=1 u=--1 v=-5]++fo
Modulo prime
Container core for modular arithmetic functions.
Source
++ fo
^?
|_ a=@
++dif:fo
Subtraction
Produces the difference between atoms b and c, with a as the modular base.
Accepts
a is an atom.
b is an atom.
c is an atom.
Produces
An atom.
Source
++ dif
|= [b=@ c=@]
(sit (sub (add a b) (sit c)))
Examples
> (~(dif fo 6) 1 2)
5
> (~(dif fo 21) 11 45)
8++exp:fo
Exponent
Produces the power of c raised to the b, with a as the modular base.
Accepts
a is an atom.
b is an atom.
c is an atom.
Produces
An atom.
Source
++ exp
|= [b=@ c=@]
?: =(0 b)
1
=+ d=$(b (rsh 0 1 b))
=+ e=(pro d d)
?:(=(0 (end 0 1 b)) e (pro c e))
Examples
> (~(exp fo 5) 8 2)
1
> (~(exp fo 95) 8 2)
66
> (~(exp fo 195) 8 2)
61
> (~(exp fo 995) 8 2)
256++fra:fo
Divide
Produces the quotient of b divided by c, with a as the modular base.
Accepts
a is an atom.
b is an atom.
c is an atom.
Produces
An atom.
Accepts
a is an atom.
b is an atom.
Source
++ fra
|= [b=@ c=@]
(pro b (inv c))
Examples
> (~(fra fo 2) 8 2)
0
> (~(fra fo 3) 8 2)
1
> (~(fra fo 4) 8 2)
0
> (~(fra fo 5) 8 2)
4++inv:fo
Inverse
Produces an atom by taking the signed modulus of a with the coefficient u;
u is produced by taking the ++egcd of a and b.
Accepts
a is an atom.
b is an atom.
Produces
An atom.
Source
++ inv
|= b=@
=+ c=(dul:si u:(egcd b a) a)
c
Examples
> (~(inv fo 11) 2)
6
> (~(inv fo 71) 255)
22
> (~(inv fo 79) 255)
22
> (~(inv fo 78) 255)
67
> (~(inv fo 70) 255)
67++pro:fo
Multiplication
Produces the multiplication of b and c modulo a.
Accepts
a is an atom.
b is an atom.
c is an atom.
Produces
An atom.
Source
++ pro
|= [b=@ c=@]
(sit (mul b c))
Examples
> (~(pro fo 3) 11 4)
2
> (mod 44 3)
2++sit:fo
Modulus
Produces the remainder of b modulo a.
Accepts
a is an atom.
b is an atom.
Produces
An atom.
Source
++ sit
|= b=@
(mod b a)
Examples
> (~(sit fo 3) 14)
2++sum:fo
Modular sum
Produces the remainder of (b + c) mod a.
Accepts
a is an atom.
b is an atom.
c is an atom.
Produces
An atom.
Source
++ sum
|= [b=@ c=@]
(sit (add b c))
--
Examples
> (~(sum fo 3) 14 3)
2
> (mod 17 3)
2++si
Signed integer
Container core for signed integer functions.
Source
++ si
^?
|%
Discussion
The signed-integer type is represented by the @s aura. Positive integers are
prepended with a --, and negative integers are prepended with a -. For
example, --1 represents positive one, and -1 represents negative one.
Zig zag encoding is used to convert atoms to signed integers. Positive signed integers correspond to even atoms of twice their absolute value, and negative signed integers correspond to odd atoms of twice their absolute value minus one. For example:
> `@`--4
8
> `@s`8
--4
> `@`-4
7
> `@s`7
-4++abs:si
Absolute value
Produces the absolute value of signed integer a.
Accepts
a is a signed integer.
Produces
An atom.
Source
++ abs |=(a=@s (add (end 0 1 a) (rsh 0 1 a)))
Examples
> (abs:si -11)
11
> (abs:si --520)
520++dif:si
Subtraction
Produces the difference of a minus b.
Accepts
a is a signed integer.
b is a signed integer.
Produces
A signed integer.
Source
++ dif |= [a=@s b=@s]
(sum a (new !(syn b) (abs b)))
Examples
> (dif:si --3 -2)
--5
> (dif:si -3 --2)
-5++dul:si
Modulus
Produces the remainder of b modulo a.
Examples
a is a signed integer.
b is an atom.
Produces
An atom.
Source
++ dul |= [a=@s b=@]
=+(c=(old a) ?:(-.c (mod +.c b) (sub b +.c)))
Examples
> `@s`(dul:si -1 --5)
-5
> `@`--5
10
> `@s`(dul:si -1 10)
-5
> `@s`(dul:si -11 -61)
--55++fra:si
Divide
Produces the quotient of b divided by c.
Accepts
a is a signed integer.
b is a signed integer.
Produces
A signed atom.
Source
++ fra |= [a=@s b=@s]
(new =(0 (mix (syn a) (syn b))) (div (abs a) (abs b)))
Examples
> (fra:si -1 -1)
--1
> (fra:si -11 --2)
-5
> (fra:si -0 -1)
--0++new:si
Atom to @s
Produces a signed integer from an atom b. The product's sign is determined
by the value of flag a: & will result in a prepending --, and | will
result in a prepending -.
Accepts
a is a flag.
b is an atom.
Produces
A signed integer.
Source
++ new |= [a=? b=@]
`@s`?:(a (mul 2 b) ?:(=(0 b) 0 +((mul 2 (dec b)))))
Examples
> (new:si | 2)
-2
> (new:si & 2)
--2
> (new:si & -2)
--3
> (new:si & --2)
--4++old:si
Sign and absolute value
Produces a cell composed of a %.y or %.n, depending on whether a is
positive or negative, and the absolute value of a.
Accepts
a is a signed integer.
Produces
A cell composed of a term and an atom.
Source
++ old |=(a=@s [(syn a) (abs a)])
Examples
> (old:si -2)
[%.n 2]
> (old:si --2)
[%.y 2]++pro:si
Multiplication
Produces a signed integer by multiplying a and b.
Accepts
a is an unsigned integer.
b is an unsigned integer.
Source
++ pro |= [a=@s b=@s]
(new =(0 (mix (syn a) (syn b))) (mul (abs a) (abs b)))
Examples
> (pro:si -3 -3)
--9
> (pro:si -3 --3)
-9++rem:si
Remainder
Produces a signed integer that is the remainder of a divided by b.
Accepts
a is a signed integer.
b is a signed integer.
Produces
A signed integer.
Source
++ rem |=([a=@s b=@s] (dif a (pro b (fra a b))))
Examples
> (rem:si -17 -3)
-2
> (rem:si --17 -3)
--2
> (rem:si -17 --3)
-2
> (rem:si --17 --3)
--2++sum:si
Addition
Produces an atom by adding a and b.
Accepts
a is a signed integer.
b is a signed integer.
Produces
A signed integer.
Source
++ sum |= [a=@s b=@s]
=+ [c=(old a) d=(old b)]
?: -.c
?: -.d
(new & (add +.c +.d))
?: (gte +.c +.d)
(new & (sub +.c +.d))
(new | (sub +.d +.c))
?: -.d
?: (gte +.c +.d)
(new | (sub +.c +.d))
(new & (sub +.d +.c))
(new | (add +.c +.d))
Examples
> (sum:si -11 --2)
-9
> (sum:si --2 --2)
--4++sun:si
@u to @s
Multiplies the unsigned integer a by two, producing an atom.
Accepts
a is an unsigned integer.
Produces
An atom.
Source
++ sun |=(a=@u (mul 2 a))
Examples
> (sun:si 90)
180
> (sun:si --90)
360
> `@u`--90
180
> (sun:si --89)
356
> `@u`--89
178
> (sun:si -89)
354
> `@u`-89
177++syn:si
Sign test
Tests whether signed atom a is positive or negative. %.y is produced if a
is positive, and %.n is produced if a is negative.
Accepts
a is a signed integer.
Produces
An term.
Source
++ syn |=(a=@s =(0 (end 0 1 a)))
Examples
> (syn:si -2)
%.n
> (syn:si --2)
%.y++cmp:si
Compare
Compares a and b to see which is greater. If a is greater than b, --1
is produced. If b is greater than a, -1 is produced. If a and b are
equal, --0 is produced.
Accepts
a is a signed integer.
b is a signed integer.
Produces
A signed integer.
Source
++ cmp |= [a=@s b=@s]
^- @s
?: =(a b)
--0
?: (syn a)
?: (syn b)
?: (gth a b)
--1
-1
--1
?: (syn b)
-1
?: (gth a b)
-1
--1
--
Examples
> (cmp:si -2 --1)
-1
> (cmp:si -2 --1)
-1
> (cmp:si --2 --1)
--1
> (cmp:si --2 --2)
--0
> (cmp:si --2 --5)
-1