source: project/wiki/eggref/5/math @ 39757

Last change on this file since 39757 was 39757, checked in by Diego, 3 months ago

math: add docs for (math base)

File size: 36.4 KB
Line 
1[[toc:]]
2
3== math
4
5=== Introduction
6
7math is a chicken port of racket's math library.
8
9The following documentation is largely taken directly from the racket
10documentation, but tweaked for the CHICKEN implementation.
11
12=== Modules
13
14==== (math base)
15
16Constants and elementary functions
17
18===== Constants
19
20<constant>phi.0</constant>
21
22An approximation of φ, the [[https://en.wikipedia.org/wiki/Golden_ratio|golden ratio]].
23
24<enscript highlight="scheme">
25> phi.0
261.618033988749895
27</enscript>
28
29<constant>euler.0</constant>
30
31An approximation of ''e'', or [[https://en.wikipedia.org/wiki/E_(mathematical_constant)|Euler's number]].
32
33<enscript highlight="scheme">
34> euler.0
352.718281828459045
36> (exp 1)
372.718281828459045
38</enscript>
39
40<constant>catalan.0</constant>
41
42An approximation of ''G'', or [[https://en.wikipedia.org/wiki/Catalan's_constant|Catalan's constant]].
43
44<enscript highlight="scheme">
45> catalan.0
460.915965594177219
47</enscript>
48
49===== Functions
50
51<procedure>(float-complex? v) -> boolean</procedure>
52
53; v : any
54
55Returns {{#t}} when {{v}} is an inexact complex number. Analogous to
56[[https://wiki.call-cc.org/man/5/Module%20(chicken%20base)#flonum|flonum?]]
57
58<procedure>(number->float-complex x) -> cplxnum</procedure>
59
60; x : number
61
62Returns a new complex number with a flonum real part and a flonum imaginary
63part. Analogous to {{exact->inexact}}.
64
65<procedure>(power-of-two? x) -> boolean</procedure>
66
67; x : number
68
69Returns {{#t}} when {{x}} is an integer power of 2.
70
71Examples:
72<enscript highlight="scheme">
73> (power-of-two? 1.0)
74#t
75> (power-of-two? 1/2)
76#t
77> (power-of-two? (flnext 2.0))
78#f
79</enscript>
80
81<procedure>(asinh z) -> number</procedure>
82<procedure>(acosh z) -> number</procedure>
83<procedure>(atanh z) -> number</procedure>
84
85; z : number
86
87The inverses of {{sinh}}, {{cosh}}, and {{tanh}}.
88
89<procedure>(sum xs) -> number</procedure>
90
91; xs : (list-of number)
92
93Like {{(apply + xs)}}, but incurs rounding error only once when adding inexact
94numbers. (In fact, the inexact numbers in {{xs}} are summed separately using
95{{fpsum}}).
96
97===== Random Number Generation
98
99<procedure>(random-natural k) -> integer</procedure>
100
101; k : integer
102
103Returns a random natural number less than {{k}}, which must be positive.
104
105<procedure>(random-integer a b) -> integer</procedure>
106
107; a : integer
108; b : integer
109
110Returns a random integer n such that {{(<= a n)}} and {{(< n b)}}.
111
112<procedure>(random-bits num)</procedure>
113
114; num : integer
115
116Returns a random natural smaller than {{(expt 2 num)}}; {{num}} must be
117positive. For powers of two, this is faster than using {{random-natural}},
118which is implemented in terms of {{random-bits}}, using biased rejection
119sampling.
120
121===== Measuring error
122
123<procedure>(absolute-error x r) -> number</procedure>
124
125; x : number
126; r : number
127
128Usually computes {{(abs (- x r))}} using exact rationals, but handles
129non-rational reals such as {{+inf.0}} specially.
130
131Examples:
132<enscript highlight="scheme">
133> (absolute-error 1/2 1/2)
1340
135> (absolute-error 0.14285714285714285 1/7)
1367.93016446160826e-18
137> (absolute-error +inf.0 +inf.0)
1380.0
139> (absolute-error +inf.0 +nan.0)
140+inf.0
141> (absolute-error 1e-20 0.0)
1421e-20
143> (absolute-error (- 1.0 (fl 4999999/5000000)) 1/5000000)
1445.751132903242251e-18
145</enscript>
146
147<procedure>(relative-error x r) -> number</procedure>
148
149; x : number
150; r : number
151
152Measures how close an approximation {{x}} is to the correct value {{r}},
153relative to the magnitude of {{r}}.
154
155This function usually computes {{(abs (/ (- x r) r))}} using exact rationals, but
156handles non-rational reals such as {{+inf.0}} specially, as well as {{r = 0}}.
157
158<enscript highlight="scheme">
159> (relative-error 1/2 1/2)
1600
161> (relative-error 0.14285714285714285 1/7)
1625.551115123125783e-17
163> (relative-error +inf.0 +inf.0)
1640.0
165> (relative-error +inf.0 +nan.0)
166+inf.0
167> (relative-error 1e-20 0.0)
168+inf.0
169> (relative-error (- 1.0 (fl 4999999/5000000)) 1/5000000)
1702.8755664516211255e-11
171</enscript>
172
173In the last two examples, relative error is high because the result is near
174zero. (Compare the same examples with {{absolute-error}}.) Because flonums are
175particularly dense near zero, this makes relative error better than absolute
176error for measuring the error in a flonum approximation. An even better one is
177error in ulps; see {{fpulp}} and {{fpulp-error}}.
178
179==== (math number-theory)
180
181Number-theoretic functions
182
183===== Congruences and modular arithmetic
184<procedure>(divides? m n) -> boolean</procedure>
185
186; m : integer
187; n : integer
188
189Returns {{#t}} if {{m}} divides {{n}}, {{#f}} otherwise.
190
191Examples:
192<enscript highlight="scheme">
193> (divides? 2 9)
194#f
195> (divides? 2 8)
196#t
197</enscript>
198
199Note that 0 cannot divide anything:
200
201<enscript highlight="scheme">
202> (divides? 0 5)
203#f
204> (divides? 0 0)
205#f
206</enscript>
207
208Practically, if {{(divides? m n)}} is {{#t}}, then {{(/ n m)}} will return an integer.
209
210Wikipedia: [[https://en.wikipedia.org/wiki/Divisor|Divisor]]
211
212<procedure>(bezout a b c ...) -> (list-of integer)</procedure>
213
214; a : integer
215; b : integer
216; c : integer
217
218Given integers {{a b c ...}} returns a list of integers {{(list u v w ...)}}
219such that {{(gcd a b c ...)}} = {{(+ (* a u) (* b v) (* c w) ...)}}.
220
221Examples:
222<enscript highlight="scheme">
223> (bezout 6 15)
224(-2 1)
225> (+ (* -2 6) (* 1 15))
2263
227> (gcd 6 15)
2283
229</enscript>
230
231Wikipedia: [[https://en.wikipedia.org/wiki/B%C3%A9zout's_identity|Bézout's Identity]]
232
233<procedure>(coprime? a b ...) -> boolean</procedure>
234
235; a : integer
236; b : integer
237
238Returns {{#t}} if the integers {{a b ...}} are coprime. Formally, a set of
239integers is considered coprime (also called relatively prime) if their greatest
240common divisor is 1.
241
242Example:
243<enscript highlight="scheme">
244> (coprime? 2 6 15)
245#t
246</enscript>
247
248Wikipedia: [[https://en.wikipedia.org/wiki/Coprime|Coprime]]
249
250<procedure>(pairwise-coprime? a b ...) -> boolean</procedure>
251
252; a : integer
253; b : integer
254
255Returns {{#t}} if the integers {{a b ...}} are ''pairwise'' coprime, meaning that each
256pair of integers is coprime.
257
258The numbers 2, 6 and 15 are coprime, but not ''pairwise'' coprime, because 6 and 15
259share the factor 3:
260<enscript highlight="scheme">
261> (pairwise-coprime? 2 6 15)
262#f
263</enscript>
264
265Wikipedia:[[https://en.wikipedia.org/wiki/Pairwise_coprime|Pairwise Coprime]]
266
267<procedure>(solve-chinese as ns) -> integer</procedure>
268
269; as : (list-of integer)
270; ns : (list-of integer)
271
272Given a length-k list of integers as and a length-k list of coprime moduli ns,
273(solve-chinese as ns) returns the least natural number x that is a solution to
274the equations
275
276 x = a₁ (mod n₁)
277  ...
278 x = aₖ (mod nₖ)
279
280The solution {{x}} is less than {{(* n1 ... nk)}}.
281
282The moduli {{ns}} must all be positive.
283
284What is the least number {{x}} that when divided by 3 leaves a remainder of 2, when
285divided by 5 leaves a remainder of 3, and when divided by 7 leaves a remainder
286of 2?
287<enscript highlight="scheme">
288> (solve-chinese '(2 3 2) '(3 5 7))
28923
290</enscript>
291
292Wikipedia: [[https://en.wikipedia.org/wiki/Chinese_remainder_theorem|Chinese Remainder Theorem]]
293
294<procedure>(quadratic-residue? a n) -> boolean</procedure>
295
296; a : integer
297; n : integer
298
299Returns {{#t}} if {{a}} is a quadratic residue modulo {{n}}, otherwise {{#f}}. The modulus
300{{n}} must be positive, and a must be nonnegative.
301
302Formally, {{a}} is a quadratic residue modulo {{n}} if there exists a number
303{{x}} such that {{(* x x)}} = {{a}} (mod {{n}}). In other words,
304{{(quadratic-residue? a n)}} is {{#t}} when {{a}} is a perfect square modulo
305{{n}}.
306
307Examples:
308<enscript highlight="scheme">
309> (quadratic-residue? 0 4)
310#f
311> (quadratic-residue? 1 4)
312#t
313> (quadratic-residue? 2 4)
314#f
315> (quadratic-residue? 3 4)
316#f
317</enscript>
318
319Wikipedia: [[https://en.wikipedia.org/wiki/Quadratic_residue|Quadratic Residue]]
320
321<procedure>(quadratic-character a p) -> integer</procedure>
322
323; a : integer
324; b : integer
325
326Returns the value of the quadratic character modulo the prime {{p}}. That is,
327for a non-zero {{a}} the number 1 is returned when {{a}} is a quadratic
328residue, and -1 is returned when {{a}} is a non-residue. If {{a}} is zero, then
3290 is returned.
330
331If {{a}} is negative or {{p}} is not positive, quadratic-character raises an
332error. If {{p}} is not prime, (quadratic-character a p) is indeterminate.
333
334This function is also known as the ''Legendre symbol''.
335
336<enscript highlight="scheme">
337> (quadratic-character 0 5)
3380
339> (quadratic-character 1 5)
3401
341> (quadratic-character 2 5)
342-1
343> (quadratic-character 3 5)
344-1
345</enscript>
346
347Wikipedia: [[https://en.wikipedia.org/wiki/Legendre_symbol|Legendre Symbol]]
348
349<procedure>(jacobi-symbol a n) -> integer</procedure>
350
351; a : integer
352; n : integer
353
354Computes the Jacobi symbol for any nonnegative integer {{a}} and any positive
355odd integer {{n}}.
356
357If {{n}} is not an odd positive integer, {{(jacobi-symbol a n)}} throws an exception.
358
359<enscript highlight="scheme">
360> (jacobi-symbol 1 1)
3611
362> (jacobi-symbol 8 11)
363-1
364> (jacobi-symbol 39 27)
3650
366> (jacobi-symbol 22 59)
3671
368> (jacobi-symbol 32 8)
369Error: (jacobi-symbol) bad argument type - not an odd integer: 8
370</enscript>
371
372Wikipedia: [[https://en.wikipedia.org/wiki/Jacobi_symbol|Jacobi Symbol]]
373
374<procedure>(modular-inverse a n) -> integer</procedure>
375
376; a : integer
377; b : integer
378
379Returns the inverse of a modulo {{n}} if {{a}} and {{n}} are coprime, otherwise raises an
380error. The modulus {{n}} must be positive, and {{a}} must be nonzero.
381
382Formally, if {{a}} and {{n}} are coprime, {{b}} = {{(modular-inverse a n)}} is the unique
383natural number less than {{n}} such that {{(* a b)}} = {{1}} (mod {{n}}).
384
385<enscript highlight="scheme">
386> (modular-inverse 2 5)
3873
388> (modulo (* 2 3) 5)
3891
390</enscript>
391
392Wikipedia: [[https://en.wikipedia.org/wiki/Modular_multiplicative_inverse|Multiplicative Inverse]]
393
394<procedure>(modular-expt a b n) -> integer</procedure>
395
396; a : integer
397; b : integer
398; n : integer
399
400Computes {{(modulo (expt a b) n)}}, but much more efficiently. The modulus {{n}} must
401be positive, and the exponent {{b}} must be nonnegative.
402
403<enscript highlight="scheme">
404> (modulo (expt -6 523) 19)
40513
406> (modular-expt -6 523 19)
40713
408> (modular-expt 9 158235208 19)
4094
410> ; don't try this at home!
411  (modulo (expt 9 158235208) 19)
4124
413</enscript>
414
415===== Parameterized Modular Arithmetic
416
417The {{math.number-theory}} library supports modular arithmetic parameterized on
418a current modulus. For example, the code
419
420<enscript highlight="scheme">
421(with-modulus n
422  (mod= (modexpt a b) c))
423</enscript>
424
425corresponds with the mathematical statement ''a^b'' = ''c'' (mod ''n'').
426
427The current modulus is stored in a parameter that, for performance reasons, can
428only be set using with-modulus. (The basic modular operators cache parameter
429reads, and this restriction guarantees that the cached values are current.
430'''NOTE:''' I'm not entirely sure this is true for the chicken port, as a
431slightly more complicated racket syntax-case has been turned into a simple
432syntax-rule for {{(parameterize ...)}})
433
434Wikipedia: [[https://en.wikipedia.org/wiki/Modular_arithmetic|Modular Arithmetic]]
435
436<syntax>(with-modulus n body ...)</syntax>
437
438; n : integer
439
440Alters the current modulus within the dynamic extent of {{body}}. The
441expression {{n}} must evaluate to a positive integer.
442
443By default, the current modulus is 1, meaning that every modular arithmetic
444expression that does not raise an error returns 0.
445
446<procedure>(current-modulus) -> integer</procedure>
447
448Returns the current modulus.
449
450Examples:
451
452<enscript highlight="scheme">
453> (current-modulus)
4541
455> (with-modulus 5 (current-modulus))
4565
457</enscript>
458
459<procedure>(mod x) -> integer</procedure>
460
461; x : exact rational
462
463Converts a rational number {{x}} to a natural number less than the current
464modulus.
465
466If {{x}} is an integer, this is equivalent to {{(modulo x n)}}. If {{x}} is a
467fraction, an integer input is generated by multiplying its numerator by its
468denominator’s modular inverse.
469
470Examples:
471
472<enscript highlight="scheme">
473> (with-modulus 7 (mod (* 218 7)))
4740
475> (with-modulus 7 (mod 3/2))
4765
477> (with-modulus 7 (mod/ 3 2))
4785
479> (with-modulus 7 (mod 3/7))
480Error: (modular-inverse) bad argument type - not coprime to modulus 7: 7
481</enscript>
482
483<procedure>(mod+ a ...) -> integer</procedure>
484<procedure>(mod* a ...) -> integer</procedure>
485
486; a : integer
487
488Equivalent to {{(modulo (+ a ...) (current-modulus))}} and {{(modulo (* a ...) (current-modulus))}},
489respectively, but generate smaller intermediate values.
490
491<procedure>(modsqr a) -> integer</procedure>
492<procedure>(modexpt a b) -> integer</procedure>
493
494; a : integer
495; b : integer
496
497Equivalent to {{(mod* a a)}} and {{(modular-expt a b (current-modulus))}}, respectively.
498
499<procedure>(mod- a b ...) -> integer</procedure>
500
501; a : integer
502; b : integer
503
504Equivalent to {{(modulo (- a b ...) (current-modulus))}}, but generates smaller
505intermediate values. Note that {{(mod- a)}} = {{(mod (- a))}}.
506
507<procedure>(mod/ a b ...) -> integer</procedure>
508
509; a : integer
510; b : integer
511
512Divides a by {{(* b ...)}}, by multiplying {{a}} by the multiplicative inverse of
513{{(* b ...)}}. The one-argument variant returns the modular inverse of {{a}}.
514
515Note that {{(mod/ a b ...)}} is '''not''' equivalent to
516{{(modulo (/ a b ...) (current-modulus))}}; see {{mod=}} for a demonstration.
517
518<procedure>(mod= a b ...) -> boolean</procedure>
519<procedure>(mod< a b ...) -> boolean</procedure>
520<procedure>(mod<= a b ...) -> boolean</procedure>
521<procedure>(mod> a b ...) -> boolean</procedure>
522<procedure>(mod>= a b ...) -> boolean</procedure>
523
524; a : integer
525; b : integer
526
527Each of these is equivalent to {{(op (mod a) (mod b) ...)}}, where op is the
528corresponding numeric comparison function. Additionally, when given one
529argument, the inequality tests always return {{#t}}.
530
531Suppose we wanted to know why 17/4 = 8 (mod 15), but 51/12 (mod 15) is
532undefined, even though normally 51/12 = 17/4. In code,
533
534<enscript highlight="scheme">
535> (with-modulus 15 (mod/ 17 4))
5368
537> (/ 51 12)
53817/4
539> (with-modulus 15 (mod/ 51 12))
540Error: (modular-inverse) bad argument type - not coprime to modulus 15: 12
541</enscript>
542
543We could try to divide by brute force: find, modulo 15, all the numbers {{a}} for
544which {{(mod* a 4)}} is 17, then find all the numbers {{b}} for which {{(mod* a 12)}} is
54551.
546<enscript highlight="scheme">
547(import srfi-42)
548> (with-modulus 15
549    (list-ec (:range a 15)
550             (if (mod= (mod* a 4) 17))
551      a))
552(8)
553> (with-modulus 15
554    (list-ec (:range a 15)
555             (if (mod= (mod* a 12) 51))
556      a))
557(3 8 13)
558</enscript>
559
560So the problem isn't that {{b}} doesn't exist, it's that {{b}} isn't
561''unique''.
562
563===== Primes
564<procedure>(prime? z) -> boolean</procedure>
565
566; z : integer
567
568Returns {{#t}} if {{z}} is a prime, {{#f}} otherwise.
569
570Formally, an integer {{z}} is prime when the only positive divisors of {{z}}
571are 1 and {{(abs z)}}.
572
573The positive primes below 20 are:
574<enscript highlight="scheme">
575> (filter prime? (iota 20 1))
576(2 3 5 7 11 13 17 19)
577</enscript>
578
579The corresponding negative primes are:
580<enscript highlight="scheme">
581> (filter prime? (iota 20 0 -1))
582(-2 -3 -5 -7 -11 -13 -17 -19)
583</enscript>
584
585Wikipedia: [[https://en.wikipedia.org/wiki/Prime_number|Prime Number]]
586
587<procedure>(odd-prime? z) -> boolean</procedure>
588
589; z : integer
590
591Returns {{#t}} if {{z}} is a odd prime, {{#f}} otherwise.
592
593<enscript highlight="scheme">
594> (odd-prime? 2)
595#f
596> (odd-prime? 3)
597#t
598</enscript>
599
600<procedure>(nth-prime n) -> integer</procedure>
601
602; n : integer
603
604Returns the {{n}}th positive prime; {{n}} must be nonnegative.
605
606<enscript highlight="scheme">
607> (nth-prime 0)
6082
609> (nth-prime 1)
6103
611> (nth-prime 2)
6125
613</enscript>
614
615<procedure>(random-prime n) -> integer</procedure>
616
617; n : integer
618
619Returns a random prime smaller than {{n}}, which must be greater than 2.
620
621The function {{random-prime}} picks random numbers below {{n}} until a prime is
622found.
623
624<enscript highlight="scheme">
625> (random-prime 10)
6263
627> (random-prime 10)
6282
629> (random-prime 10)
6305
631</enscript>
632
633<procedure>(next-prime z) -> integer</procedure>
634
635; z : integer
636
637Returns the first prime larger than {{z}}.
638
639<enscript highlight="scheme">
640> (next-prime 4)
6415
642> (next-prime 5)
6437
644</enscript>
645
646<procedure>(prev-prime z) -> integer</procedure>
647
648Returns the first prime smaller than {{z}}.
649
650<enscript highlight="scheme">
651> (prev-prime 4)
6523
653> (prev-prime 5)
6543
655</enscript>
656
657<procedure>(next-primes z n) -> (list-of integer)</procedure>
658
659; z : integer
660; n : integer
661
662Returns list of the next {{n}} primes larger than {{z}}; {{n}} must be
663nonnegative.
664
665<enscript highlight="scheme">
666> (next-primes 2 4)
667(3 5 7 11)
668</enscript>
669
670<procedure>(prev-primes z n) -> (list-of integer)</procedure>
671
672; z : integer
673; n : integer
674
675Returns list of the next {{n}} primes smaller than {{z}}; {{n}} must be
676nonnegative.
677
678<enscript highlight="scheme">
679> (prev-primes 13 4)
680(11 7 5 3)
681</enscript>
682
683<procedure>(factorize n) -> (list-of (list integer integer))</procedure>
684
685; n : integer
686
687Returns the factorization of a natural number {{n}}. The factorization consists of
688a list of corresponding primes and exponents. The primes will be in ascending
689order.
690
691The prime factorization of 600 = 2^3 * 3^1 * 5^2:
692
693<enscript highlight="scheme">
694> (factorize 600)
695((2 3) (3 1) (5 2))
696</enscript>
697
698<procedure>(defactorize f) -> integer</procedure>
699
700; f : (list-of (list integer integer))
701
702Returns the natural number, whose factorization is given by {{f}}. The
703factorization {{f}} is represented as described in {{factorize}}.
704
705<enscript highlight="scheme">
706> (defactorize '((2 3) (3 1) (5 2)))
707600
708</enscript>
709
710Wikipedia: [[https://en.wikipedia.org/wiki/Integer_factorization|Integer Factorization]]
711
712<procedure>(divisors z) -> (list-of integer)</procedure>
713
714; z : integer
715
716Returns a list of all positive divisors of the integer {{z}}. The divisors appear
717in ascending order.
718
719<enscript highlight="scheme">
720> (divisors 120)
721(1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120)
722> (divisors -120)
723(1 2 3 4 5 6 8 10 12 15 20 24 30 40 60 120)
724</enscript>
725
726<procedure>(prime-divisors z) -> (list-of integer)</procedure>
727
728; z : integer
729
730Returns a list of all positive prime divisors of the integer {{z}}. The divisors
731appear in ascending order.
732
733<enscript highlight="scheme">
734> (prime-divisors 120)
735'(2 3 5)
736</enscript>
737
738<procedure>(prime-exponents z) -> (list-of integer)</procedure>
739
740; z : integer
741
742Returns a list of the exponents of in a factorization of the integer {{z}}.
743
744<enscript highlight="scheme">
745> (define z (* 2 2 2 3 5 5))
746> (prime-divisors z)
747(2 3 5)
748> (prime-exponents z)
749(3 1 2)
750</enscript>
751
752===== Roots
753
754<procedure>(integer-root n m) -> integer</procedure>
755
756; n : integer
757; m : integer
758
759Returns the mth integer root of {{n}}. This is the largest integer {{r}} such that
760{{(expt r m)}} <= {{n}}.
761
762<enscript highlight="scheme">
763> (integer-root (expt 3 4) 4)
7643
765> (integer-root (+ (expt 3 4) 1) 4)
7663
767</enscript>
768
769<procedure>(integer-root/remainder n m) -> integer integer</procedure>
770
771; n : integer
772; m : integer
773
774Returns two values. The first, {{r}}, is the {{m}}th integer root of {{n}}. The
775second is {{n}}-{{r}}^{{m}}.
776
777<enscript highlight="scheme">
778> (integer-root/remainder (expt 3 4) 4)
7793
7800
781> (integer-root/remainder (+ (expt 3 4) 1) 4)
7823
7831
784</enscript>
785
786===== Powers
787
788<procedure>(max-dividing-power a b) -> integer</procedure>
789
790; a : integer
791; b : integre
792
793Returns the largest exponent, {{n}}, of a power with base {{a}} that divides
794{{b}}.
795
796That is, {{(expt a n)}} divides {{b}} but {{(expt a (+ n 1))}} does not divide {{b}}.
797
798<enscript highlight="scheme">
799> (max-dividing-power 3 (expt 3 4))
8004
801> (max-dividing-power 3 5)
8020
803</enscript>
804
805<procedure>(perfect-power m) -> (or (list integer integer) #f)</procedure>
806
807; m : integer
808
809If {{m}} is a perfect power, a list with two elements {{b}} and {{n}} such that
810{{(expt b n)}} = {{m}} is returned, otherwise {{#f}} is returned.
811
812<enscript highlight="scheme">
813> (perfect-power (expt 3 4))
814(3 4)
815> (perfect-power (+ (expt 3 4) 1))
816#f
817</enscript>
818
819<procedure>(perfect-power? m) -> boolean</procedure>
820
821; m : integer
822
823Returns {{#t}} if {{m}} is a perfect power, otherwise {{#f}}.
824
825<enscript highlight="scheme">
826> (perfect-power? (expt 3 4))
827#t
828> (perfect-power? (+ (expt 3 4) 1))
829#f
830</enscript>
831
832Wikipedia: [[https://en.wikipedia.org/wiki/Perfect_power|Perfect Power]]
833
834<procedure>(prime-power m) -> (or (list integer integer) #f)</procedure>
835
836; m : integer
837
838If {{M}} is a power of the form {{(expt p n)}} where p is prime, then a list with the
839prime and the exponent is returned, otherwise {{#f}} is returned.
840
841<enscript highlight="scheme">
842> (prime-power (expt 3 4))
843(3 4)
844> (prime-power (expt 6 4))
845#f
846</enscript>
847
848<procedure>(prime-power? m) -> boolean</procedure>
849
850; m : integer
851
852Returns {{#t}} if {{m}} is a prime power, otherwise {{#f}}.
853
854<enscript highlight="scheme">
855> (prime-power? (expt 3 4))
856#t
857> (prime-power? (expt 6 4))
858#f
859> (prime-power? 1)
860#f
861> (prime-power? 0)
862#f
863</enscript>
864
865<procedure>(odd-prime-power? m) -> boolean</procedure>
866
867; m : integer
868
869Returns {{#t}} if {{m}} is a power of an odd prime, otherwise {{#f}}.
870
871<enscript highlight="scheme">
872> (odd-prime-power? (expt 2 4))
873#f
874> (odd-prime-power? (expt 3 4))
875#t
876> (odd-prime-power? (expt 15 4))
877#f
878</enscript>
879
880<procedure>(as-power m) -> integer integer</procedure>
881
882; m : integer
883
884Returns two values {{b}} and {{n}} such that {{m}} = {{(expt b n)}} and {{n}}
885is maximal.
886
887<enscript highlight="scheme">
888> (as-power (* (expt 2 4) (expt 3 4)))
8896
8904
891> (expt 6 4)
8921296
893> (* (expt 2 4) (expt 3 4))
8941296
895> (as-power (* (expt 2 4) (expt 3 5)))
8963888
8971
898</enscript>
899
900<procedure>(prefect-square m) -> (or integer #f)</procedure>
901
902Returns {{(sqrt m)}} if {{m}} is perfect square, otherwise {{#f}}.
903
904<enscript highlight="scheme">
905> (perfect-square 9)
9063
907> (perfect-square 10)
908#f
909</enscript>
910
911===== Multiplicative and Arithmetic Functions
912
913The functions in this section are ''multiplicative'' (with exception of the Von
914Mangoldt function). In number theory, a multiplicative function is a function
915{{f}} such that {{(f (* a b))}} = {{(* (f a) (f b))}} for all coprime natural
916numbers {{a}} and {{b}}.
917
918<procedure>(totient n) -> integer</procedure>
919
920; n : integer
921
922Returns the number of integers from 1 to {{n}} that are coprime with {{n}}.
923
924This function is known as Euler's totient or phi function.
925
926<enscript highlight="scheme">
927> (totient 9)
9286
929> (length (filter (curry coprime? 9) (range 10)))
9306
931</enscript>
932
933Wikipedia: [[https://en.wikipedia.org/wiki/Euler%27s_totient_function|Euler's Totient]]
934
935<procedure>(moebius-mu n) -> integer</procedure>
936
937; n : integer
938
939Returns:
940
941* 1 if {{n}} is a square-free product of an even number of primes
942* -1 if {{n}} is a square-free product of an odd number of primes
943* 0 if {{n}} has a multiple prime factor
944
945<enscript highlight="scheme">
946> (moebius-mu (* 2 3 5))
947-1
948> (moebius-mu (* 2 3 5 7))
9491
950> (moebius-mu (* 2 2 3 5 7))
9510
952</enscript>
953
954Wikipedia: [[https://en.wikipedia.org/wiki/M%C3%B6bius_function|Moebius Function]]
955
956<procedure>(divisor-sum n k) -> integer</procedure>
957
958; n : integer
959; k : integer
960
961Returns sum of the {{k}}th powers of all divisors of {{n}}.
962
963<enscript highlight="scheme">
964> (divisor-sum 12 2)
965210
966> (apply + (map sqr (divisors 12)))
967210
968</enscript>
969
970Wikipedia: [[https://en.wikipedia.org/wiki/Divisor_function|Divisor Function]]
971
972<procedure>(prime-omega n) -> integer</procedure>
973
974; n : integer
975
976Counting multiplicities the number of prime factors of {{n}} is returned.
977
978<enscript highlight="scheme">
979> (prime-omega (* 2 2 2 3 3 5))
9806
981</enscript>
982
983OEIS: [[https://oeis.org/A001222|Big Omega]], [[https://oeis.org/wiki/Omega(n),_number_of_prime_factors_of_n_(with_multiplicity)|Big Omega]]
984
985<procedure>(mangoldt-lambda n) -> number</procedure>
986
987; n : integer
988
989The von Mangoldt function. If n=p^k for a prime {{p}} and an integer {{k>=1}}
990then {{(log n)}} is returned. Otherwise {{0}} is returned.
991
992Note: The Von Mangoldt function is not multiplicative.
993
994<enscript highlight="scheme">
995> (mangoldt-lambda (* 3 3))
9961.0986122886681098
997> (log 3)
9981.0986122886681098
999</enscript>
1000
1001Wikipedia: [[https://en.wikipedia.org/wiki/Von_Mangoldt_function|Von Mangoldt Function]]
1002
1003===== Number Sequences
1004
1005<procedure>(bernoulli-number n) -> ratnum</procedure>
1006
1007; n : integer
1008
1009Returns the {{n}}th Bernoulli number; {{n}} must be nonnegative.
1010
1011<enscript highlight="scheme">
1012> (map bernoulli-number (iota 9))
1013(1 -1/2 1/6 0 -1/30 0 1/42 0 -1/30)
1014</enscript>
1015
1016Note that these are the ''first'' Bernoulli numbers, since
1017{{(bernoulli-number 1)}} = {{-1/2}}.
1018
1019Wikipedia: [[https://en.wikipedia.org/wiki/Bernoulli_number|Bernoulli Number]]
1020
1021<procedure>(eulerian-number n k) -> integer</procedure>
1022
1023; n : integer
1024; k : integer
1025
1026Returns the Eulerian number {{<n,k>}}; both arguments must be nonnegative.
1027
1028<enscript highlight="scheme">
1029> (eulerian-number 5 2)
103066
1031</enscript>
1032
1033Wikipedia: [[http://mathworld.wolfram.com/EulerianNumber.html|Eulerian Number]]
1034
1035<procedure>(fibonacci n) -> integer</procedure>
1036
1037; n : integer
1038
1039Returns the {{n}}th Fibonacci number; {{n}} must be nonnegative.
1040
1041The ten first Fibonacci numbers:
1042<enscript highlight="scheme">
1043> (map fibonacci (iota 10))
1044'(0 1 1 2 3 5 8 13 21 34)
1045</enscript>
1046
1047Wikipedia: [[https://en.wikipedia.org/wiki/Fibonacci_number|Fibonacci Number]]
1048
1049<procedure>(make-fibonaci a b) -> (integer -> integer)</procedure>
1050
1051; a : integer
1052; b : integer
1053
1054Returns a function representing a Fibonacci sequence with the first two numbers
1055{{a}} and {{b}}. The {{fibonacci}} function is defined as {{(make-fibonacci 0 1)}}.
1056
1057The Lucas numbers are defined as a Fibonacci sequence starting with 2 and 1:
1058
1059<enscript highlight="scheme">
1060> (map (make-fibonacci 2 1) (iota 10))
1061(2 1 3 4 7 11 18 29 47 76)
1062</enscript>
1063
1064Wikipedia: [[https://wikipedia.org/wiki/Lucas_number|Lucas Number]]
1065
1066<procedure>(modular-fibonacci n m) -> integer</procedure>
1067
1068; n : integer
1069; m : integer
1070
1071Returns the {{n}}th Fibonacci number modulo {{m}}; {{n}} must be nonnegative
1072and {{m}} must be positive.
1073
1074The ten first Fibonacci numbers modulo 5:
1075<enscript highlight="scheme">
1076> (map (lambda (n) (modular-fibonacci n 5)) (range 10))
1077(0 1 1 2 3 0 3 3 1 4)
1078</enscript>
1079
1080<procedure>(make-modular-fibonacci a b) -> (integer integer -> integer)</procedure>
1081
1082; a : integer
1083; b : integer
1084
1085Like {{make-fibonacci}}, but makes a modular fibonacci sequence.
1086
1087<procedure>(farey-sequence n) -> (list-of ratnum)</procedure>
1088
1089; n : integer
1090
1091Returns a list of the numbers in the {{n}}th Farey sequence; {{n}} must be positive.
1092
1093The {{n}}th Farey sequence is the sequence of all completely reduced rational
1094numbers from 0 to 1 which denominators are less than or equal to {{n}}.
1095
1096<enscript highlight="scheme">
1097> (farey-sequence 1)
1098(0 1)
1099> (farey-sequence 2)
1100(0 1/2 1)
1101> (farey-sequence 3)
1102(0 1/3 1/2 2/3 1)
1103</enscript>
1104
1105Wikipedia: [[https://en.wikipedia.org/wiki/Farey_sequence|Farey Sequence]]
1106
1107<procedure>(tangent-number n) -> integer</procedure>
1108
1109; n : integer
1110
1111Returns the {{n}}th tangent number; {{n}} must be nonnegative.
1112
1113<enscript highlight="scheme">
1114> (tangent-number 1)
11151
1116> (tangent-number 2)
11170
1118> (tangent-number 3)
11192
1120</enscript>
1121
1122MathWorld: [[http://mathworld.wolfram.com/TangentNumber.html|Tangent Number]]
1123
1124===== Combinatorics
1125
1126<procedure>(factorial n) -> integer</procedure>
1127
1128; n : integer
1129
1130Returns the factorial of {{n}}, which must be nonnegative. The factorial of
1131{{n}} is the number {{(* n (- n 1) (- n 2) ... 1)}}.
1132
1133<enscript highlight="scheme">
1134> (factorial 3)
11356
1136> (factorial 0)
11371
1138</enscript>
1139
1140Wikipedia: [[https://en.wikipedia.org/wiki/Factorial|Factorial]]
1141
1142<procedure>(binomial n k) -> integer</procedure>
1143
1144; n : integer
1145; k : integer
1146
1147Returns the number of ways to choose a set of k items from a set of n items;
1148i.e. the order of the k items is not significant. Both arguments must be
1149nonnegative.
1150
1151When {{k > n}}, {{(binomial n k) = 0}}. Otherwise, {{(binomial n k)}} is
1152equivalent to {{(/ (factorial n) (factorial k) (factorial (- n k)))}},
1153but computed more quickly.
1154
1155<enscript highlight="scheme">
1156> (binomial 5 3)
115710
1158</enscript>
1159
1160Wikipedia: [[https://en.wikipedia.org/wiki/Binomial_coefficient|Binomial Coefficient]]
1161
1162<procedure>(permutations n k) -> integer</procedure>
1163
1164; n : integer
1165; k : integer
1166
1167Returns the number of ways to choose a sequence of {{k}} items from a set of n
1168items; i.e. the order of the {{k}} items is significant. Both arguments must be
1169nonnegative.
1170
1171When {{k > n}}, {{(permutations n k) = 0}}. Otherwise, {{(permutations n k)}}
1172is equivalent to {{(/ (factorial n) (factorial (- n k)))}}.
1173
1174<enscript highlight="scheme">
1175> (permutations 5 3)
117660
1177</enscript>
1178
1179Wikipedia: [[https://en.wikipedia.org/wiki/Permutation#Permutations_in_combinatorics|Permutations]]
1180
1181<procedure>(multinomial n ks) -> integer</procedure>
1182
1183; n : integer
1184; ks : (list-of integer)
1185
1186A generalization of binomial to multiple sets of choices; e.g.
1187{{(multinomial n (list k0 k1 k2))}} is the number of ways to choose a set of
1188{{k0}} items, a set of {{k1}} items, and a set of {{k2}} items from a set of {{n}}
1189items. All arguments must be nonnegative.
1190
1191When {{(apply + ks) = n}}, this is equivalent to
1192{{(apply / (factorial n) (map factorial ks))}}. Otherwise, multinomial returns 0.
1193
1194<enscript highlight="scheme">
1195> (multinomial 5 '(3 2))
119610
1197> (= (multinomial 8 '(5 3))
1198     (binomial 8 5)
1199     (binomial 8 3))
1200#t
1201> (multinomial 10 '(5 3 2))
12022520
1203> (multinomial 0 '())
12041
1205> (multinomial 4 '(1 1))
12060
1207</enscript>
1208
1209Wikipedia: [[https://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients|Multinomial Coefficient]]
1210
1211<procedure>(partitions n) -> integer</procedure>
1212
1213; n : integer
1214
1215Returns the number of partitions of {{n}}, which must be nonnegative. A partition
1216of a positive integer {{n}} is a way of writing {{n}} as a sum of positive integers.
1217The number 3 has the partitions {{(+ 1 1 1)}}, {{(+ 1 2)}} and {{(+ 3)}}.
1218
1219<enscript highlight="scheme">
1220> (partitions 3)
12213
1222> (partitions 4)
12235
1224</enscript>
1225
1226Wikipedia: [[https://en.wikipedia.org/wiki/Partition_(number_theory)|Partition]]
1227
1228===== Polygonal numbers
1229
1230<procedure>(triangle-number? n) -> boolean</procedure>
1231<procedure>(square-number? n) -> boolean</procedure>
1232<procedure>(pentagonal-number? n) -> boolean</procedure>
1233<procedure>(hexagonal-number? n) -> boolean</procedure>
1234<procedure>(heptagonal-number? n) -> boolean</procedure>
1235<procedure>(octagonal-number? n) -> boolean</procedure>
1236
1237; n : integer
1238
1239These functions check whether the input is a polygonal number of the types
1240triangle, square, pentagonal, hexagonal, heptagonal and octogonal respectively.
1241
1242Wikipedia: [[https://en.wikipedia.org/wiki/Polygonal_number|Polygonal Number]]
1243
1244
1245<procedure>(triangle-number n) -> boolean</procedure>
1246<procedure>(sqr n) -> boolean</procedure>
1247<procedure>(pentagonal-number n) -> boolean</procedure>
1248<procedure>(hexagonal-number n) -> boolean</procedure>
1249<procedure>(heptagonal-number n) -> boolean</procedure>
1250<procedure>(octagonal-number n) -> boolean</procedure>
1251
1252; n : integer
1253
1254These functions return the {{n}}th polygonal number of the corresponding type
1255of polygonal number.
1256
1257===== Fractions
1258
1259<procedure>(mediant x y) -> ratnum</procedure>
1260
1261; x : ratnum
1262; y : ratnum
1263
1264Computes the mediant of the numbers {{x}} and {{y}}. The mediant of two
1265fractions {{p/q}} and {{r/s}} in their lowest term is the number
1266{{(p+r)/(q+s)}}.
1267
1268<enscript highlight="scheme">
1269> (mediant 1/2 5/6)
12703/4
1271</enscript>
1272
1273Wikipedia: [[https://en.wikipedia.org/wiki/Mediant_(mathematics)|Mediant]]
1274
1275===== The Quadratic Equation
1276
1277<procedure>(quadratic-solutions a b c) -> (list-of number)</procedure>
1278  a : number
1279  b : number
1280  c : number
1281
1282Returns a list of all real solutions to the equation a {{x^2 + bx + c = 0}}
1283with real coefficients.
1284
1285<enscript highlight="scheme">
1286> (quadratic-solutions 1 0 -1)
1287'(-1 1)
1288> (quadratic-solutions 1 2 1)
1289'(-1)
1290> (quadratic-solutions 1 0 1)
1291'()
1292</enscript>
1293
1294<procedure>(quadratic-integer-solutions a b c) -> (list-of integer)</procedure>
1295
1296; a : number
1297; b : number
1298; c : number
1299
1300Returns a list of all integer solutions to the equation a {{x^2 + bx + c = 0}}
1301with real coefficients.
1302
1303<enscript highlight="scheme">
1304> (quadratic-integer-solutions 1 0 -1)
1305'(-1 1)
1306> (quadratic-integer-solutions 1 0 -2)
1307'()
1308</enscript>
1309
1310<procedure>(quadratic-natural-solutions a b c) -> (list-of integer)</procedure>
1311
1312; a : number
1313; b : number
1314; c : number
1315
1316Returns a list of all natural solutions to the equation a {{x^2 + bx + c = 0}}
1317with real coefficients.
1318
1319<enscript highlight="scheme">
1320> (quadratic-natural-solutions 1 0 -1)
1321'(1)
1322> (quadratic-natural-solutions 1 0 -2)
1323'()
1324</enscript>
1325
1326<procedure>(complex-quadratic-solutions a b c) -> (list-of number)</procedure>
1327
1328; a : number
1329; b : number
1330; c : number
1331
1332Returns a list of all complex solutions to the equation a {{x^2 + bx + c = 0}}.
1333This function allows complex coeffecients.
1334
1335<enscript highlight="scheme">
1336> (complex-quadratic-solutions 1 0 1)
1337(0-1i 0+1i)
1338> (complex-quadratic-solutions 1 0 (sqrt -1))
1339(-0.7071067811865476+0.7071067811865475i 0.7071067811865476-0.7071067811865475i)
1340> (complex-quadratic-solutions 1 0 1)
1341(0-1i 0+1i)
1342</enscript>
1343
1344===== The group Zn and Primitive Roots
1345
1346The numbers 0, 1, ..., n-1 with addition and multiplication modulo {{n}} is a ring
1347called {{Zn}}.
1348
1349The group of units in {{Zn}} with respect to multiplication modulo {{n}} is
1350called {{Un}}.
1351
1352The order of an element {{x}} in {{Un}} is the least {{k>0}} such that {{x^k=1 mod n}}.
1353
1354A generator the group {{Un}} is called a primitive root modulo {{n}}. Note that {{g}} is a
1355primitive root if and only if {{order(g)=totient(n)}}. A group with a generator is
1356called cyclic.
1357
1358Wikipedia: [[https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n|The Group Zn]]
1359
1360<procedure>(unit-group n) -> (list-of integer)</procedure>
1361
1362; n : integer
1363
1364Returns a list of all elements of {{Un}}, the unit group modulo {{n}}. The
1365modulus {{n}} must be positive.
1366
1367<enscript highlight="scheme">
1368> (unit-group 5)
1369(1 2 3 4)
1370> (unit-group 6)
1371(1 5)
1372</enscript>
1373
1374<procedure>(unit-group-order x n) -> integer</procedure>
1375
1376; x : integer
1377; n : integer
1378
1379Returns the order of {{x}} in the group {{Un}}; both arguments must be
1380positive. If {{x}} and n are not coprime, {{(unit-group-order x n)}} raises an
1381error.
1382
1383<enscript highlight="scheme">
1384> (unit-group-order 2 5)
13854
1386> (unit-group-order 2 6)
1387Error: (unit-group-order) expected coprime arguments; given 2 and 6
1388</enscript>
1389
1390<procedure>(unit-group-orders n) -> (list-of positive-integer)</procedure>
1391
1392; n : integer
1393
1394Returns a list {{(list (unit-group-order x0 n) (unit-group-order x1 n) ...)}}
1395where {{x0}}, {{x1}}, {{...}} are the elements of {{Un}}. The modulus {{n}}
1396must be positive.
1397
1398<enscript highlight="scheme">
1399> (unit-group-orders 5)
1400(1 4 4 2)
1401> (map (cut unit-group-order <> 5) (unit-group 5))
1402(1 4 4 2)
1403</enscript>
1404
1405<procedure>(primitive-root? x n) -> boolean</procedure>
1406
1407; x : integer
1408; n : integer
1409
1410Returns {{#t}} if the element {{x}} in {{Un}} is a primitive root modulo {{n}},
1411otherwise {{#f}} is returned. An error is signaled if {{x}} is not a member of
1412{{Un}}. Both arguments must be positive.
1413
1414<enscript highlight="scheme">
1415> (primitive-root? 1 5)
1416#f
1417> (primitive-root? 2 5)
1418#t
1419> (primitive-root? 5 5)
1420Error: (primitive-root?) expected coprime arguments; given 5 and 5
1421</enscript>
1422
1423<procedure>(exists-primitive-root? n) -> boolean</procedure>
1424
1425; n : integer
1426
1427Returns {{#t}} if the group {{Un}} has a primitive root (i.e. it is cyclic),
1428otherwise {{#f}} is returned. In other words, {{#t}} is returned if {{n}} is
1429one of {{1}}, {{2}}, {{4}}, {{p^e}}, {{2*p^e}} where {{p}} is an odd prime, and
1430{{#f}} otherwise. The modulus {{n}} must be positive.
1431
1432<enscript highlight="scheme">
1433> (exists-primitive-root? 5)
1434#t
1435> (exists-primitive-root? 6)
1436#t
1437> (exists-primitive-root? 12)
1438#f
1439</enscript>
1440
1441<procedure>(primitive-root n) -> (or integer false)</procedure>
1442
1443Returns a primitive root of {{Un}} if one exists, otherwise {{#f}} is returned.
1444The modulus {{n}} must be positive.
1445
1446<enscript highlight="scheme">
1447> (primitive-root 5)
14482
1449> (primitive-root 6)
14505
1451</enscript>
1452
1453<procedure>(primitive-roots n) -> (list-of integer)</procedure>
1454
1455; n : integer
1456
1457Returns a list of all primitive roots of {Un}. The modulus {{n}} must be positive.
1458
1459<enscript highlight="scheme">
1460> (primitive-roots 3)
1461(2)
1462> (primitive-roots 5)
1463(2 3)
1464> (primitive-roots 6)
1465(5)
1466</enscript>
1467
1468=== Original documentation
1469
1470[[https://docs.racket-lang.org/math/]]
1471
1472=== Development status
1473
1474This egg is still largely under active development, with the exception of the
1475{{math.number-theory}} module, which is finished and ready for use.
1476
1477
1478=== Implementation caveats
1479
1480* It's possible some undefined behavior may occur with arguments of the wrong
1481  type, since a good amount of the original functions were originally defined
1482  in typed racket, which AFAIK would catch those and throw an exception.
1483
1484* In some places the original implementation references {{unsafe-}} {{fx}} and
1485  {{fl}} operators, but these are actually just aliased to safe operators. This
1486  implementation just uses chicken's {{chicken.fixnum}} module, which is
1487  unsafe. This may also lead to undefined behavior in some cases.
1488
1489=== Author
1490
1491Neil Toronto and Jens Axel SÞgaard for Racket
1492
1493=== Maintainer
1494
1495[[/users/diego-mundo|Diego A. Mundo]]
1496
1497=== Repository
1498
1499[[https://github.com/dieggsy/chicken-math]]
1500
1501=== License
1502
1503GPL-3.0
1504
1505=== Version History
1506
1507; 0.3.0 : Finish (math base) and (math flonum), bug and typo fixes, credit original authors
1508; 0.2.3 : Fix broken .egg file
1509; 0.2.2 : Re-organize internals, add (math base constants)
1510; 0.2.1 : Minor bug fixes
1511; 0.2.0 : Update (math number-theory quadratic) to reflect upstream
1512; 0.1.0 : Initial release
Note: See TracBrowser for help on using the repository browser.