content/docs/hoon/reference/stdlib/3a.md · urbit.org

git.iko.soy/urbit.org

on 3869731 help sign in

urbit.org/content/docs/hoon/reference/stdlib/3a.md

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

58## `++fo`

60Modulo prime

62Container core for modular arithmetic functions.

64#### Source

66```hoon

67 ++ fo

68 ^?

69 |_ a=@

70```

72---

74### `++dif:fo`

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

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

110---

112### `++exp:fo`

114Exponent

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

118#### Accepts

120`a` is an atom.

122`b` is an atom.

124`c` is an atom.

126#### Produces

128An atom.

130#### Source

132```hoon

133 ++ exp

134 |= [b=@ c=@]

135 ?: =(0 b)

136 1

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

138 =+ e=(pro d d)

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

140```

141

142#### Examples

143

144```

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

146 1

147

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

149 66

150

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

152 61

153

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

155 256

156```

158---

160### `++fra:fo`

162Divide

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

166#### Accepts

168`a` is an atom.

170`b` is an atom.

172`c` is an atom.

174#### Produces

176An atom.

178#### Accepts

180`a` is an atom.

182`b` is an atom.

184#### Source

186```hoon

187 ++ fra

188 |= [b=@ c=@]

189 (pro b (inv c))

190```

191

192#### Examples

193

194```

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

196 0

197

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

199 1

200

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

202 0

203

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

205 4

206```

208---

210### `++inv:fo`

212Inverse

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

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

217#### Accepts

219`a` is an atom.

221`b` is an atom.

223#### Produces

225An atom.

227#### Source

229```hoon

230 ++ inv

231 |= b=@

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

233 c

234```

235

236#### Examples

237

238```

239 > (~(inv fo 11) 2)

240 6

241

242 > (~(inv fo 71) 255)

243 22

244

245 > (~(inv fo 79) 255)

246 22

247

248 > (~(inv fo 78) 255)

249 67

250

251 > (~(inv fo 70) 255)

252 67

253```

255---

257### `++pro:fo`

259Multiplication

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

263#### Accepts

265`a` is an atom.

267`b` is an atom.

269`c` is an atom.

271#### Produces

273An atom.

275#### Source

277```hoon

278 ++ pro

279 |= [b=@ c=@]

280 (sit (mul b c))

281```

282

283#### Examples

284

285```

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

287 2

288

289 > (mod 44 3)

290 2

291```

293---

295### `++sit:fo`

297Modulus

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

301#### Accepts

303`a` is an atom.

305`b` is an atom.

307#### Produces

309An atom.

311#### Source

313```hoon

314 ++ sit

315 |= b=@

316 (mod b a)

317```

318

319#### Examples

320

321```

322 > (~(sit fo 3) 14)

323 2

324```

326---

328### `++sum:fo`

330Modular sum

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

334#### Accepts

336`a` is an atom.

338`b` is an atom.

340`c` is an atom.

342#### Produces

344An atom.

346#### Source

348```hoon

349 ++ sum

350 |= [b=@ c=@]

351 (sit (add b c))

352 --

353```

354

355#### Examples

356

357```

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

359 2

360

361 > (mod 17 3)

362 2

363```

365---

367## `++si`

369Signed integer

371Container core for signed integer functions.

372

373#### Source

374

375```hoon

376 ++ si

377 ^?

378 |%

379```

380

381#### Discussion

382

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

384prepended with a `--`, and negative integers are prepended with a `-`. For

385example, `--1` represents positive one, and `-1` represents negative one.

386

387Zig zag encoding is used to convert atoms to signed integers. Positive signed

388integers correspond to even atoms of twice their absolute value, and negative

389signed integers correspond to odd atoms of twice their absolute value minus

390one. For example:

391

392```

393 > `@`--4

394 8

395 > `@s`8

396 --4

397

398 > `@`-4

399 7

400 > `@s`7

401 -4

402```

404---

406### `++abs:si`

408Absolute value

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

411

412#### Accepts

413

414`a` is a signed integer.

416#### Produces

418An atom.

420#### Source

422```hoon

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

424```

425

426#### Examples

427

428```

429 > (abs:si -11)

430 11

431

432 > (abs:si --520)

433 520

434```

436---

438### `++dif:si`

440Subtraction

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

443

444#### Accepts

445

446`a` is a signed integer.

447

448`b` is a signed integer.

450#### Produces

452A signed integer.

454#### Source

456```hoon

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

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

459```

