reference/library/3a.md · urbit.org

git.iko.soy/urbit.org

on b93c19b help sign in

urbit.org/reference/library/3a.md

857 lines 10 kB history raw

1+++

2title = "3a: Modular and Signed Ints"

3weight = 21

4template = "doc.html"

5+++

6# 3a: modular and signed ints

8### `++egcd`

10Extended Euclidean algorithm

12Produces `d`, the

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

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

16#### Accepts

18`a` is an atom.

20`b` is an atom.

22#### Produces

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

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

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

30#### Source

32```

33 ++ egcd

34 |= [a=@ b=@]

35 =+ si

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

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

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

39 ?: =(--0 c)

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

41 =+ q=(fra d c)

42 %= $

43 c (dif d (pro q c))

44 d c

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

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

47 ==

48```

50#### Examples

52```

53 > (egcd 11 2)

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

55```

57---

58### `++fo`

60Modulo prime

62Container core for modular arithmetic functions.

64#### Source

66```

67 ++ fo

68 ^?

69 |_ a=@

70```

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

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

103

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

105 8

106```

107

108### `++exp:fo`

109

110Exponent

111

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

114#### Accepts

116`a` is an atom.

118`b` is an atom.

120`c` is an atom.

122#### Produces

124An atom.

126#### Source

128```

129 ++ exp

130 |= [b=@ c=@]

131 ?: =(0 b)

132 1

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

134 =+ e=(pro d d)

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

136```

137

138#### Examples

139

140```

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

142 1

143

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

145 66

146

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

148 61

149

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

151 256

152```

153

154---

155### `++fra:fo`

156

157Divide

158

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

161#### Accepts

163`a` is an atom.

165`b` is an atom.

167`c` is an atom.

169#### Produces

171An atom.

173#### Accepts

175`a` is an atom.

177`b` is an atom.

179#### Source

181```

182 ++ fra

183 |= [b=@ c=@]

184 (pro b (inv c))

185```

186

187#### Examples

188

189```

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

191 0

192

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

194 1

195

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

197 0

198

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

200 4

201```

202

203---

204### `++inv:fo`

205

206Inverse

207

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

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

211#### Accepts

213`a` is an atom.

215`b` is an atom.

217#### Produces

219An atom.

221#### Source

223```

224 ++ inv

225 |= b=@

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

227 c

228```

229

230#### Examples

231

232```

233 > (~(inv fo 11) 2)

234 6

235

236 > (~(inv fo 71) 255)

237 22

238

239 > (~(inv fo 79) 255)

240 22

241

242 > (~(inv fo 78) 255)

243 67

244

245 > (~(inv fo 70) 255)

246 67

247```

248

249---

250### `++pro:fo`

251

252Multiplication

253

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

256#### Accepts

258`a` is an atom.

260`b` is an atom.

262`c` is an atom.

264#### Produces

266An atom.

268#### Source

270```

271 ++ pro

272 |= [b=@ c=@]

273 (sit (mul b c))

274```

275

276#### Examples

277

278```

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

280 2

281

282 > (mod 44 3)

283 2

284```

285

286---

287### `++sit:fo`

288

289Modulus

290

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

293#### Accepts

295`a` is an atom.

297`b` is an atom.

299#### Produces

301An atom.

303#### Source

305```

306 ++ sit

307 |= b=@

308 (mod b a)

309```

310

311#### Examples

312

313```

314 > (~(sit fo 3) 14)

315 2

316```

317

318---

319### `++sum:fo`

320

321Modular sum

322

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

325#### Accepts

327`a` is an atom.

329`b` is an atom.

331`c` is an atom.

333#### Produces

335An atom.

337#### Source

339```

340 ++ sum

341 |= [b=@ c=@]

342 (sit (add b c))

343 --

344```

345

346#### Examples

347

348```

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

350 2

351

352 > (mod 17 3)

353 2

354```

355

356---

357### `++si`

358

359Signed integer

360

361Container core for signed integer functions.

362

363#### Source

364

365```

366 ++ si

367 ^?

368 |%

369```

370

371#### Discussion

372

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

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

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

376

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

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

379minus one. For example:

380

381```

382 > `@`--4

383 8

384 > `@s`8

385 --4

386

387 > `@`-4

388 7

389 > `@s`7

390 -4

391```

392

393---

394### `++abs:si`

395

396Absolute value

397

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

399

400#### Accepts

401

402`a` is a signed integer.

404#### Produces

406An atom.

408### Source

410```

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

412```

413

414#### Examples

415

416```

417 > (abs:si -11)

418 11

419

420 > (abs:si --520)

421 520

422```

423

424---

425### `++dif:si`

426

427Subtraction

428

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

430

431#### Accepts

432

433`a` is a signed integer.

434

435`b` is a signed integer.

437#### Produces

439A signed integer.

441#### Source

443```

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

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

446```

447

448#### Examples

449

450```

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

452 --5

453

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

455 -5

