Urbit / Docs

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
      |=  [[email protected] [email protected]]
      =+  si
      =+  [c=(sun a) d=(sun b)]
      =+  [u=[c=(sun 1) d=--0] v=[c=--0 d=(sun 1)]]
      |-  ^-  [[email protected] [email protected] [email protected]]
      ?:  =(--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
      ^?
      |_  [email protected]

++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
        |=  [[email protected] [email protected]]
        (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
        |=  [[email protected] [email protected]]
        ?:  =(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
        |=  [[email protected] [email protected]]
        (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
        |=  [email protected]
        =+  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
        |=  [[email protected] [email protected]]
        (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
        |=  [email protected]
        (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
        |=  [[email protected] [email protected]]
        (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  |=([email protected] (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  |=  [[email protected] [email protected]]
               (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  |=  [[email protected] [email protected]]
               =+(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  |=  [[email protected] [email protected]]
               (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=? [email protected]]
               `@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  |=([email protected] [(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  |=  [[email protected] [email protected]]
               (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  |=([[email protected] [email protected]] (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  |=  [[email protected] [email protected]]
               =+  [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  |=([email protected] (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  |=([email protected] =(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  |=  [[email protected] [email protected]]
               ^-  @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