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

git.iko.soy/urbit.org

on 2fc2532 help sign in

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

882 lines 9.8 kB history raw

1+++

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

3weight = 21

4template = "doc.html"

5+++

7## `++egcd`

9Extended Euclidean algorithm

11Produces `d`, the [greatest common

12divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor) of `a` and `b`.

13Also 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 `door` for modular arithmetic functions.

64#### Accepts

66`a` is an atom

68#### Source

70```hoon

71++ fo

72 ^|

73 |_ a=@

74```

76---

78### `++dif:fo`

80Subtraction

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

84#### Accepts

86`a` is an atom, and is the sample of `+fo`.

88`b` is an atom.

90`c` is an atom.

92#### Produces

94An atom.

96#### Source

98```hoon

99++ dif

100 |= [b=@ c=@]

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

102```

103

104#### Examples

105

106```

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

1085

109

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

1118

112```

114---

116### `++exp:fo`

118Exponent

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

121

122#### Accepts

123

124`a` is an atom, and is the sample of `+fo`.

126`b` is an atom.

128`c` is an atom.

130#### Produces

132An atom.

134#### Source

136```hoon

137++ exp

138 |= [b=@ c=@]

139 ?: =(0 b)

140 1

141 =+ d=$(b (rsh 0 b))

142 =+ e=(pro d d)

143 ?:(=(0 (end 0 b)) e (pro c e))

144```

145

146#### Examples

147

148```

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

150 1

151

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

153 66

154

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

156 61

157

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

159 256

160```

162---

164### `++fra:fo`

166Divide

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

169

170#### Accepts

171

172`a` is an atom, and is the sample of `+fo`.

174`b` is an atom.

176`c` is an atom.

178#### Produces

180An atom.

182#### Source

184```hoon

185++ fra

186 |= [b=@ c=@]

187 (pro b (inv c))

188```

189

190#### Examples

191

192```

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

1940

195

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

1971

198

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

2000

201

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

2034

204```

206---

208### `++inv:fo`

210Inverse

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

213`u` is produced by taking the [`+egcd`](#egcd) of `a` and `b`.

214

215#### Accepts

216

217`a` is an atom, and is the sample of `+fo`.

219`b` is an atom.

221#### Produces

223An atom.

225#### Source

227```hoon

228++ inv

229 |= b=@

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

231 c

232```

233

234#### Examples

235

236```

237> (~(inv fo 11) 2)

2386

239

240> (~(inv fo 71) 255)

24122

242

243> (~(inv fo 79) 255)

24422

245

246> (~(inv fo 78) 255)

24767

248

249> (~(inv fo 70) 255)

25067

251```

253---

255### `++pro:fo`

257Multiplication

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

260

261#### Accepts

262

263`a` is an atom, and is the sample of `+fo`.

265`b` is an atom.

267`c` is an atom.

269#### Produces

271An atom.

273#### Source

275```hoon

276++ pro

277 |= [b=@ c=@]

278 (sit (mul b c))

279```

280

281#### Examples

282

283```

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

2852

286

287> (mod 44 3)

2882

289```

291---

293### `++sit:fo`

295Modulus

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

298

299#### Accepts

300

301`a` is an atom, and is the sample of `+fo`.

303`b` is an atom.

305#### Produces

307An atom.

309#### Source

311```hoon

312++ sit

313 |= b=@

314 (mod b a)

315```

316

317#### Examples

318

319```

320> (~(sit fo 3) 14)

3212

322```

324---

326### `++sum:fo`

328Modular sum

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

331

332#### Accepts

333

334`a` is an atom, and is the sample of `+fo`.

336`b` is an atom.

338`c` is an atom.

340#### Produces

342An atom.

344#### Source

346```hoon

347++ sum

348 |= [b=@ c=@]

349 (sit (add b c))

350```

351

352#### Examples

353

354```

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

3562

357

358> (mod 17 3)

3592

360```

362---

364## `++si`

366Signed integer

368Container core for signed integer functions.

369

370#### Source

371

372```hoon

373++ si

374 ^?

375 |%

376```

377

378#### Discussion

379

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

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

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

383

384[ZigZag encoding](https://developers.google.com/protocol-buffers/docs/encoding?hl=en#signed-ints)

385is used to convert atoms to signed integers. Positive signed

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

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

388one. For example:

389

390```

391> `@`--4

3928

393> `@s`8

394--4

395```

396

397```

398> `@`-4

3997

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 a) (rsh 0 a)))

424```

425

426#### Examples

427

428```

429> (abs:si -11)

43011

431

432> (abs:si --520)

433520

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

50310

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 `?` and an atom.

608

609#### Source

610

611```hoon

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

613```

614

615```hoon

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

617```

618

619#### Examples

620

621```

622> (old:si -2)

623[%.n 2]

624

625> (old:si --2)

626[%.y 2]

627```

629---

631### `++pro:si`

633Multiplication

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

636

637#### Accepts

638

639`a` is an unsigned integer.

640

641`b` is an unsigned integer.

642

643#### Source

644

645```hoon

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

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

648```

649

650#### Examples

651

652```

653> (pro:si -3 -3)

654--9

655

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

657-9

658```

660---

662### `++rem:si`

664Remainder

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

667

668#### Accepts

669

670`a` is a signed integer.

671

672`b` is a signed integer.

674#### Produces

676A signed integer.

678#### Source

680```hoon

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

682```

683

684#### Examples

685

686```

687> (rem:si -17 -3)

688-2

689

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

691--2

692

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

694-2

695

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

697--2

698```

700---

702### `++sum:si`

704Addition

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

707

708#### Accepts

709

710`a` is a signed integer.

711

712`b` is a signed integer.

714#### Produces

716A signed integer.

718#### Source

720```hoon

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

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

723 ?: -.c

724 ?: -.d

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

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

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

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

729 ?: -.d

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

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

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

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

734```

735

736#### Examples

737

738```

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

740-9

741

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

743--4

744```

746---

748### `++sun:si`

750`@u` to `@s`

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

753

754#### Accepts

755

756`a` is an unsigned integer.

758#### Produces

760An atom.

762#### Source

764```hoon

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

766```

767

768#### Examples

769

770```

771> (sun:si 90)

772180

773

774> (sun:si --90)

775360

776> `@u`--90

777180

778

779> (sun:si --89)

780356

781> `@u`--89

782178

783

784> (sun:si -89)

785354

786> `@u`-89

787177

788```

790---

792### `++syn:si`

794Sign test

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

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

798

799#### Accepts

800

801`a` is a signed integer.

803#### Produces

805A `?`.

807#### Source

809```hoon

810++ syn |=(a=@s =(0 (end 0 a)))

811```

812

813#### Examples

814

815```

816> (syn:si -2)

817%.n

818

819> (syn:si --2)

820%.y

821```

823---

825### `++cmp:si`

827Compare

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

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

831equal, `--0` is produced.

832

833#### Accepts

834

835`a` is a signed integer.

836

837`b` is a signed integer.

839#### Produces

841A signed integer.

843#### Source

845```hoon

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

847 ^- @s

848 ?: =(a b)

849 --0

850 ?: (syn a)

851 ?: (syn b)

852 ?: (gth a b)

853 --1

854 -1

855 --1

856 ?: (syn b)

857 -1

858 ?: (gth a b)

859 -1

860 --1

861```

862

863#### Examples

864

865```

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

867-1

868

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

870-1

871

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

873--1

874

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

876--0

877

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

879-1

880```

881

882---