docs/reference/library/3a.udon · urbit.org

git.iko.soy/urbit.org

on c19bc7a help sign in

urbit.org/docs/reference/library/3a.udon

859 lines 10 kB history raw

1:- :~ navhome/'/docs/'

2 sort/'21'

3 title/'3a: Modular and Signed Ints'

4 ==

6;>

8# 3a: modular and signed ints

10### `++egcd`

12Extended Euclidean algorithm

14Produces `d`, the

15[greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor)

16of `a` and `b`. Also produces `u` and `v` such that `au + bv = GCD(a, b)`.

18#### Accepts

20`a` is an atom.

22`b` is an atom.

24#### Produces

26`d`, the greatest common divisor, is an atom.

28`u`, the coefficient of `a`, is a signed integer.

30`v`, the coefficient of `b`, is a signed integer.

32#### Source

34```

35 ++ egcd

36 |= [a=@ b=@]

37 =+ si

38 =+ [c=(sun a) d=(sun b)]

39 =+ [u=[c=(sun 1) d=--0] v=[c=--0 d=(sun 1)]]

40 |- ^- [d=@ u=@s v=@s]

41 ?: =(--0 c)

42 [(abs d) d.u d.v]

43 =+ q=(fra d c)

44 %= $

45 c (dif d (pro q c))

46 d c

47 u [(dif d.u (pro q c.u)) c.u]

48 v [(dif d.v (pro q c.v)) c.v]

49 ==

50```

52#### Examples

54```

55 > (egcd 11 2)

56 [d=1 u=--1 v=-5]

57```

59---

60### `++fo`

62Modulo prime

64Container core for modular arithmetic functions.

66#### Source

68```

69 ++ fo

70 ^?

71 |_ a=@

72```

74#### `++dif`

76Subtraction

78Produces the difference between atoms `b` and `c`, with `a` as the modular base.

80#### Accepts

82`a` is an atom.

84`b` is an atom.

86`c` is an atom.

88#### Produces

90An atom.

92#### Source

94```

95 ++ dif

96 |= [b=@ c=@]

97 (sit (sub (add a b) (sit c)))

98```

100#### Examples

101

102```

103 > (~(dif fo 6) 1 2)

104 5

105

106 > (~(dif fo 21) 11 45)

107 8

108```

109

110#### `++exp`

111

112Exponent

113

114Produces the power of `b` raised to the `c`, with `a` as the modular base.

116#### Accepts

118`a` is an atom.

120`b` is an atom.

122`c` is an atom.

124#### Produces

126An atom.

128#### Source

130```

131 ++ exp

132 |= [b=@ c=@]

133 ?: =(0 b)

134 1

135 =+ d=$(b (rsh 0 1 b))

136 =+ e=(pro d d)

137 ?:(=(0 (end 0 1 b)) e (pro c e))

138```

139

140#### Examples

141

142```

143 > (~(exp fo 5) 8 2)

144 1

145

146 > (~(exp fo 95) 8 2)

147 66

148

149 > (~(exp fo 195) 8 2)

150 61

151

152 > (~(exp fo 995) 8 2)

153 256

154```

155

156---

157### `++fra`

158

159Divide

160

161Produces the quotient of `b` divided by `c`, with `a` as the modular base.

163#### Accepts

165`a` is an atom.

167`b` is an atom.

169`c` is an atom.

171#### Produces

173An atom.

175#### Accepts

177`a` is an atom.

179`b` is an atom.

181#### Source

183```

184 ++ fra

185 |= [b=@ c=@]

186 (pro b (inv c))

187```

188

189#### Examples

190

191```

192 > (~(fra fo 2) 8 2)

193 0

194

195 > (~(fra fo 3) 8 2)

196 1

197

198 > (~(fra fo 4) 8 2)

199 0

200

201 > (~(fra fo 5) 8 2)

202 4

203```

204

205---

206### `++inv`

207

208Inverse

209

210Produces an atom by taking the signed modulus of `a` with the coefficient `u`;

211`u` is produced by taking the `++egcd` of `a` and `b`.

213#### Accepts

215`a` is an atom.

217`b` is an atom.

219#### Produces

221An atom.

223#### Source

225```

226 ++ inv

227 |= b=@

228 =+ c=(dul:si u:(egcd b a) a)

229 c

230```

231

232#### Examples

233

234```

235 > (~(inv fo 11) 2)

236 6

237

238 > (~(inv fo 71) 255)

239 22

240

241 > (~(inv fo 79) 255)

242 22

243

244 > (~(inv fo 78) 255)

245 67

246

247 > (~(inv fo 70) 255)

248 67

249```

