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 door for modular arithmetic functions.

Accepts

a is an atom

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

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

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

++  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, and is the sample of +fo.

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

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

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

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

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

++  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: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 ? 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

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

> (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 ?.

Source

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

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