3a: Modular and Signed Ints
+egcd
+egcdExtended 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
+foModulo prime
Container door for modular arithmetic functions.
Accepts
a is an atom
Source
++ fo
^|
|_ a=@++dif:fo
++dif:foSubtraction
Produces the difference between atoms b and c, with a as the modular base.
Accepts
a is an atom, and is the sample of +fo.
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
++exp:foExponent
Produces the power of c raised to the b, with a as the modular base.
Accepts
a is an atom, and is the sample of +fo.
b is an atom.
c is an atom.
Produces
An atom.
Source
++ exp
|= [b=@ c=@]
?: =(0 b)
1
=+ d=$(b (rsh 0 b))
=+ e=(pro d d)
?:(=(0 (end 0 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
++fra:foDivide
Produces the quotient of b divided by c, with a as the modular base.
Accepts
a is an atom, and is the sample of +fo.
b is an atom.
c is an atom.
Produces
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
++inv:foInverse
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, and is the sample of +fo.
b is an atom.
Produces
An atom.
Source
++ inv
|= b=@
=+ c=(dul:si u:(egcd b a) a)
cExamples
> (~(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
++pro:foMultiplication
Produces the multiplication of b and c modulo a.
Accepts
a is an atom, and is the sample of +fo.
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
++sit:foModulus
Produces the remainder of b modulo a.
Accepts
a is an atom, and is the sample of +fo.
b is an atom.
Produces
An atom.
Source
++ sit
|= b=@
(mod b a)Examples
> (~(sit fo 3) 14)
2++sum:fo
++sum:foModular sum
Produces the remainder of (b + c) mod a.
Accepts
a is an atom, and is the sample of +fo.
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
+siSigned 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.
ZigZag 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
++abs:siAbsolute 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 a) (rsh 0 a)))Examples
> (abs:si -11)
11
> (abs:si --520)
520++dif:si
++dif:siSubtraction
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
++dul:siModulus
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
++fra:siDivide
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
++new:siAtom 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
++old:siSign 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 ? and an atom.
Source
++ old |=(a=@s [(syn a) (abs a)])++ old |=(a=@s [(syn a) (abs a)])Examples
> (old:si -2)
[%.n 2]
> (old:si --2)
[%.y 2]++pro:si
++pro:siMultiplication
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
++rem:siRemainder
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
++sum:siAddition
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
++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
++syn:siSign 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
A ?.
Source
++ syn |=(a=@s =(0 (end 0 a)))Examples
> (syn:si -2)
%.n
> (syn:si --2)
%.y++cmp:si
++cmp:siCompare
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
--1Examples
> (cmp:si -2 --1)
-1
> (cmp:si -2 --1)
-1
> (cmp:si --2 --1)
--1
> (cmp:si --2 --2)
--0
> (cmp:si --2 --5)
-1Last updated