git.iko.soy/urbit.org
on 979ae21 help sign in
urbit.org/hoon/reference/stdlib/3a.md
859 lines 10 kB history raw
1+++
2title = "3a: Modular and Signed Ints"
3weight = 21
4template = "doc.html"
5+++
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
375prepended with a `--`, and negative integers are prepended with a `-`. For
376example, `--1` represents positive one, and `-1` represents negative one.
378Zig zag encoding is used to convert atoms to signed integers. Positive signed
379integers correspond to even atoms of twice their absolute value, and negative
380signed integers correspond to odd atoms of twice their absolute value minus
381one. For example:
383```
384 > `@`--4
385 8
386 > `@s`8
387 --4
389 > `@`-4
390 7
391 > `@s`7
392 -4
393```
395---
396### `++abs:si`
398Absolute value
400Produces the absolute value of signed integer `a`.
402#### Accepts
404`a` is a signed integer.
406#### Produces
408An atom.
410### Source
412```hoon
413 ++ abs |=(a=@s (add (end 0 1 a) (rsh 0 1 a)))
414```
416#### Examples
418```
419 > (abs:si -11)
420 11
422 > (abs:si --520)
423 520
424```
426---
427### `++dif:si`
429Subtraction
431Produces the difference of `a` minus `b`.
433#### Accepts
435`a` is a signed integer.
437`b` is a signed integer.
439#### Produces
441A signed integer.
443#### Source
445```hoon
446 ++ dif |= [a=@s b=@s]
447 (sum a (new !(syn b) (abs b)))
448```
450#### Examples
452```
453 > (dif:si --3 -2)
454 --5
456 > (dif:si -3 --2)
457 -5
458```
460---
461### `++dul:si`
463Modulus
465Produces the remainder of `b` modulo `a`.
467#### Examples
469`a` is a signed integer.
471`b` is an atom.
473#### Produces
475An atom.
477#### Source
479```hoon
480 ++ dul |= [a=@s b=@]
481 =+(c=(old a) ?:(-.c (mod +.c b) (sub b +.c)))
482```
484#### Examples
486```
487 > `@s`(dul:si -1 --5)
488 -5
490 > `@`--5
491 10
492 > `@s`(dul:si -1 10)
493 -5
495 > `@s`(dul:si -11 -61)
496 --55
497```
499---
500### `++fra:si`
502Divide
504Produces the quotient of `b` divided by `c`.
506#### Accepts
508`a` is a signed integer.
510`b` is a signed integer.
512#### Produces
514A signed atom.
516#### Source
518```hoon
519 ++ fra |= [a=@s b=@s]
520 (new =(0 (mix (syn a) (syn b))) (div (abs a) (abs b)))
521```
523#### Examples
525```
526 > (fra:si -1 -1)
527 --1
529 > (fra:si -11 --2)
530 -5
532 > (fra:si -0 -1)
533 --0
534```
536---
537### `++new:si`
539Atom to @s
541Produces a signed integer from an atom `b`. The product's sign is determined
542by the value of flag `a`: `&` will result in a prepending `--`, and `|` will
543result in a prepending `-`.
545#### Accepts
547`a` is a flag.
549`b` is an atom.
551#### Produces
553A signed integer.
555#### Source
557```hoon
558 ++ new |= [a=? b=@]
559 `@s`?:(a (mul 2 b) ?:(=(0 b) 0 +((mul 2 (dec b)))))
560```
562#### Examples
564```
565 > (new:si | 2)
566 -2
568 > (new:si & 2)
569 --2
571 > (new:si & -2)
572 --3
574 > (new:si & --2)
575 --4
576```
578---
579### `++old:si`
581Sign and absolute value
583Produces a cell composed of a `%.y` or `%.n`, depending on whether `a` is
584positive or negative, and the absolute value of `a`.
586#### Accepts
588`a` is a signed integer.
590#### Produces
592A cell composed of a `term` and an atom.
594#### Source
596```hoon
597 ++ old |=(a=@s [(syn a) (abs a)])
598```
600#### Examples
602```
603 > (old:si -2)
604 [%.n 2]
606 > (old:si --2)
607 [%.y 2]
608```
610---
611### `++pro:si`
613Multiplication
615Produces a signed integer by multiplying `a` and `b`.
617#### Accepts
619`a` is an unsigned integer.
621`b` is an unsigned integer.
623#### Source
625```hoon
626 ++ pro |= [a=@s b=@s]
627 (new =(0 (mix (syn a) (syn b))) (mul (abs a) (abs b)))
628```
630#### Examples
632```
633 > (pro:si -3 -3)
634 --9
636 > (pro:si -3 --3)
637 -9
638```
640---
641### `++rem:si`
643Remainder
645Produces a signed integer that is the remainder of `a` divided by `b`.
647#### Accepts
649`a` is a signed integer.
651`b` is a signed integer.
653#### Produces
655A signed integer.
657#### Source
659```hoon
660 ++ rem |=([a=@s b=@s] (dif a (pro b (fra a b))))
661```
663#### Examples
665```
666 > (rem:si -17 -3)
667 -2
669 > (rem:si --17 -3)
670 --2
672 > (rem:si -17 --3)
673 -2
675 > (rem:si --17 --3)
676 --2
677```
680---
681### `++sum:si`
683Addition
685Produces an atom by adding `a` and `b`.
687#### Accepts
689`a` is a signed integer.
691`b` is a signed integer.
693#### Produces
695A signed integer.
697#### Source
699```hoon
700 ++ sum |= [a=@s b=@s]
701 =+ [c=(old a) d=(old b)]
702 ?: -.c
703 ?: -.d
704 (new & (add +.c +.d))
705 ?: (gte +.c +.d)
706 (new & (sub +.c +.d))
707 (new | (sub +.d +.c))
708 ?: -.d
709 ?: (gte +.c +.d)
710 (new | (sub +.c +.d))
711 (new & (sub +.d +.c))
712 (new | (add +.c +.d))
713```
715#### Examples
717```
718 > (sum:si -11 --2)
719 -9
721 > (sum:si --2 --2)
722 --4
723```
725---
726### `++sun:si`
728@u to @s
730Multiplies the unsigned integer `a` by two, producing an atom.
732#### Accepts
734`a` is an unsigned integer.
736#### Produces
738An atom.
740#### Source
742```hoon
743 ++ sun |=(a=@u (mul 2 a))
744```
746#### Examples
748```
749 > (sun:si 90)
750 180
752 > (sun:si --90)
753 360
754 > `@u`--90
755 180
757 > (sun:si --89)
758 356
759 > `@u`--89
760 178
762 > (sun:si -89)
763 354
764 > `@u`-89
765 177
766```
768---
769### `++syn:si`
771Sign test
773Tests whether signed atom `a` is positive or negative. `%.y` is produced if `a`
774is positive, and `%.n` is produced if `a` is negative.
776#### Accepts
778`a` is a signed integer.
780#### Produces
782An `term`.
784#### Source
786```hoon
787 ++ syn |=(a=@s =(0 (end 0 1 a)))
788```
790#### Examples
792```
793 > (syn:si -2)
794 %.n
796 > (syn:si --2)
797 %.y
798```
800---
801### `++cmp:si`
803Compare
805Compares `a` and `b` to see which is greater. If `a` is greater than `b`, `--1`
806is produced. If `b` is greater than `a`, `-1` is produced. If `a` and `b` are
807equal, `--0` is produced.
809#### Accepts
811`a` is a signed integer.
813`b` is a signed integer.
815#### Produces
817A signed integer.
819#### Source
821```hoon
822 ++ cmp |= [a=@s b=@s]
823 ^- @s
824 ?: =(a b)
825 --0
826 ?: (syn a)
827 ?: (syn b)
828 ?: (gth a b)
829 --1
830 -1
831 --1
832 ?: (syn b)
833 -1
834 ?: (gth a b)
835 -1
836 --1
837 --
838```
840#### Examples
842```
843 > (cmp:si -2 --1)
844 -1
846 > (cmp:si -2 --1)
847 -1
849 > (cmp:si --2 --1)
850 --1
852 > (cmp:si --2 --2)
853 --0
855 > (cmp:si --2 --5)
856 -1
857```
859---