# 3a: Modular and Signed Ints
## `+egcd`
Extended Euclidean algorithm.
Produces `.d`, the [greatest common divisor](https://en.wikipedia.org/wiki/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
```hoon
++ 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 door for modular arithmetic functions.
#### Accepts
`.a` is an `$atom`
#### Source
```hoon
++ fo
^|
|_ a=@
```
***
### `+dif:fo`
Subtraction.
Produces the difference between `$atom`s `.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
```hoon
++ 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`, and is the sample of `+fo`.
`.b` is an `$atom`.
`.c` is an `$atom`.
#### Produces
An `$atom`.
#### Source
```hoon
++ 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`
Divide.
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
```hoon
++ 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`](#egcd) of `.a` and `.b`.
#### Accepts
`.a` is an `$atom`, and is the sample of `+fo`.
`.b` is an `$atom`.
#### Produces
An `$atom`.
#### Source
```hoon
++ 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`, and is the sample of `+fo`.
`.b` is an `$atom`.
`.c` is an `$atom`.
#### Produces
An `$atom`.
#### Source
```hoon
++ 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`, and is the sample of `+fo`.
`.b` is an `$atom`.
#### Produces
An `$atom`.
#### Source
```hoon
++ 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`, and is the sample of `+fo`.
`.b` is an `$atom`.
`.c` is an `$atom`.
#### Produces
An `$atom`.
#### Source
```hoon
++ 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
```hoon
++ 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](https://developers.google.com/protocol-buffers/docs/encoding?hl=en#signed-ints) is used to convert `$atom`s to signed integers. Positive signed integers correspond to even `$atom`s of twice their absolute value, and negative signed integers correspond to odd `$atom`s 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
```hoon
++ abs |=(a=@s (add (end 0 a) (rsh 0 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
```hoon
++ 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
```hoon
++ 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
```hoon
++ 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
```hoon
++ 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 `$flag` and an `$atom`.
#### Source
```hoon
++ old |=(a=@s [(syn a) (abs a)])
```
```hoon
++ 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
```hoon
++ 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
```hoon
++ 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
```hoon
++ 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
```hoon
++ 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
A `$flag`.
#### Source
```hoon
++ syn |=(a=@s =(0 (end 0 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
```hoon
++ 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
```
***