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

git.iko.soy/urbit.org

on 883cb21 help sign in

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

881 lines 9.7 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

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

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

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

387one. For example:

388

389```

390> `@`--4

3918

392> `@s`8

393--4

394```

395

396```

397> `@`-4

3987

399> `@s`7

400-4

401```

403---

405### `++abs:si`

407Absolute value

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

410

411#### Accepts

412

413`a` is a signed integer.

415#### Produces

417An atom.

419#### Source

421```hoon

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

423```

424

425#### Examples

426

427```

428> (abs:si -11)

42911

430

431> (abs:si --520)

432520

433```

435---

437### `++dif:si`

439Subtraction

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

442

443#### Accepts

444

445`a` is a signed integer.

446

447`b` is a signed integer.

449#### Produces

451A signed integer.

453#### Source

455```hoon

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

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

458```

459

460#### Examples

461

462```

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

464--5

465

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

467-5

468```

470---

472### `++dul:si`

474Modulus

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

477

478#### Examples

479

480`a` is a signed integer.

482`b` is an atom.

484#### Produces

486An atom.

488#### Source

490```hoon

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

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

493```

494

495#### Examples

496

497```

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

499-5

500

501> `@`--5

50210

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

504-5

505

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

507--55

508```

510---

512### `++fra:si`

514Divide

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

517

518#### Accepts

519

520`a` is a signed integer.

521

522`b` is a signed integer.

524#### Produces

526A signed atom.

528#### Source

530```hoon

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

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

533```

534

535#### Examples

536

537```

538> (fra:si -1 -1)

539--1

540

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

542-5

543

544> (fra:si -0 -1)

545--0

546```

548---

550### `++new:si`

552Atom to `@s`

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

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

556result in a prepending `-`.

558#### Accepts

560`a` is a flag.

562`b` is an atom.

564#### Produces

566A signed integer.

568#### Source

570```hoon

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

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

573```

574

575#### Examples

576

577```

578> (new:si | 2)

579-2

580

581> (new:si & 2)

582--2

583

584> (new:si & -2)

585--3

586

587> (new:si & --2)

588--4

589```

590

591---

592

593### `++old:si`

594

595Sign and absolute value

596

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

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

599

600#### Accepts

601

602`a` is a signed integer.

603

604#### Produces

605

606A cell composed of a `?` and an atom.

607

608#### Source

609

610```hoon

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

612```

613

614```hoon

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

616```

617

618#### Examples

619

620```

621> (old:si -2)

622[%.n 2]

623

624> (old:si --2)

625[%.y 2]

626```

628---

630### `++pro:si`

632Multiplication

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

635

636#### Accepts

637

638`a` is an unsigned integer.

639

640`b` is an unsigned integer.

641

642#### Source

643

644```hoon

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

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

647```

648

649#### Examples

650

651```

652> (pro:si -3 -3)

653--9

654

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

656-9

657```

659---

661### `++rem:si`

663Remainder

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

666

667#### Accepts

668

669`a` is a signed integer.

670

671`b` is a signed integer.

673#### Produces

675A signed integer.

677#### Source

679```hoon

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

681```

682

683#### Examples

684

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

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

696--2

697```

699---

701### `++sum:si`

703Addition

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

706

707#### Accepts

708

709`a` is a signed integer.

710

711`b` is a signed integer.

713#### Produces

715A signed integer.

717#### Source

719```hoon

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

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

722 ?: -.c

723 ?: -.d

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

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

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

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

728 ?: -.d

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

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

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

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

733```

734

735#### Examples

736

737```

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

739-9

740

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

742--4

743```

745---

747### `++sun:si`

749`@u` to `@s`

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

752

753#### Accepts

754

755`a` is an unsigned integer.

757#### Produces

759An atom.

761#### Source

763```hoon

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

765```

766

767#### Examples

768

769```

770> (sun:si 90)

771180

772

773> (sun:si --90)

774360

775> `@u`--90

776180

777

778> (sun:si --89)

779356

780> `@u`--89

781178

782

783> (sun:si -89)

784354

785> `@u`-89

786177

787```

789---

791### `++syn:si`

793Sign test

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

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

797

798#### Accepts

799

800`a` is a signed integer.

802#### Produces

804A `?`.

806#### Source

808```hoon

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

810```

811

812#### Examples

813

814```

815> (syn:si -2)

816%.n

817

818> (syn:si --2)

819%.y

820```

822---

824### `++cmp:si`

826Compare

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

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

830equal, `--0` is produced.

831

832#### Accepts

833

834`a` is a signed integer.

835

836`b` is a signed integer.

838#### Produces

840A signed integer.

842#### Source

844```hoon

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

846 ^- @s

847 ?: =(a b)

848 --0

849 ?: (syn a)

850 ?: (syn b)

851 ?: (gth a b)

852 --1

853 -1

854 --1

855 ?: (syn b)

856 -1

857 ?: (gth a b)

858 -1

859 --1

860```

861

862#### Examples

863

864```

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

866-1

867

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

869-1

870

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

872--1

873

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

875--0

876

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

878-1

879```

880

881---