# 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 ```hoon ++ 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 ```hoon ++ fo ^| |_ a=@ ``` *** ### `+dif:fo` Subtraction. Produces the difference between `$atom`s `.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 ```hoon ++ 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 ```hoon ++ 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 ```hoon ++ 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`](#egcd) of `.a` and `.b`. #### Accepts `.a` is an `$atom`, and is the sample of `+fo`. `.b` is an `$atom`. #### Produces An `$atom`. #### Source ```hoon ++ 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 ```hoon ++ 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 ```hoon ++ 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 ```hoon ++ 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 ```hoon ++ 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](https://developers.google.com/protocol-buffers/docs/encoding?hl=en#signed-ints) is used to convert `$atom`s to signed integers. Positive signed integers correspond to even `$atom`s of twice their absolute value, and negative signed integers correspond to odd `$atom`s 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 ```hoon ++ 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 ```hoon ++ 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 ```hoon ++ 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 ```hoon ++ 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 ```hoon ++ 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 `$flag` and an `$atom`. #### Source ```hoon ++ old |=(a=@s [(syn a) (abs a)]) ``` ```hoon ++ 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 ```hoon ++ 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 ```hoon ++ 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 ```hoon ++ 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 ```hoon ++ 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 `$flag`. #### Source ```hoon ++ 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 ```hoon ++ 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 ``` *** --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://docs.urbit.org/hoon/stdlib/3a.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.