git.iko.soy/urbit.org
on 8564483 help sign in
urbit.org/docs/hoon/library/3a.md
947 lines 14 kB history raw
1---
2navhome: /docs
3---
6# 3a: signed and modular ints
7### `++fe` :: modulo bloq
9Modulo bloq
11Core containing XX
13Accepts
14-------
16`a` is a `++bloq`.
18Source
19------
21 |_ a=bloq
23### `++dif`
25Produces the difference between two atoms in the modular basis
26representation.
28Accepts
29-------
31`a` is a `++bloq`.
33`b` is an atom.
35`c` is an atom.
37Produces
38--------
40A `@s`
42Source
43------
45 ++ dif |=([b/@ c/@] (sit (sub (add out (sit b)) (sit c))))
47Examples
48--------
50 > (~(dif fe 3) 63 64)
51 255
52 > (~(dif fe 3) 5 10)
53 251
54 > (~(dif fe 3) 0 1)
55 255
56 > (~(dif fe 0) 9 10)
57 1
58 > (~(dif fe 0) 9 11)
59 0
60 > (~(dif fe 0) 9 12)
61 1
62 > (~(dif fe 2) 9 12)
63 13
64 > (~(dif fe 2) 63 64)
65 15
67------------------------------------------------------------------------
69### `++inv`
71Invert mod field
73Inverts the order of the modular field.
75Accepts
76-------
78`b` is a `++bloq`.
80Produces
81--------
83An atom.
86Source
87------
89 ++ inv |=(b/@ (sub (dec out) (sit b)))
91Examples
92--------
94 > (~(inv fe 3) 255)
95 0
96 > (~(inv fe 3) 256)
97 255
98 > (~(inv fe 3) 0)
99 255
100 > (~(inv fe 3) 1)
101 254
102 > (~(inv fe 3) 2)
103 253
104 > (~(inv fe 3) 55)
105 200
107------------------------------------------------------------------------
109### `++net`
111Reverse bytes
113Revereses bytes within block.
115Accepts
116-------
118`b` is a `++bloq`.
120Produces
121--------
123An atom.
125Source
126------
128 ++ net |= b/@ ^- @
129 => .(b (sit b))
130 ?: (lte a 3)
131 b
132 =+ c=(dec a)
133 %+ con
134 (lsh c 1 $(a c, b (cut c [0 1] b)))
135 $(a c, b (cut c [1 1] b))
137Examples
138--------
140 > (~(net fe 3) 64)
141 64
142 > (~(net fe 3) 128)
143 128
144 > (~(net fe 3) 255)
145 255
146 > (~(net fe 3) 256)
147 0
148 > (~(net fe 3) 257)
149 1
150 > (~(net fe 3) 500)
151 244
152 > (~(net fe 3) 511)
153 255
154 > (~(net fe 3) 512)
155 0
156 > (~(net fe 3) 513)
157 1
158 > (~(net fe 3) 0)
159 0
160 > (~(net fe 3) 1)
161 1
162 > (~(net fe 0) 1)
163 1
164 > (~(net fe 0) 2)
165 0
166 > (~(net fe 0) 3)
167 1
168 > (~(net fe 6) 1)
169 72.057.594.037.927.936
170 > (~(net fe 6) 2)
171 144.115.188.075.855.872
172 > (~(net fe 6) 3)
173 216.172.782.113.783.808
174 > (~(net fe 6) 4)
175 288.230.376.151.711.744
176 > (~(net fe 6) 5)
177 360.287.970.189.639.680
178 > (~(net fe 6) 6)
179 432.345.564.227.567.616
180 > (~(net fe 6) 7)
181 504.403.158.265.495.552
182 > (~(net fe 6) 512)
183 562.949.953.421.312
184 > (~(net fe 6) 513)
185 72.620.543.991.349.248
187------------------------------------------------------------------------
189### `++out`
191Max integer value
193The maximum integer value that the current block can store.
195Accepts
196-------
198A `++bloq`.
200Produces
201--------
203An atom.
205Source
206------
208 ++ out (bex (bex a))
210Examples
211--------
213 > ~(out fe 0)
214 2
215 > ~(out fe 1)
216 4
217 > ~(out fe 2)
218 16
219 > ~(out fe 3)
220 256
221 > ~(out fe 4)
222 65.536
223 > ~(out fe 10)
224 \/179.769.313.486.231.590.772.930.519.078.902.473.361.797.697.894.230.657.\/
225 273.430.081.157.732.675.805.500.963.132.708.477.322.407.536.021.120.113.
226 879.871.393.357.658.789.768.814.416.622.492.847.430.639.474.124.377.767.
227 893.424.865.485.276.302.219.601.246.094.119.453.082.952.085.005.768.838.
228 150.682.342.462.881.473.913.110.540.827.237.163.350.510.684.586.298.239.
229 947.245.938.479.716.304.835.356.329.624.224.137.216
230 \/ \/
232------------------------------------------------------------------------
234### `++rol`
236Roll left
238Roll `d` to the left by `c` `b`-sized blocks.
240Accepts
241-------
243`a` is a `++bloq`.
245`b` is a `++bloq`.
247`c` is an atom.
249`d` is an atom.
251Produces
252--------
254An atom.
256Source
257------
259 ++ rol |= [b/bloq c/@ d/@] ^- @ :: roll left
260 =+ e=(sit d)
261 =+ f=(bex (sub a b))
262 =+ g=(mod c f)
263 (sit (con (lsh b g e) (rsh b (sub f g) e)))
265Examples
266--------
268 > `@ux`(~(rol fe 6) 4 3 0xabac.dedf.1213)
269 0x1213.0000.abac.dedf
270 > `@ux`(~(rol fe 6) 4 2 0xabac.dedf.1213)
271 0xdedf.1213.0000.abac
272 > `@t`(~(rol fe 5) 3 1 'dfgh')
273 'hdfg'
274 > `@t`(~(rol fe 5) 3 2 'dfgh')
275 'ghdf'
276 > `@t`(~(rol fe 5) 3 0 'dfgh')
277 'dfgh'
279------------------------------------------------------------------------
281### `++ror`
283Roll right
285Roll `d` to the right by `c` `b`-sized blocks.
287Accepts
288-------
290`a` is a `++bloq`.
292`b` is a `++bloq`.
294`c` is an atom.
296`d` is an atom.
298Produces
299--------
301An atom.
303Source
304------
306 ++ ror |= {b/bloq c/@ d/@} ^- @ :: roll right
307 =+ e=(sit d)
308 =+ f=(bex (sub a b))
309 =+ g=(mod c f)
310 (sit (con (rsh b g e) (lsh b (sub f g) e)))
313Examples
314--------
316 > `@ux`(~(ror fe 6) 4 1 0xabac.dedf.1213)
317 0x1213.0000.abac.dedf
318 > `@ux`(~(ror fe 6) 3 5 0xabac.dedf.1213)
319 0xacde.df12.1300.00ab
320 > `@ux`(~(ror fe 6) 3 3 0xabac.dedf.1213)
321 0xdf12.1300.00ab.acde
322 > `@t`(~(rol fe 5) 3 0 'hijk')
323 'hijk'
324 > `@t`(~(rol fe 5) 3 1 'hijk')
325 'khij'
326 > `@t`(~(rol fe 5) 3 2 'hijk')
327 'jkhi'
329------------------------------------------------------------------------
331### `++sum`
333Sum
335Sum two numbers in this modular field.
337Accepts
338-------
340`a` is a `++bloq`.
342`b` is an atom.
344`c` is an atom.
346Produces
347--------
349An atom.
351Source
352------
354 ++ sum |=([b/@ c/@] (sit (add b c))) :: wrapping add
356Examples
357--------
359 > (~(sum fe 3) 10 250)
360 4
361 > (~(sum fe 0) 0 1)
362 1
363 > (~(sum fe 0) 0 2)
364 0
365 > (~(sum fe 2) 14 2)
366 0
367 > (~(sum fe 2) 14 3)
368 1
369 > (~(sum fe 4) 10.000 256)
370 10.256
371 > (~(sum fe 4) 10.000 100.000)
372 44.464
374### `++sit`
376Atom in mod block representation
378Produce an atom in the current modular block representation.
380Accepts
381-------
383`a` is a `++bloq`.
385`b` is an atom.
387Produces
388--------
390An atom.
392Source
393------
395 ++ sit |=(b/@ (end a 1 b)) :: enforce modulo
397Examples
398--------
400 > (~(sit fe 3) 255)
401 255
402 > (~(sit fe 3) 256)
403 0
404 > (~(sit fe 3) 257)
405 1
406 > (~(sit fe 2) 257)
407 1
408 > (~(sit fe 2) 10.000)
409 0
410 > (~(sit fe 2) 100)
411 4
412 > (~(sit fe 2) 19)
413 3
414 > (~(sit fe 2) 17)
415 1
416 > (~(sit fe 0) 17)
417 1
418 > (~(sit fe 0) 0)
419 0
420 > (~(sit fe 0) 1)
421 1
425***
426### `++si`
428 ++ si !: :: signed integer
429 |%
431Container core for the signed integer functions.
433------------------------------------------------------------------------
435### `++abs`
437Absolute value
439Produces the absolute value of a signed integer.
441Accepts
442-------
444`a` is a signed integer, `@s`.
446Produces
447--------
449An atom.
451Source
452------
454 ++ abs |=(a/@s (add (end 0 1 a) (rsh 0 1 a))) :: absolute value
456Examples
457--------
459 > (abs:si -2)
460 2
461 > (abs:si -10.000)
462 10.000
463 > (abs:si --2)
464 2
466------------------------------------------------------------------------
468### `++dif`
470Difference
472Produces the difference between two signed integers `b` and `c`.
474Accepts
475-------
477`a` is a signed integer, `@s`.
479`b` is a signed integer, `@s`.
481Produces
482--------
484A `@s`.
487Source
488------
490 ++ dif |= [a/@s b/@s] :: subtraction
491 (sum a (new !(syn b) (abs b)))
493Examples
494--------
496 > (dif:si --10 -7)
497 --17
498 > (dif:si --10 --7)
499 --3
500 > (dif:si `@s`0 --7)
501 -7
502 > (dif:si `@s`0 `@s`7)
503 --4
505------------------------------------------------------------------------
507### `++dul`
509Modulus
511Produces the modulus of two signed integers.
513Accepts
514-------
516`a` is a signed integer, `@s`.
518`b` is an atom.
520Produces
521--------
523An atom.
525Source
526------
528 ++ dul |= [a/@s b/@] :: modulus
529 =+(c=(old a) ?:(-.c (mod +.c b) (sub b +.c)))
531Examples
532--------
534 > (dul:si --9 3)
535 0
536 > (dul:si --9 4)
537 1
538 > (dul:si --9 5)
539 4
540 > (dul:si --9 6)
541 3
542 > (dul:si --90 --10)
543 10
545------------------------------------------------------------------------
547### `++fra`
549Divide
551Produces the quotient of two signed integers.
553Accepts
554-------
556`a` is a signed integer, `@s`.
558`b` is a signed integer, `@s`.
560Produces
561--------
563An atom.
565Source
566------
568 ++ fra |= [a/@s b/@s] :: divide
569 (new =(0 (mix (syn a) (syn b))) (div (abs a) (abs b)))
571Examples
572--------
574 > (fra:si --10 -2)
575 -5
576 > (fra:si -20 -5)
577 --4
579------------------------------------------------------------------------
581### `++new`
583Signed integer
585Produces a signed integer from a loobean sign value `a` and an atom `b`.
587Accepts
588-------
590`a` is a loobean.
592`b` is an atom.
594Produces
595--------
597A `@s`
599Source
600------
602 ++ new |= [a/? b/@] :: [sign value] to @s
603 `@s`?:(a (mul 2 b) ?:(=(0 b) 0 +((mul 2 (dec b)))))
605Examples
606--------
608 > (new:si [& 10])
609 --10
610 > (new:si [| 10])
611 -10
612 > (new:si [%.y 7])
613 --7
615------------------------------------------------------------------------
617### `++old`
619sign value
621Produces the cell `[sign value]` representations of a signed integer.
623Accepts
624-------
626`a` is a `@s`.
628Produces
629--------
631A cell of a boolean and an atom.
633Source
634------
636 ++ old |=(a/@s [(syn a) (abs a)]) :: [sign value]
638Examples
639--------
641 > (old:si 7)
642 ! type-fail
643 ! exit
644 > (old:si -7)
645 [%.n 7]
646 > (old:si --7)
647 [%.y 7]
648 > (old:si `@s`7)
649 [%.n 4]
650 > (old:si -0)
651 [%.y 0]
653------------------------------------------------------------------------
655### `++pro`
657Multiply
659Produces the product of two signed integers.
661Accepts
662-------
664`a` is a `@s`.
666`b` is a `@s`.
668Produces
669--------
671A `@s`.
673Source
674------
676 ++ pro |= [a/@s b/@s] :: multiplication
677 (new =(0 (mix (syn a) (syn b))) (mul (abs a) (abs b)))
679Examples
680--------
682 > (pro:si -4 --2)
683 -8
684 > (pro:si -4 -2)
685 --8
686 > (pro:si --10.000.000 -10)
687 -100.000.000
688 > (pro:si -1.337 --0)
689 --0
691------------------------------------------------------------------------
693### `++rem`
695Remainder
697Produces the remainder from a division of two signed integers.
699Accepts
700-------
702`a` is a `@s`.
704`b` is a `@s`.
706Produces
707--------
709A `@sd`.
711Source
712------
714 ++ rem |=([a/@s b/@s] (dif a (pro b (fra a b)))) :: remainder
716Examples
717--------
719 > (rem:si -10 -4)
720 -2
721 > (rem:si --10 --4)
722 --2
723 > (rem:si --10 -4)
724 --2
725 > (rem:si --7 --3)
726 --1
727 > (rem:si --0 --10.000)
728 --0
730------------------------------------------------------------------------
732### `++sum`
734Add
736Sum two signed integers.
738Accepts
739-------
741`b` is a `@s`.
743`c` is a signed integer `@s`.
745Produces
746--------
748A `@s`.
750Source
751------
753 ++ sum |= [a/@s b/@s] :: addition
754 ~| %si-sum
755 =+ [c=(old a) d=(old b)]
756 ?: -.c
757 ?: -.d
758 (new & (add +.c +.d))
759 ?: (gte +.c +.d)
760 (new & (sub +.c +.d))
761 (new | (sub +.d +.c))
762 ?: -.d
763 ?: (gte +.c +.d)
764 (new | (sub +.c +.d))
765 (new & (sub +.d +.c))
766 (new | (add +.c +.d))
768Examples
769--------
771 > (sum:si --10 --10)
772 --20
773 > (sum:si --10 -0)
774 --10
775 > (sum:si -10 -7)
776 -17
777 > (sum:si -10 --7)
778 -3
780------------------------------------------------------------------------
782### `++sun`
784Signed from unsigned
786Produces a signed integer from an unsigned integer.
788Note that the result must be manually cast to some `@s` odor to be
789inferred as an unsigned integer in the type system.
791Accepts
792-------
794`a` is a `@u`.
796Produces
797--------
799A `@s`.
801Source
802------
804 ++ sun |=(a/@u (mul 2 a)) :: @u to @s
806Examples
807--------
809 > `@s`10
810 --5
811 > (sun:si 10)
812 20
813 > `@s`(sun:si 10)
814 --10
815 > `@sd`(sun:si 10)
816 --10
817 > `@sd`(sun:si 12.345)
818 --12.345
820------------------------------------------------------------------------
822### `++syn`
824Sign
826Produce the sign of a signed integer, where `&` is posiitve, and `|` is negative.
828Accepts
829-------
831`a` is a `@s`.
833Produces
834--------
836A boolean.
838Source
839------
841 ++ syn |=(a/@s =(0 (end 0 1 a))) :: sign test
843Examples
844--------
846 > (syn:si -2)
847 %.n
848 > (syn:si --2)
849 %.y
850 > (syn:si -0)
851 %.y
853------------------------------------------------------------------------
855### `++cmp`
857Compare
859Compare two signed integers.
861Accepts
862-------
864`b` is a `@s`.
866`c` is a `@s`.
868Produces
869--------
871A `@s`.
873Source
874------
876 ++ cmp |= [a/@s b/@s] :: compare
877 ^- @s
878 ?: =(a b)
879 --0
880 ?: (syn a)
881 ?: (syn b)
882 ?: (gth a b)
883 --1
884 -1
885 --1
886 ?: (syn b)
887 -1
888 ?: (gth a b)
889 -1
890 --1
892Examples
893--------
895 > (cmp:si --10 --10)
896 --0
897 > (cmp:si --10 -0)
898 --1
899 > (cmp:si -10 -7)
900 -1
901 > (cmp:si -10 --7)
902 -1
905***
906### `++egcd`
908GCD
910 ++ egcd !: :: schneier's egcd
911 |= {a/@ b/@}
912 =+ si
913 =+ [c=(sun a) d=(sun b)]
914 =+ [u=[c=(sun 1) d=--0] v=[c=--0 d=(sun 1)]]
915 |- ^- {d/@ u/@s v/@s}
916 ?: =(--0 c)
917 [(abs d) d.u d.v]
918 :: ?> ?& =(c (sum (pro (sun a) c.u) (pro (sun b) c.v)))
919 :: =(d (sum (pro (sun a) d.u) (pro (sun b) d.v)))
920 :: ==
921 =+ q=(fra d c)
922 %= $
923 c (dif d (pro q c))
924 d c
925 u [(dif d.u (pro q c.u)) c.u]
926 v [(dif d.v (pro q c.v)) c.v]
927 ==
928 ::
931Greatest common denominator
933 > (egcd 20 15)
934 [d=5 u=2 v=1]
935 > (egcd 24 16)
936 [d=8 u=2 v=1]
937 > (egcd 7 5)
938 [d=1 u=3 v=6]
939 > (egcd (shaf ~ %ham) (shaf ~ %sam))
940 [ d=1
941 u=59.983.396.314.566.203.239.184.568.129.921.874.787
942 v=38.716.650.351.034.402.960.165.718.823.532.275.722
943 ]
947***