460

461#### Examples

462

463```

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

465 --5

466

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

468 -5

469```

471---

473### `++dul:si`

475Modulus

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

478

479#### Examples

480

481`a` is a signed integer.

483`b` is an atom.

485#### Produces

487An atom.

489#### Source

491```hoon

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

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

494```

495

496#### Examples

497

498```

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

500 -5

501

502 > `@`--5

503 10

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

505 -5

506

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

508 --55

509```

511---

513### `++fra:si`

515Divide

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

518

519#### Accepts

520

521`a` is a signed integer.

522

523`b` is a signed integer.

525#### Produces

527A signed atom.

529#### Source

531```hoon

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

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

534```

535

536#### Examples

537

538```

539 > (fra:si -1 -1)

540 --1

541

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

543 -5

544

545 > (fra:si -0 -1)

546 --0

547```

549---

551### `++new:si`

553Atom to @s

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

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

557result in a prepending `-`.

559#### Accepts

561`a` is a flag.

563`b` is an atom.

565#### Produces

567A signed integer.

569#### Source

571```hoon

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

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

574```

575

576#### Examples

577

578```

579 > (new:si | 2)

580 -2

581

582 > (new:si & 2)

583 --2

584

585 > (new:si & -2)

586 --3

587

588 > (new:si & --2)

589 --4

590```

591

592---

593

594### `++old:si`

595

596Sign and absolute value

597

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

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

600

601#### Accepts

602

603`a` is a signed integer.

604

605#### Produces

606

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

608

609#### Source

610

611```hoon

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

613```

614

615#### Examples

616

617```

618 > (old:si -2)

619 [%.n 2]

620

621 > (old:si --2)

622 [%.y 2]

623```

625---

627### `++pro:si`

629Multiplication

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

632

633#### Accepts

634

635`a` is an unsigned integer.

636

637`b` is an unsigned integer.

638

639#### Source

640

641```hoon

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

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

644```

645

646#### Examples

647

648```

649 > (pro:si -3 -3)

650 --9

651

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

653 -9

654```

656---

658### `++rem:si`

660Remainder

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

663

664#### Accepts

665

666`a` is a signed integer.

667

668`b` is a signed integer.

670#### Produces

672A signed integer.

674#### Source

676```hoon

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

678```

679

680#### Examples

681

682```

683 > (rem:si -17 -3)

684 -2

685

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

687 --2

688

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

690 -2

691

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

693 --2

694```

696---

698### `++sum:si`

700Addition

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

703

704#### Accepts

705

706`a` is a signed integer.

707

708`b` is a signed integer.

710#### Produces

712A signed integer.

714#### Source

716```hoon

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

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

719 ?: -.c

720 ?: -.d

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

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

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

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

725 ?: -.d

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

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

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

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

730```

731

732#### Examples

733

734```

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

736 -9

737

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

739 --4

740```

742---

744### `++sun:si`

746@u to @s

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

749

750#### Accepts

751

752`a` is an unsigned integer.

754#### Produces

756An atom.

758#### Source

760```hoon

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

762```

763

764#### Examples

765

766```

767 > (sun:si 90)

768 180

769

770 > (sun:si --90)

771 360

772 > `@u`--90

773 180

774

775 > (sun:si --89)

776 356

777 > `@u`--89

778 178

779

780 > (sun:si -89)

781 354

782 > `@u`-89

783 177

784```

786---

788### `++syn:si`

790Sign test

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

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

794

795#### Accepts

796

797`a` is a signed integer.

799#### Produces

801An `term`.

803#### Source

805```hoon

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

807```

808

809#### Examples

810

811```

812 > (syn:si -2)

813 %.n

814

815 > (syn:si --2)

816 %.y

817```

819---

821### `++cmp:si`

823Compare

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

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

827equal, `--0` is produced.

828

829#### Accepts

830

831`a` is a signed integer.

832

833`b` is a signed integer.

835#### Produces

837A signed integer.

839#### Source

841```hoon

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

843 ^- @s

844 ?: =(a b)

845 --0

846 ?: (syn a)

847 ?: (syn b)

848 ?: (gth a b)

849 --1

850 -1

851 --1

852 ?: (syn b)

853 -1

854 ?: (gth a b)

855 -1

856 --1

857 --

858```

859

860#### Examples

861

862```

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

864 -1

865

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

867 -1

868

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

870 --1

871

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

873 --0

874

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

876 -1

877```

878

879---