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 .
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 $flag 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 $flag.
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