git.iko.soy/urbit.org
on f3ca521 help sign in
urbit.org/reference/library/3a.md
858 lines 10 kB history raw
1+++
2title = "3a: Modular and Signed Ints"
3weight = 21
4template = "doc.html"
5aliases = ["/docs/reference/library/3a"]
6+++
7### `++egcd`
9Extended Euclidean algorithm
11Produces `d`, the
12[greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor)
13of `a` and `b`. Also produces `u` and `v` such that `au + bv = GCD(a, b)`.
15#### Accepts
17`a` is an atom.
19`b` is an atom.
21#### Produces
23`d`, the greatest common divisor, is an atom.
25`u`, the coefficient of `a`, is a signed integer.
27`v`, the coefficient of `b`, is a signed integer.
29#### Source
31```hoon
32 ++ egcd
33 |= [a=@ b=@]
34 =+ si
35 =+ [c=(sun a) d=(sun b)]
36 =+ [u=[c=(sun 1) d=--0] v=[c=--0 d=(sun 1)]]
37 |- ^- [d=@ u=@s v=@s]
38 ?: =(--0 c)
39 [(abs d) d.u d.v]
40 =+ q=(fra d c)
41 %= $
42 c (dif d (pro q c))
43 d c
44 u [(dif d.u (pro q c.u)) c.u]
45 v [(dif d.v (pro q c.v)) c.v]
46 ==
47```
49#### Examples
51```
52 > (egcd 11 2)
53 [d=1 u=--1 v=-5]
54```
56---
57### `++fo`
59Modulo prime
61Container core for modular arithmetic functions.
63#### Source
65```hoon
66 ++ fo
67 ^?
68 |_ a=@
69```
71---
72### `++dif:fo`
74Subtraction
76Produces the difference between atoms `b` and `c`, with `a` as the modular base.
78#### Accepts
80`a` is an atom.
82`b` is an atom.
84`c` is an atom.
86#### Produces
88An atom.
90#### Source
92```hoon
93 ++ dif
94 |= [b=@ c=@]
95 (sit (sub (add a b) (sit c)))
96```
98#### Examples
100```
101 > (~(dif fo 6) 1 2)
102 5
104 > (~(dif fo 21) 11 45)
105 8
106```
108---
109### `++exp:fo`
111Exponent
113Produces the power of `c` raised to the `b`, with `a` as the modular base.
115#### Accepts
117`a` is an atom.
119`b` is an atom.
121`c` is an atom.
123#### Produces
125An atom.
127#### Source
129```hoon
130 ++ exp
131 |= [b=@ c=@]
132 ?: =(0 b)
133 1
134 =+ d=$(b (rsh 0 1 b))
135 =+ e=(pro d d)
136 ?:(=(0 (end 0 1 b)) e (pro c e))
137```
139#### Examples
141```
142 > (~(exp fo 5) 8 2)
143 1
145 > (~(exp fo 95) 8 2)
146 66
148 > (~(exp fo 195) 8 2)
149 61
151 > (~(exp fo 995) 8 2)
152 256
153```
155---
156### `++fra:fo`
158Divide
160Produces the quotient of `b` divided by `c`, with `a` as the modular base.
162#### Accepts
164`a` is an atom.
166`b` is an atom.
168`c` is an atom.
170#### Produces
172An atom.
174#### Accepts
176`a` is an atom.
178`b` is an atom.
180#### Source
182```hoon
183 ++ fra
184 |= [b=@ c=@]
185 (pro b (inv c))
186```
188#### Examples
190```
191 > (~(fra fo 2) 8 2)
192 0
194 > (~(fra fo 3) 8 2)
195 1
197 > (~(fra fo 4) 8 2)
198 0
200 > (~(fra fo 5) 8 2)
201 4
202```
204---
205### `++inv:fo`
207Inverse
209Produces an atom by taking the signed modulus of `a` with the coefficient `u`;
210`u` is produced by taking the `++egcd` of `a` and `b`.
212#### Accepts
214`a` is an atom.
216`b` is an atom.
218#### Produces
220An atom.
222#### Source
224```hoon
225 ++ inv
226 |= b=@
227 =+ c=(dul:si u:(egcd b a) a)
228 c
229```
231#### Examples
233```
234 > (~(inv fo 11) 2)
235 6
237 > (~(inv fo 71) 255)
238 22
240 > (~(inv fo 79) 255)
241 22
243 > (~(inv fo 78) 255)
244 67
246 > (~(inv fo 70) 255)
247 67
248```
250---
251### `++pro:fo`
253Multiplication
255Produces the multiplication of `b` and `c` modulo `a`.
257#### Accepts
259`a` is an atom.
261`b` is an atom.
263`c` is an atom.
265#### Produces
267An atom.
269#### Source
271```hoon
272 ++ pro
273 |= [b=@ c=@]
274 (sit (mul b c))
275```
277#### Examples
279```
280 > (~(pro fo 3) 11 4)
281 2
283 > (mod 44 3)
284 2
285```
287---
288### `++sit:fo`
290Modulus
292Produces the remainder of `b` modulo `a`.
294#### Accepts
296`a` is an atom.
298`b` is an atom.
300#### Produces
302An atom.
304#### Source
306```hoon
307 ++ sit
308 |= b=@
309 (mod b a)
310```
312#### Examples
314```
315 > (~(sit fo 3) 14)
316 2
317```
319---
320### `++sum:fo`
322Modular sum
324Produces the remainder of `(b + c) mod a`.
326#### Accepts
328`a` is an atom.
330`b` is an atom.
332`c` is an atom.
334#### Produces
336An atom.
338#### Source
340```hoon
341 ++ sum
342 |= [b=@ c=@]
343 (sit (add b c))
344 --
345```
347#### Examples
349```
350 > (~(sum fo 3) 14 3)
351 2
353 > (mod 17 3)
354 2
355```
357---
358### `++si`
360Signed integer
362Container core for signed integer functions.
364#### Source
366```hoon
367 ++ si
368 ^?
369 |%
370```
372#### Discussion
374The signed-integer type is represented by the `@s` aura. Positive integers are
375represented with a two prepending `-`s, and negative integers are represented
376with two; `--1` and `-1`, respectively.
378Positive signed integers correspond to odd atoms of twice their absolute value,
379and negative signed integers correspond to atoms of twice their absolute value
380minus one. For example:
382```
383 > `@`--4
384 8
385 > `@s`8
386 --4
388 > `@`-4
389 7
390 > `@s`7
391 -4
392```
394---
395### `++abs:si`
397Absolute value
399Produces the absolute value of signed integer `a`.
401#### Accepts
403`a` is a signed integer.
405#### Produces
407An atom.
409### Source
411```hoon
412 ++ abs |=(a=@s (add (end 0 1 a) (rsh 0 1 a)))
413```
415#### Examples
417```
418 > (abs:si -11)
419 11
421 > (abs:si --520)
422 520
423```
425---
426### `++dif:si`
428Subtraction
430Produces the difference of `a` minus `b`.
432#### Accepts
434`a` is a signed integer.
436`b` is a signed integer.
438#### Produces
440A signed integer.
442#### Source
444```hoon
445 ++ dif |= [a=@s b=@s]
446 (sum a (new !(syn b) (abs b)))
447```
449#### Examples
451```
452 > (dif:si --3 -2)
453 --5
455 > (dif:si -3 --2)
456 -5
457```
459---
460### `++dul:si`
462Modulus
464Produces the remainder of `b` modulo `a`.
466#### Examples
468`a` is a signed integer.
470`b` is an atom.
472#### Produces
474An atom.
476#### Source
478```hoon
479 ++ dul |= [a=@s b=@]
480 =+(c=(old a) ?:(-.c (mod +.c b) (sub b +.c)))
481```
483#### Examples
485```
486 > `@s`(dul:si -1 --5)
487 -5
489 > `@`--5
490 10
491 > `@s`(dul:si -1 10)
492 -5
494 > `@s`(dul:si -11 -61)
495 --55
496```
498---
499### `++fra:si`
501Divide
503Produces the quotient of `b` divided by `c`.
505#### Accepts
507`a` is a signed integer.
509`b` is a signed integer.
511#### Produces
513A signed atom.
515#### Source
517```hoon
518 ++ fra |= [a=@s b=@s]
519 (new =(0 (mix (syn a) (syn b))) (div (abs a) (abs b)))
520```
522#### Examples
524```
525 > (fra:si -1 -1)
526 --1
528 > (fra:si -11 --2)
529 -5
531 > (fra:si -0 -1)
532 --0
533```
535---
536### `++new:si`
538Atom to @s
540Produces a signed integer from an atom `b`. The product's sign is determined
541by the value of flag `a`: `&` will result in a prepending `--`, and `|` will
542result in a prepending `-`.
544#### Accepts
546`a` is a flag.
548`b` is an atom.
550#### Produces
552A signed integer.
554#### Source
556```hoon
557 ++ new |= [a=? b=@]
558 `@s`?:(a (mul 2 b) ?:(=(0 b) 0 +((mul 2 (dec b)))))
559```
561#### Examples
563```
564 > (new:si | 2)
565 -2
567 > (new:si & 2)
568 --2
570 > (new:si & -2)
571 --3
573 > (new:si & --2)
574 --4
575```
577---
578### `++old:si`
580Sign and absolute value
582Produces a cell composed of a `%.y` or `%.n`, depending on whether `a` is
583positive or negative, and the absolute value of `a`.
585#### Accepts
587`a` is a signed integer.
589#### Produces
591A cell composed of a `term` and an atom.
593#### Source
595```hoon
596 ++ old |=(a=@s [(syn a) (abs a)])
597```
599#### Examples
601```
602 > (old:si -2)
603 [%.n 2]
605 > (old:si --2)
606 [%.y 2]
607```
609---
610### `++pro:si`
612Multiplication
614Produces a signed integer by multiplying `a` and `b`.
616#### Accepts
618`a` is an unsigned integer.
620`b` is an unsigned integer.
622#### Source
624```hoon
625 ++ pro |= [a=@s b=@s]
626 (new =(0 (mix (syn a) (syn b))) (mul (abs a) (abs b)))
627```
629#### Examples
631```
632 > (pro:si -3 -3)
633 --9
635 > (pro:si -3 --3)
636 -9
637```
639---
640### `++rem:si`
642Remainder
644Produces a signed integer that is the remainder of `a` divided by `b`.
646#### Accepts
648`a` is a signed integer.
650`b` is a signed integer.
652#### Produces
654A signed integer.
656#### Source
658```hoon
659 ++ rem |=([a=@s b=@s] (dif a (pro b (fra a b))))
660```
662#### Examples
664```
665 > (rem:si -17 -3)
666 -2
668 > (rem:si --17 -3)
669 --2
671 > (rem:si -17 --3)
672 -2
674 > (rem:si --17 --3)
675 --2
676```
679---
680### `++sum:si`
682Addition
684Produces an atom by adding `a` and `b`.
686#### Accepts
688`a` is a signed integer.
690`b` is a signed integer.
692#### Produces
694A signed integer.
696#### Source
698```hoon
699 ++ sum |= [a=@s b=@s]
700 =+ [c=(old a) d=(old b)]
701 ?: -.c
702 ?: -.d
703 (new & (add +.c +.d))
704 ?: (gte +.c +.d)
705 (new & (sub +.c +.d))
706 (new | (sub +.d +.c))
707 ?: -.d
708 ?: (gte +.c +.d)
709 (new | (sub +.c +.d))
710 (new & (sub +.d +.c))
711 (new | (add +.c +.d))
712```
714#### Examples
716```
717 > (sum:si -11 --2)
718 -9
720 > (sum:si --2 --2)
721 --4
722```
724---
725### `++sun:si`
727@u to @s
729Multiplies the unsigned integer `a` by two, producing an atom.
731#### Accepts
733`a` is an unsigned integer.
735#### Produces
737An atom.
739#### Source
741```hoon
742 ++ sun |=(a=@u (mul 2 a))
743```
745#### Examples
747```
748 > (sun:si 90)
749 180
751 > (sun:si --90)
752 360
753 > `@u`--90
754 180
756 > (sun:si --89)
757 356
758 > `@u`--89
759 178
761 > (sun:si -89)
762 354
763 > `@u`-89
764 177
765```
767---
768### `++syn:si`
770Sign test
772Tests whether signed atom `a` is positive or negative. `%.y` is produced if `a`
773is positive, and `%.n` is produced if `a` is negative.
775#### Accepts
777`a` is a signed integer.
779#### Produces
781An `term`.
783#### Source
785```hoon
786 ++ syn |=(a=@s =(0 (end 0 1 a)))
787```
789#### Examples
791```
792 > (syn:si -2)
793 %.n
795 > (syn:si --2)
796 %.y
797```
799---
800### `++cmp:si`
802Compare
804Compares `a` and `b` to see which is greater. If `a` is greater than `b`, `--1`
805is produced. If `b` is greater than `a`, `-1` is produced. If `a` and `b` are
806equal, `--0` is produced.
808#### Accepts
810`a` is a signed integer.
812`b` is a signed integer.
814#### Produces
816A signed integer.
818#### Source
820```hoon
821 ++ cmp |= [a=@s b=@s]
822 ^- @s
823 ?: =(a b)
824 --0
825 ?: (syn a)
826 ?: (syn b)
827 ?: (gth a b)
828 --1
829 -1
830 --1
831 ?: (syn b)
832 -1
833 ?: (gth a b)
834 -1
835 --1
836 --
837```
839#### Examples
841```
842 > (cmp:si -2 --1)
843 -1
845 > (cmp:si -2 --1)
846 -1
848 > (cmp:si --2 --1)
849 --1
851 > (cmp:si --2 --2)
852 --0
854 > (cmp:si --2 --5)
855 -1
856```
858---