# 3a: Modular and Signed Ints

### `++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.

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.

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.

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.

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.

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.

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.

An atom.

#### Source

``````      ++  sum
|=  [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.

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.

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.

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`

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
?:  (gte +.c +.d)
(new & (sub +.c +.d))
(new | (sub +.d +.c))
?:  -.d
?:  (gte +.c +.d)
(new | (sub +.c +.d))
(new & (sub +.d +.c))
``````

#### 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.

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
``````