Skip to content

3a.md

Latest commit

 

History

History
968 lines (644 loc) · 10.5 KB

3a.md

File metadata and controls

968 lines (644 loc) · 10.5 KB
Raw
description Signed integer arithmetic and modular arithmetic operations.
layout
title description tableOfContents outline pagination
visible
true
visible
visible
true
visible
true
visible
true

3a: Signed and Modular Arithmetic

+egcd {#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 {#fo}

Modulo prime.

Container door for modular arithmetic functions.

Accepts

.a is an $atom

Source

++  fo
  ^|
  |_  a=@

+dif:fo {#diffo}

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 {#expfo}

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 {#frafo}

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 {#invfo}

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 {#profo}

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 {#sitfo}

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 {#sumfo}

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 {#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 {#abssi}

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 {#difsi}

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 {#dulsi}

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 {#frasi}

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 {#newsi}

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 {#oldsi}

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

      ++  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 {#prosi}

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 {#remsi}

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 {#sumsi}

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 {#sunsi}

@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 {#synsi}

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

++  syn  |=(a=@s =(0 (end 0 a)))

Examples

> (syn:si -2)
%.n

> (syn:si --2)
%.y

+cmp:si {#cmpsi}

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