456```

457

458---

459### `++dul:si`

460

461Modulus

462

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

464

465#### Examples

466

467`a` is a signed integer.

469`b` is an atom.

471#### Produces

473An atom.

475#### Source

477```

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

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

480```

481

482#### Examples

483

484```

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

486 -5

487

488 > `@`--5

489 10

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

491 -5

492

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

494 --55

495```

496

497---

498### `++fra:si`

499

500Divide

501

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

503

504#### Accepts

505

506`a` is a signed integer.

507

508`b` is a signed integer.

510#### Produces

512A signed atom.

514#### Source

516```

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

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

519```

520

521#### Examples

522

523```

524 > (fra:si -1 -1)

525 --1

526

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

528 -5

529

530 > (fra:si -0 -1)

531 --0

532```

533

534---

535### `++new:si`

536

537Atom to @s

538

539Produces a signed integer from an atom `b`. The product's sign is determined

540by the value of flag `a`: `&` will result in a prepending `--`, and `|` will

541result in a prepending `-`.

543#### Accepts

545`a` is a flag.

547`b` is an atom.

549#### Produces

551A signed integer.

553#### Source

555```

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

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

558```

559

560#### Examples

561

562```

563 > (new:si | 2)

564 -2

565

566 > (new:si & 2)

567 --2

568

569 > (new:si & -2)

570 --3

571

572 > (new:si & --2)

573 --4

574```

575

576---

577### `++old:si`

578

579Sign and absolute value

580

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

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

583

584#### Accepts

585

586`a` is a signed integer.

587

588#### Produces

589

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

591

592#### Source

593

594```

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

596```

597

598#### Examples

599

600```

601 > (old:si -2)

602 [%.n 2]

603

604 > (old:si --2)

605 [%.y 2]

606```

607

608---

609### `++pro:si`

610

611Multiplication

612

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

614

615#### Accepts

616

617`a` is an unsigned integer.

618

619`b` is an unsigned integer.

620

621#### Source

622

623```

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

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

626```

627

628#### Examples

629

630```

631 > (pro:si -3 -3)

632 --9

633

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

635 -9

636```

637

638---

639### `++rem:si`

640

641Remainder

642

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

644

645#### Accepts

646

647`a` is a signed integer.

648

649`b` is a signed integer.

651#### Produces

653A signed integer.

655#### Source

657```

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

659```

660

661#### Examples

662

663```

664 > (rem:si -17 -3)

665 -2

666

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

668 --2

669

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

671 -2

672

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

674 --2

675```

676

677

678---

679### `++sum:si`

680

681Addition

682

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

684

685#### Accepts

686

687`a` is a signed integer.

688

689`b` is a signed integer.

691#### Produces

693A signed integer.

695#### Source

697```

698 ++ sum |= [a=@s b=@s]

699 =+ [c=(old a) d=(old b)]

700 ?: -.c

701 ?: -.d

702 (new & (add +.c +.d))

703 ?: (gte +.c +.d)

704 (new & (sub +.c +.d))

705 (new | (sub +.d +.c))

706 ?: -.d

707 ?: (gte +.c +.d)

708 (new | (sub +.c +.d))

709 (new & (sub +.d +.c))

710 (new | (add +.c +.d))

711```

712

713#### Examples

714

715```

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

717 -9

718

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

720 --4

721```

722

723---

724### `++sun:si`

725

726@u to @s

727

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

729

730#### Accepts

731

732`a` is an unsigned integer.

734#### Produces

736An atom.

738#### Source

740```

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

742```

743

744#### Examples

745

746```

747 > (sun:si 90)

748 180

749

750 > (sun:si --90)

751 360

752 > `@u`--90

753 180

754

755 > (sun:si --89)

756 356

757 > `@u`--89

758 178

759

760 > (sun:si -89)

761 354

762 > `@u`-89

763 177

764```

765

766---

767### `++syn:si`

768

769Sign test

770

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

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

773

774#### Accepts

775

776`a` is a signed integer.

778#### Produces

780An `term`.

782#### Source

784```

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

786```

787

788#### Examples

789

790```

791 > (syn:si -2)

792 %.n

793

794 > (syn:si --2)

795 %.y

796```

797

798---

799### `++cmp:si`

800

801Compare

802

803Compares `a` and `b` to see which is greater. If `a` is greater than `b`, `--1`

804is produced. If `b` is greater than `a`, `-1` is produced. If `a` and `b` are

805equal, `--0` is produced.

806

807#### Accepts

808

809`a` is a signed integer.

810

811`b` is a signed integer.

813#### Produces

815A signed integer.

817#### Source

819```

820 ++ cmp |= [a=@s b=@s]

821 ^- @s

822 ?: =(a b)

823 --0

824 ?: (syn a)

825 ?: (syn b)

826 ?: (gth a b)

827 --1

828 -1

829 --1

830 ?: (syn b)

831 -1

832 ?: (gth a b)

833 -1

834 --1

835 --

836```

837

838#### Examples

839

840```

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

842 -1

843

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

845 -1

846

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

848 --1

849

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

851 --0

852

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

854 -1

855```

856

857---