git.iko.soy/urbit.org
on 657b415 help sign in
urbit.org/docs/programming/reference/library/3a.md
942 lines 14 kB history raw
1# 3a: signed and modular ints
2### `++fe` :: modulo bloq
4Modulo bloq
6Core containing XX
8Accepts
9-------
11`a` is a `++bloq`.
13Source
14------
16 |_ a=bloq
18### `++dif`
20Produces the difference between two atoms in the modular basis
21representation.
23Accepts
24-------
26`a` is a `++bloq`.
28`b` is an atom.
30`c` is an atom.
32Produces
33--------
35A `@s`
37Source
38------
40 ++ dif |=([b/@ c/@] (sit (sub (add out (sit b)) (sit c))))
42Examples
43--------
45 > (~(dif fe 3) 63 64)
46 255
47 > (~(dif fe 3) 5 10)
48 251
49 > (~(dif fe 3) 0 1)
50 255
51 > (~(dif fe 0) 9 10)
52 1
53 > (~(dif fe 0) 9 11)
54 0
55 > (~(dif fe 0) 9 12)
56 1
57 > (~(dif fe 2) 9 12)
58 13
59 > (~(dif fe 2) 63 64)
60 15
62------------------------------------------------------------------------
64### `++inv`
66Invert mod field
68Inverts the order of the modular field.
70Accepts
71-------
73`b` is a `++bloq`.
75Produces
76--------
78An atom.
81Source
82------
84 ++ inv |=(b/@ (sub (dec out) (sit b)))
86Examples
87--------
89 > (~(inv fe 3) 255)
90 0
91 > (~(inv fe 3) 256)
92 255
93 > (~(inv fe 3) 0)
94 255
95 > (~(inv fe 3) 1)
96 254
97 > (~(inv fe 3) 2)
98 253
99 > (~(inv fe 3) 55)
100 200
102------------------------------------------------------------------------
104### `++net`
106Reverse bytes
108Revereses bytes within block.
110Accepts
111-------
113`b` is a `++bloq`.
115Produces
116--------
118An atom.
120Source
121------
123 ++ net |= b/@ ^- @
124 => .(b (sit b))
125 ?: (lte a 3)
126 b
127 =+ c=(dec a)
128 %+ con
129 (lsh c 1 $(a c, b (cut c [0 1] b)))
130 $(a c, b (cut c [1 1] b))
132Examples
133--------
135 > (~(net fe 3) 64)
136 64
137 > (~(net fe 3) 128)
138 128
139 > (~(net fe 3) 255)
140 255
141 > (~(net fe 3) 256)
142 0
143 > (~(net fe 3) 257)
144 1
145 > (~(net fe 3) 500)
146 244
147 > (~(net fe 3) 511)
148 255
149 > (~(net fe 3) 512)
150 0
151 > (~(net fe 3) 513)
152 1
153 > (~(net fe 3) 0)
154 0
155 > (~(net fe 3) 1)
156 1
157 > (~(net fe 0) 1)
158 1
159 > (~(net fe 0) 2)
160 0
161 > (~(net fe 0) 3)
162 1
163 > (~(net fe 6) 1)
164 72.057.594.037.927.936
165 > (~(net fe 6) 2)
166 144.115.188.075.855.872
167 > (~(net fe 6) 3)
168 216.172.782.113.783.808
169 > (~(net fe 6) 4)
170 288.230.376.151.711.744
171 > (~(net fe 6) 5)
172 360.287.970.189.639.680
173 > (~(net fe 6) 6)
174 432.345.564.227.567.616
175 > (~(net fe 6) 7)
176 504.403.158.265.495.552
177 > (~(net fe 6) 512)
178 562.949.953.421.312
179 > (~(net fe 6) 513)
180 72.620.543.991.349.248
182------------------------------------------------------------------------
184### `++out`
186Max integer value
188The maximum integer value that the current block can store.
190Accepts
191-------
193A `++bloq`.
195Produces
196--------
198An atom.
200Source
201------
203 ++ out (bex (bex a))
205Examples
206--------
208 > ~(out fe 0)
209 2
210 > ~(out fe 1)
211 4
212 > ~(out fe 2)
213 16
214 > ~(out fe 3)
215 256
216 > ~(out fe 4)
217 65.536
218 > ~(out fe 10)
219 \/179.769.313.486.231.590.772.930.519.078.902.473.361.797.697.894.230.657.\/
220 273.430.081.157.732.675.805.500.963.132.708.477.322.407.536.021.120.113.
221 879.871.393.357.658.789.768.814.416.622.492.847.430.639.474.124.377.767.
222 893.424.865.485.276.302.219.601.246.094.119.453.082.952.085.005.768.838.
223 150.682.342.462.881.473.913.110.540.827.237.163.350.510.684.586.298.239.
224 947.245.938.479.716.304.835.356.329.624.224.137.216
225 \/ \/
227------------------------------------------------------------------------
229### `++rol`
231Roll left
233Roll `d` to the left by `c` `b`-sized blocks.
235Accepts
236-------
238`a` is a `++bloq`.
240`b` is a `++bloq`.
242`c` is an atom.
244`d` is an atom.
246Produces
247--------
249An atom.
251Source
252------
254 ++ rol |= [b/bloq c/@ d/@] ^- @ :: roll left
255 =+ e=(sit d)
256 =+ f=(bex (sub a b))
257 =+ g=(mod c f)
258 (sit (con (lsh b g e) (rsh b (sub f g) e)))
260Examples
261--------
263 > `@ux`(~(rol fe 6) 4 3 0xabac.dedf.1213)
264 0x1213.0000.abac.dedf
265 > `@ux`(~(rol fe 6) 4 2 0xabac.dedf.1213)
266 0xdedf.1213.0000.abac
267 > `@t`(~(rol fe 5) 3 1 'dfgh')
268 'hdfg'
269 > `@t`(~(rol fe 5) 3 2 'dfgh')
270 'ghdf'
271 > `@t`(~(rol fe 5) 3 0 'dfgh')
272 'dfgh'
274------------------------------------------------------------------------
276### `++ror`
278Roll right
280Roll `d` to the right by `c` `b`-sized blocks.
282Accepts
283-------
285`a` is a `++bloq`.
287`b` is a `++bloq`.
289`c` is an atom.
291`d` is an atom.
293Produces
294--------
296An atom.
298Source
299------
301 ++ ror |= {b/bloq c/@ d/@} ^- @ :: roll right
302 =+ e=(sit d)
303 =+ f=(bex (sub a b))
304 =+ g=(mod c f)
305 (sit (con (rsh b g e) (lsh b (sub f g) e)))
308Examples
309--------
311 > `@ux`(~(ror fe 6) 4 1 0xabac.dedf.1213)
312 0x1213.0000.abac.dedf
313 > `@ux`(~(ror fe 6) 3 5 0xabac.dedf.1213)
314 0xacde.df12.1300.00ab
315 > `@ux`(~(ror fe 6) 3 3 0xabac.dedf.1213)
316 0xdf12.1300.00ab.acde
317 > `@t`(~(rol fe 5) 3 0 'hijk')
318 'hijk'
319 > `@t`(~(rol fe 5) 3 1 'hijk')
320 'khij'
321 > `@t`(~(rol fe 5) 3 2 'hijk')
322 'jkhi'
324------------------------------------------------------------------------
326### `++sum`
328Sum
330Sum two numbers in this modular field.
332Accepts
333-------
335`a` is a `++bloq`.
337`b` is an atom.
339`c` is an atom.
341Produces
342--------
344An atom.
346Source
347------
349 ++ sum |=([b/@ c/@] (sit (add b c))) :: wrapping add
351Examples
352--------
354 > (~(sum fe 3) 10 250)
355 4
356 > (~(sum fe 0) 0 1)
357 1
358 > (~(sum fe 0) 0 2)
359 0
360 > (~(sum fe 2) 14 2)
361 0
362 > (~(sum fe 2) 14 3)
363 1
364 > (~(sum fe 4) 10.000 256)
365 10.256
366 > (~(sum fe 4) 10.000 100.000)
367 44.464
369### `++sit`
371Atom in mod block representation
373Produce an atom in the current modular block representation.
375Accepts
376-------
378`a` is a `++bloq`.
380`b` is an atom.
382Produces
383--------
385An atom.
387Source
388------
390 ++ sit |=(b/@ (end a 1 b)) :: enforce modulo
392Examples
393--------
395 > (~(sit fe 3) 255)
396 255
397 > (~(sit fe 3) 256)
398 0
399 > (~(sit fe 3) 257)
400 1
401 > (~(sit fe 2) 257)
402 1
403 > (~(sit fe 2) 10.000)
404 0
405 > (~(sit fe 2) 100)
406 4
407 > (~(sit fe 2) 19)
408 3
409 > (~(sit fe 2) 17)
410 1
411 > (~(sit fe 0) 17)
412 1
413 > (~(sit fe 0) 0)
414 0
415 > (~(sit fe 0) 1)
416 1
420***
421### `++si`
423 ++ si !: :: signed integer
424 |%
426Container core for the signed integer functions.
428------------------------------------------------------------------------
430### `++abs`
432Absolute value
434Produces the absolute value of a signed integer.
436Accepts
437-------
439`a` is a signed integer, `@s`.
441Produces
442--------
444An atom.
446Source
447------
449 ++ abs |=(a/@s (add (end 0 1 a) (rsh 0 1 a))) :: absolute value
451Examples
452--------
454 > (abs:si -2)
455 2
456 > (abs:si -10.000)
457 10.000
458 > (abs:si --2)
459 2
461------------------------------------------------------------------------
463### `++dif`
465Difference
467Produces the difference between two signed integers `b` and `c`.
469Accepts
470-------
472`a` is a signed integer, `@s`.
474`b` is a signed integer, `@s`.
476Produces
477--------
479A `@s`.
482Source
483------
485 ++ dif |= [a/@s b/@s] :: subtraction
486 (sum a (new !(syn b) (abs b)))
488Examples
489--------
491 > (dif:si --10 -7)
492 --17
493 > (dif:si --10 --7)
494 --3
495 > (dif:si `@s`0 --7)
496 -7
497 > (dif:si `@s`0 `@s`7)
498 --4
500------------------------------------------------------------------------
502### `++dul`
504Modulus
506Produces the modulus of two signed integers.
508Accepts
509-------
511`a` is a signed integer, `@s`.
513`b` is an atom.
515Produces
516--------
518An atom.
520Source
521------
523 ++ dul |= [a/@s b/@] :: modulus
524 =+(c=(old a) ?:(-.c (mod +.c b) (sub b +.c)))
526Examples
527--------
529 > (dul:si --9 3)
530 0
531 > (dul:si --9 4)
532 1
533 > (dul:si --9 5)
534 4
535 > (dul:si --9 6)
536 3
537 > (dul:si --90 --10)
538 10
540------------------------------------------------------------------------
542### `++fra`
544Divide
546Produces the quotient of two signed integers.
548Accepts
549-------
551`a` is a signed integer, `@s`.
553`b` is a signed integer, `@s`.
555Produces
556--------
558An atom.
560Source
561------
563 ++ fra |= [a/@s b/@s] :: divide
564 (new =(0 (mix (syn a) (syn b))) (div (abs a) (abs b)))
566Examples
567--------
569 > (fra:si --10 -2)
570 -5
571 > (fra:si -20 -5)
572 --4
574------------------------------------------------------------------------
576### `++new`
578Signed integer
580Produces a signed integer from a loobean sign value `a` and an atom `b`.
582Accepts
583-------
585`a` is a loobean.
587`b` is an atom.
589Produces
590--------
592A `@s`
594Source
595------
597 ++ new |= [a/? b/@] :: [sign value] to @s
598 `@s`?:(a (mul 2 b) ?:(=(0 b) 0 +((mul 2 (dec b)))))
600Examples
601--------
603 > (new:si [& 10])
604 --10
605 > (new:si [| 10])
606 -10
607 > (new:si [%.y 7])
608 --7
610------------------------------------------------------------------------
612### `++old`
614sign value
616Produces the cell `[sign value]` representations of a signed integer.
618Accepts
619-------
621`a` is a `@s`.
623Produces
624--------
626A cell of a boolean and an atom.
628Source
629------
631 ++ old |=(a/@s [(syn a) (abs a)]) :: [sign value]
633Examples
634--------
636 > (old:si 7)
637 ! type-fail
638 ! exit
639 > (old:si -7)
640 [%.n 7]
641 > (old:si --7)
642 [%.y 7]
643 > (old:si `@s`7)
644 [%.n 4]
645 > (old:si -0)
646 [%.y 0]
648------------------------------------------------------------------------
650### `++pro`
652Multiply
654Produces the product of two signed integers.
656Accepts
657-------
659`a` is a `@s`.
661`b` is a `@s`.
663Produces
664--------
666A `@s`.
668Source
669------
671 ++ pro |= [a/@s b/@s] :: multiplication
672 (new =(0 (mix (syn a) (syn b))) (mul (abs a) (abs b)))
674Examples
675--------
677 > (pro:si -4 --2)
678 -8
679 > (pro:si -4 -2)
680 --8
681 > (pro:si --10.000.000 -10)
682 -100.000.000
683 > (pro:si -1.337 --0)
684 --0
686------------------------------------------------------------------------
688### `++rem`
690Remainder
692Produces the remainder from a division of two signed integers.
694Accepts
695-------
697`a` is a `@s`.
699`b` is a `@s`.
701Produces
702--------
704A `@sd`.
706Source
707------
709 ++ rem |=([a/@s b/@s] (dif a (pro b (fra a b)))) :: remainder
711Examples
712--------
714 > (rem:si -10 -4)
715 -2
716 > (rem:si --10 --4)
717 --2
718 > (rem:si --10 -4)
719 --2
720 > (rem:si --7 --3)
721 --1
722 > (rem:si --0 --10.000)
723 --0
725------------------------------------------------------------------------
727### `++sum`
729Add
731Sum two signed integers.
733Accepts
734-------
736`b` is a `@s`.
738`c` is a signed integer `@s`.
740Produces
741--------
743A `@s`.
745Source
746------
748 ++ sum |= [a/@s b/@s] :: addition
749 ~| %si-sum
750 =+ [c=(old a) d=(old b)]
751 ?: -.c
752 ?: -.d
753 (new & (add +.c +.d))
754 ?: (gte +.c +.d)
755 (new & (sub +.c +.d))
756 (new | (sub +.d +.c))
757 ?: -.d
758 ?: (gte +.c +.d)
759 (new | (sub +.c +.d))
760 (new & (sub +.d +.c))
761 (new | (add +.c +.d))
763Examples
764--------
766 > (sum:si --10 --10)
767 --20
768 > (sum:si --10 -0)
769 --10
770 > (sum:si -10 -7)
771 -17
772 > (sum:si -10 --7)
773 -3
775------------------------------------------------------------------------
777### `++sun`
779Signed from unsigned
781Produces a signed integer from an unsigned integer.
783Note that the result must be manually cast to some `@s` odor to be
784inferred as an unsigned integer in the type system.
786Accepts
787-------
789`a` is a `@u`.
791Produces
792--------
794A `@s`.
796Source
797------
799 ++ sun |=(a/@u (mul 2 a)) :: @u to @s
801Examples
802--------
804 > `@s`10
805 --5
806 > (sun:si 10)
807 20
808 > `@s`(sun:si 10)
809 --10
810 > `@sd`(sun:si 10)
811 --10
812 > `@sd`(sun:si 12.345)
813 --12.345
815------------------------------------------------------------------------
817### `++syn`
819Sign
821Produce the sign of a signed integer, where `&` is posiitve, and `|` is negative.
823Accepts
824-------
826`a` is a `@s`.
828Produces
829--------
831A boolean.
833Source
834------
836 ++ syn |=(a/@s =(0 (end 0 1 a))) :: sign test
838Examples
839--------
841 > (syn:si -2)
842 %.n
843 > (syn:si --2)
844 %.y
845 > (syn:si -0)
846 %.y
848------------------------------------------------------------------------
850### `++cmp`
852Compare
854Compare two signed integers.
856Accepts
857-------
859`b` is a `@s`.
861`c` is a `@s`.
863Produces
864--------
866A `@s`.
868Source
869------
871 ++ cmp |= [a/@s b/@s] :: compare
872 ^- @s
873 ?: =(a b)
874 --0
875 ?: (syn a)
876 ?: (syn b)
877 ?: (gth a b)
878 --1
879 -1
880 --1
881 ?: (syn b)
882 -1
883 ?: (gth a b)
884 -1
885 --1
887Examples
888--------
890 > (cmp:si --10 --10)
891 --0
892 > (cmp:si --10 -0)
893 --1
894 > (cmp:si -10 -7)
895 -1
896 > (cmp:si -10 --7)
897 -1
900***
901### `++egcd`
903GCD
905 ++ egcd !: :: schneier's egcd
906 |= {a/@ b/@}
907 =+ si
908 =+ [c=(sun a) d=(sun b)]
909 =+ [u=[c=(sun 1) d=--0] v=[c=--0 d=(sun 1)]]
910 |- ^- {d/@ u/@s v/@s}
911 ?: =(--0 c)
912 [(abs d) d.u d.v]
913 :: ?> ?& =(c (sum (pro (sun a) c.u) (pro (sun b) c.v)))
914 :: =(d (sum (pro (sun a) d.u) (pro (sun b) d.v)))
915 :: ==
916 =+ q=(fra d c)
917 %= $
918 c (dif d (pro q c))
919 d c
920 u [(dif d.u (pro q c.u)) c.u]
921 v [(dif d.v (pro q c.v)) c.v]
922 ==
923 ::
926Greatest common denominator
928 > (egcd 20 15)
929 [d=5 u=2 v=1]
930 > (egcd 24 16)
931 [d=8 u=2 v=1]
932 > (egcd 7 5)
933 [d=1 u=3 v=6]
934 > (egcd (shaf ~ %ham) (shaf ~ %sam))
935 [ d=1
936 u=59.983.396.314.566.203.239.184.568.129.921.874.787
937 v=38.716.650.351.034.402.960.165.718.823.532.275.722
938 ]
942***