:-  :~  navhome/'/docs/'
        sort/'21'
        title/'3a: Modular and Signed Ints'
    ==

;>

# 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

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

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`

Exponent

Produces the power of `b` raised to the `c`, 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`

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`

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`

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`

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`

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
represented with a two prepending `-`s, and negative integers are represented
with two; `--1` and `-1`, respectively.

Positive signed integers correspond to odd atoms of twice their absolute value,
and negative signed integers correspond to 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`

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`

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

```
    > (mul 2 90)
    180

    > (mul 2 --90)
    360
    > `@u`--90
    180

    > (mul 2 --89)
    356
    > `@u`--89
    178

    > (mul 2 -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
```

---