Debian Codegraph @

lib/srfi/194/zipf-zri.scm

raw
1 ;;;
2 ;;; Grafted from srfi-194 reference implementation
3 ;;; Original code by Linas Vepstas
4 ;;;
5
6 (define-module srfi.194.zipf-zri
7 (use srfi.194)
8 (export make-zipf-generator)
9 )
10 (select-module srfi.194.zipf-zri)
11
12 ;
13 ; zipf-zri.scm
14 ; Create a Zipf random distribution.
15 ;
16 ; Created by Linas Vepstas 10 July 2020
17 ; Nominated for inclusion in srfi-194
18 ;
19 ; Not optimized for speed!
20 ;
21 ; Implementation from ZRI algorithm presented in the paper:
22 ; "Rejection-inversion to generate variates from monotone discrete
23 ; distributions", Wolfgang Hörmann and Gerhard Derflinger
24 ; ACM TOMACS 6.3 (1996): 169-184
25 ;
26 ; Hörmann and Derflinger use "q" everywhere, when they really mean "s".
27 ; Thier "q" is not the standard q-series deformation. Its just "s".
28 ; The notation in the code below differs from the article to reflect
29 ; conventional usage.
30 ;
31 ;------------------------------------------------------------------
32 ;
33 ; The Hurwicz zeta distribution 1 / (k+q)^s for 1 <= k <= n integer
34 ; The Zipf distribution is recovered by setting q=0.
35 ;
36 ; The exponent `s` must be a real number not equal to 1.
37 ; Accuracy is diminished for |1-s|< 1e-6. The accuracy is roughly
38 ; equal to 1e-15 / |1-s| where 1e-15 == 64-bit double-precision ULP.
39 ;
40 (define (make-zipf-generator/zri n s q)
41
42 ; The hat function h(x) = 1 / (x+q)^s
43 (define (hat x)
44 (expt (+ x q) (- s)))
45
46 (define _1-s (- 1 s))
47 (define oms (/ 1 _1-s))
48
49 ; The integral of hat(x)
50 ; H(x) = (x+q)^{1-s} / (1-s)
51 ; Note that H(x) is always negative.
52 (define (big-h x)
53 (/ (expt (+ q x) _1-s) _1-s))
54
55 ; The inverse function of H(x)
56 ; H^{-1}(y) = -q + (y(1-s))^{1/(1-s)}
57 (define (big-h-inv y)
58 (- (expt (* y _1-s) oms) q))
59
60 ; Lower and upper bounds for the uniform random generator.
61 (define big-h-half (- (big-h 1.5) (hat 1)))
62 (define big-h-n (big-h (+ n 0.5)))
63
64 ; Rejection cut
65 (define cut (- 1 (big-h-inv (- (big-h 1.5) (hat 1)))))
66
67 ; Uniform distribution
68 (define dist (make-random-real-generator big-h-half big-h-n))
69
70 ; Attempt to hit the dartboard. Return #f if we fail,
71 ; otherwise return an integer between 1 and n.
72 (define (try)
73 (define u (dist))
74 (define x (big-h-inv u))
75 (define kflt (floor (+ x 0.5)))
76 (define k (exact kflt))
77 (if (and (< 0 k)
78 (or
79 (<= (- k x) cut)
80 (>= u (- (big-h (+ k 0.5)) (hat k))))) k #f))
81
82 ; Did we hit the dartboard? If not, try again.
83 (define (loop-until)
84 (define k (try))
85 (if k k (loop-until)))
86
87 ; Return the generator.
88 loop-until)
89
90 ;------------------------------------------------------------------
91 ;
92 ; The Hurwicz zeta distribution 1 / (k+q)^s for 1 <= k <= n integer
93 ; The Zipf distribution is recovered by setting q=0.
94 ;
95 ; The exponent `s` must be a real number close to 1.
96 ; Accuracy is diminished for |1-s|> 2e-4. The accuracy is roughly
97 ; equal to 0.05 * |1-s|^4 due to exp(1-s) being expanded to 4 terms.
98 ;
99 ; This handles the special case of s==1 perfectly.
100 (define (make-zipf-generator/one n s q)
101
102 (define _1-s (- 1 s))
103
104 ; The hat function h(x) = 1 / (x+q)^s
105 ; Written for s->1 i.e. 1/(x+q)(x+q)^{s-1}
106 (define (hat x)
107 (define xpq (+ x q))
108 (/ (expt xpq _1-s) xpq))
109
110 ; Expansion of exn(y) = [exp(y(1-s))-1]/(1-s) for s->1
111 ; Expanded to 4th order.
112 ; Should equal this:
113 ;;; (define (exn lg) (/ (- (exp (* _1-s lg)) 1) _1-s))
114 ; but more accurate for s near 1.0
115 (define (exn lg)
116 (define (trm n u lg) (* lg (+ 1 (/ (* _1-s u) n))))
117 (trm 2 (trm 3 (trm 4 1 lg) lg) lg))
118
119 ; Expansion of lg(y) = [log(1 + y(1-s))] / (1-s) for s->1
120 ; Expanded to 4th order.
121 ; Should equal this:
122 ;;; (define (lg y) (/ (log (+ 1 (* y _1-s))) _1-s))
123 ; but more accurate for s near 1.0
124 (define (lg y)
125 (define yms (* y _1-s))
126 (define (trm n u r) (- (/ 1 n) (* u r)))
127 (* y (trm 1 yms (trm 2 yms (trm 3 yms (trm 4 yms 0))))))
128
129 ; The integral of hat(x) defined at s==1
130 ; H(x) = [exp{(1-s) log(x+q)} - 1]/(1-s)
131 ; Should equal this:
132 ;;; (define (big-h x) (/ (- (exp (* _1-s (log (+ q x)))) 1) _1-s))
133 ; but expanded so that it's more accurate for s near 1.0
134 (define (big-h x)
135 (exn (log (+ q x))))
136
137 ; The inverse function of H(x)
138 ; H^{-1}(y) = -q + (1 + y(1-s))^{1/(1-s)}
139 ; Should equal this:
140 ;;; (define (big-h-inv y) (- (expt (+ 1 (* y _1-s)) (/ 1 _1-s)) q ))
141 ; but expanded so that it's more accurate for s near 1.0
142 (define (big-h-inv y)
143 (- (exp (lg y)) q))
144
145 ; Lower and upper bounds for the uniform random generator.
146 (define big-h-half (- (big-h 1.5) (hat 1)))
147
148 (define big-h-n (big-h (+ n 0.5)))
149
150 ; Rejection cut
151 (define cut (- 1 (big-h-inv (- (big-h 1.5) (/ 1 (+ 1 q))))))
152
153 ; Uniform distribution
154 (define dist (make-random-real-generator big-h-half big-h-n))
155
156 ; Attempt to hit the dartboard. Return #f if we fail,
157 ; otherwise return an integer between 1 and n.
158 (define (try)
159 (define u (dist))
160 (define x (big-h-inv u))
161 (define kflt (floor (+ x 0.5)))
162 (define k (exact kflt))
163 (if (and (< 0 k)
164 (or
165 (<= (- k x) cut)
166 (>= u (- (big-h (+ k 0.5)) (hat k))))) k #f))
167
168 ; Did we hit the dartboard? If not, try again.
169 (define (loop-until)
170 (define k (try))
171 (if k k (loop-until)))
172
173 ; Return the generator.
174 loop-until)
175
176 ;------------------------------------------------------------------
177 ;
178 ; (make-zipf-generator n [s [q]])
179 ;
180 ; The Hurwicz zeta distribution 1 / (k+q)^s for 1 <= k <= n integer
181 ; The Zipf distribution is recovered by setting q=0.
182 ; If `q` is not specified, 0 is assumed.
183 ; If `s` is not specified, 1 is assumed.
184 ;
185 ; Valid for real -10 < s < 100 (otherwise overflows likely)
186 ; Valid for real -0.5 < q < 2e8 (otherwise overflows likely)
187 ; Valid for integer 1 <= k < int-max
188 ;
189 ; Example usage:
190 ; (define zgen (make-zipf-generator 50 1.01 0))
191 ; (generator->list zgen 10)
192 ;
193 (define make-zipf-generator
194 (case-lambda
195 ((n)
196 (make-zipf-generator n 1.0 0.0))
197 ((n s)
198 (make-zipf-generator n s 0.0))
199 ((n s q)
200 (if (< 1e-5 (abs (- 1 s)))
201 (make-zipf-generator/zri n s q)
202 (make-zipf-generator/one n s q)))))