250

251---

252### `++pro`

253

254Multiplication

255

256Produces the multiplication of `b` and `c` modulo `a`.

258#### Accepts

260`a` is an atom.

262`b` is an atom.

264`c` is an atom.

266#### Produces

268An atom.

270#### Source

272```

273 ++ pro

274 |= [b=@ c=@]

275 (sit (mul b c))

276```

277

278#### Examples

279

280```

281 > (~(pro fo 3) 11 4)

282 2

283

284 > (mod 44 3)

285 2

286```

287

288---

289### `++sit`

290

291Modulus

292

293Produces the remainder of `b` modulo `a`.

295#### Accepts

297`a` is an atom.

299`b` is an atom.

301#### Produces

303An atom.

305#### Source

307```

308 ++ sit

309 |= b=@

310 (mod b a)

311```

312

313#### Examples

314

315```

316 > (~(sit fo 3) 14)

317 2

318```

319

320---

321### `++sum`

322

323Modular sum

324

325Produces the remainder of `(b + c) mod a`.

327#### Accepts

329`a` is an atom.

331`b` is an atom.

333`c` is an atom.

335#### Produces

337An atom.

339#### Source

341```

342 ++ sum

343 |= [b=@ c=@]

344 (sit (add b c))

345 --

346```

347

348#### Examples

349

350```

351 > (~(sum fo 3) 14 3)

352 2

353

354 > (mod 17 3)

355 2

356```

357

358---

359### `++si`

360

361Signed integer

362

363Container core for signed integer functions.

364

365#### Source

366

367```

368 ++ si

369 ^?

370 |%

371```

372

373#### Discussion

374

375The signed-integer type is represented by the `@s` aura. Positive integers are

376represented with a two prepending `-`s, and negative integers are represented

377with two; `--1` and `-1`, respectively.

378

379Positive signed integers correspond to odd atoms of twice their absolute value,

380and negative signed integers correspond to atoms of twice their absolute value

381minus one. For example:

382

383```

384 > `@`--4

385 8

386 > `@s`8

387 --4

388

389 > `@`-4

390 7

391 > `@s`7

392 -4

393```

394

395---

396### `++abs:si`

397

398Absolute value

399

400Produces the absolute value of signed integer `a`.

401

402#### Accepts

403

404`a` is a signed integer.

406#### Produces

408An atom.

410### Source

412```

413 ++ abs |=(a=@s (add (end 0 1 a) (rsh 0 1 a)))

414```

415

416#### Examples

417

418```

419 > (abs:si -11)

420 11

421

422 > (abs:si --520)

423 520

424```

425

426---

427### `++dif:si`

428

429Subtraction

430

431Produces the difference of `a` minus `b`.

432

433#### Accepts

434

435`a` is a signed integer.

436

437`b` is a signed integer.

439#### Produces

441A signed integer.

443#### Source

445```

446 ++ dif |= [a=@s b=@s]

447 (sum a (new !(syn b) (abs b)))

448```

449

450#### Examples

451

452```

453 > (dif:si --3 -2)

454 --5

455

456 > (dif:si -3 --2)

457 -5

458```

459

460---

461### `++dul:si`

462

463Modulus

464

465Produces the remainder of `b` modulo `a`.

466

467#### Examples

468

469`a` is a signed integer.

471`b` is an atom.

473#### Produces

475An atom.

477#### Source

479```

480 ++ dul |= [a=@s b=@]

481 =+(c=(old a) ?:(-.c (mod +.c b) (sub b +.c)))

482```

483

484#### Examples

485

486```

487 > `@s`(dul:si -1 --5)

488 -5

489

490 > `@`--5

491 10

492 > `@s`(dul:si -1 10)

493 -5

494

495 > `@s`(dul:si -11 -61)

496 --55

497```

498

499---

500#### `++fra:si`

501

502Divide

503

504Produces the quotient of `b` divided by `c`.

505

506#### Accepts

507

508`a` is a signed integer.

509

510`b` is a signed integer.

512#### Produces

514A signed atom.

516#### Source

518```

519 ++ fra |= [a=@s b=@s]

520 (new =(0 (mix (syn a) (syn b))) (div (abs a) (abs b)))

521```

522

523#### Examples

524

525```

526 > (fra:si -1 -1)

527 --1

528

529 > (fra:si -11 --2)

530 -5

531

532 > (fra:si -0 -1)

533 --0

534```

