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.

    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.

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

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

    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.

    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.

    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.

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

    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

    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