535

536---

537### `++new`

538

539Atom to @s

540

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```

558 ++ new |= [a=? b=@]

559 `@s`?:(a (mul 2 b) ?:(=(0 b) 0 +((mul 2 (dec b)))))

560```

561

562#### Examples

563

564```

565 > (new:si | 2)

566 -2

567

568 > (new:si & 2)

569 --2

570

571 > (new:si & -2)

572 --3

573

574 > (new:si & --2)

575 --4

576```

577

578---

579### `++old:si`

580

581Sign and absolute value

582

583Produces a cell composed of a `%.y` or `%.n`, depending on whether `a` is

584positive or negative, and the absolute value of `a`.

585

586#### Accepts

587

588`a` is a signed integer.

589

590#### Produces

591

592A cell composed of a `term` and an atom.

593

594#### Source

595

596```

597 ++ old |=(a=@s [(syn a) (abs a)])

598```

599

600#### Examples

601

602```

603 > (old:si -2)

604 [%.n 2]

605

606 > (old:si --2)

607 [%.y 2]

608```

609

610---

611### `++pro`

612

613Multiplication

614

615Produces a signed integer by multiplying `a` and `b`.

616

617#### Accepts

618

619`a` is an unsigned integer.

620

621`b` is an unsigned integer.

622

623#### Source

624

625```

626 ++ pro |= [a=@s b=@s]

627 (new =(0 (mix (syn a) (syn b))) (mul (abs a) (abs b)))

628```

629

630#### Examples

631

632```

633 > (pro:si -3 -3)

634 --9

635

636 > (pro:si -3 --3)

637 -9

638```

639

640---

641### `++rem:si`

642

643Remainder

644

645Produces a signed integer that is the remainder of `a` divided by `b`.

646

647#### Accepts

648

649`a` is a signed integer.

650

651`b` is a signed integer.

653#### Produces

655A signed integer.

657#### Source

659```

660 ++ rem |=([a=@s b=@s] (dif a (pro b (fra a b))))

661```

662

663#### Examples

664

665```

666 > (rem:si -17 -3)

667 -2

668

669 > (rem:si --17 -3)

670 --2

671

672 > (rem:si -17 --3)

673 -2

674

675 > (rem:si --17 --3)

676 --2

677```

678

679

680---

681### `++sum:si`

682

683Addition

684

685Produces an atom by adding `a` and `b`.

686

687#### Accepts

688

689`a` is a signed integer.

690

691`b` is a signed integer.

693#### Produces

695A signed integer.

697#### Source

699```

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```

714

715#### Examples

716

717```

718 > (sum:si -11 --2)

719 -9

720

721 > (sum:si --2 --2)

722 --4

723```

724

725---

726#### `++sun:si`

727

728@u to @s

729

730Multiplies the unsigned integer `a` by two, producing an atom.

731

732#### Accepts

733

734`a` is an unsigned integer.

736#### Produces

738An atom.

740#### Source

742```

743 ++ sun |=(a=@u (mul 2 a))

744```

745

746#### Examples

747

748```

749 > (mul 2 90)

750 180

751

752 > (mul 2 --90)

753 360

754 > `@u`--90

755 180

756

757 > (mul 2 --89)

758 356

759 > `@u`--89

760 178

761

762 > (mul 2 -89)

763 354

764 > `@u`-89

765 177

766```

767

768---

769### `++syn:si`

770

771Sign test

772

773Tests whether signed atom `a` is positive or negative. `%.y` is produced if `a`

774is positive, and `%.n` is produced if `a` is negative.

775

776#### Accepts

777

778`a` is a signed integer.

780#### Produces

782An `term`.

784#### Source

786```

787 ++ syn |=(a=@s =(0 (end 0 1 a)))

788```

789

790#### Examples

791

792```

793 > (syn:si -2)

794 %.n

795

796 > (syn:si --2)

797 %.y

798```

799

800---

801### `++cmp:si`

802

803Compare

804

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.

808

809#### Accepts

810

811`a` is a signed integer.

812

813`b` is a signed integer.

815#### Produces

817A signed integer.

819#### Source

821```

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```

839

840#### Examples

841

842```

843 > (cmp:si -2 --1)

844 -1

845

846 > (cmp:si -2 --1)

847 -1

848

849 > (cmp:si --2 --1)

850 --1

851

852 > (cmp:si --2 --2)

853 --0

854

855 > (cmp:si --2 --5)

856 -1

857```

858

859---