1 /* Exercise mpz_bin_ui and mpz_bin_uiui.
2
3 Copyright 2000, 2001, 2010, 2012, 2018, 2020 Free Software Foundation, Inc.
4
5 This file is part of the GNU MP Library test suite.
6
7 The GNU MP Library test suite is free software; you can redistribute it
8 and/or modify it under the terms of the GNU General Public License as
9 published by the Free Software Foundation; either version 3 of the License,
10 or (at your option) any later version.
11
12 The GNU MP Library test suite is distributed in the hope that it will be
13 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
15 Public License for more details.
16
17 You should have received a copy of the GNU General Public License along with
18 the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */
19
20 #include <stdio.h>
21 #include <stdlib.h>
22 #include "gmp-impl.h"
23 #include "tests.h"
24
25 /* Default number of generated tests. */
26 #define COUNT 700
27
28 void
29 try_mpz_bin_ui (mpz_srcptr want, mpz_srcptr n, unsigned long k)
30 {
31 mpz_t got;
32
33 mpz_init (got);
34 mpz_bin_ui (got, n, k);
35 MPZ_CHECK_FORMAT (got);
36 if (mpz_cmp (got, want) != 0)
37 {
38 printf ("mpz_bin_ui wrong\n");
39 printf (" n="); mpz_out_str (stdout, 10, n); printf ("\n");
40 printf (" k=%lu\n", k);
41 printf (" got="); mpz_out_str (stdout, 10, got); printf ("\n");
42 printf (" want="); mpz_out_str (stdout, 10, want); printf ("\n");
43 abort();
44 }
45 mpz_clear (got);
46 }
47
48
49 void
50 try_mpz_bin_uiui (mpz_srcptr want, unsigned long n, unsigned long k)
51 {
52 mpz_t got;
53
54 mpz_init (got);
55 mpz_bin_uiui (got, n, k);
56 MPZ_CHECK_FORMAT (got);
57 if (mpz_cmp (got, want) != 0)
58 {
59 printf ("mpz_bin_uiui wrong\n");
60 printf (" n=%lu\n", n);
61 printf (" k=%lu\n", k);
62 printf (" got="); mpz_out_str (stdout, 10, got); printf ("\n");
63 printf (" want="); mpz_out_str (stdout, 10, want); printf ("\n");
64 abort();
65 }
66 mpz_clear (got);
67 }
68
69
70 void
71 samples (void)
72 {
73 static const struct {
74 const char *n;
75 unsigned long k;
76 const char *want;
77 } data[] = {
78
79 { "0", 123456, "0" },
80 { "1", 543210, "0" },
81 { "2", 123321, "0" },
82 { "3", 234567, "0" },
83 { "10", 23456, "0" },
84
85 /* negatives, using bin(-n,k)=bin(n+k-1,k) */
86 { "-1", 0, "1" },
87 { "-1", 1, "-1" },
88 { "-1", 2, "1" },
89 { "-1", 3, "-1" },
90 { "-1", 4, "1" },
91
92 { "-2", 0, "1" },
93 { "-2", 1, "-2" },
94 { "-2", 2, "3" },
95 { "-2", 3, "-4" },
96 { "-2", 4, "5" },
97 { "-2", 5, "-6" },
98 { "-2", 6, "7" },
99
100 { "-3", 0, "1" },
101 { "-3", 1, "-3" },
102 { "-3", 2, "6" },
103 { "-3", 3, "-10" },
104 { "-3", 4, "15" },
105 { "-3", 5, "-21" },
106 { "-3", 6, "28" },
107
108 /* A few random values */
109 { "41", 20, "269128937220" },
110 { "62", 37, "147405545359541742" },
111 { "50", 18, "18053528883775" },
112 { "149", 21, "19332950844468483467894649" },
113 };
114
115 mpz_t n, want;
116 int i;
117
118 mpz_init (n);
119 mpz_init (want);
120
121 for (i = 0; i < numberof (data); i++)
122 {
123 mpz_set_str_or_abort (n, data[i].n, 0);
124 mpz_set_str_or_abort (want, data[i].want, 0);
125
126 try_mpz_bin_ui (want, n, data[i].k);
127
128 if (mpz_fits_ulong_p (n))
129 try_mpz_bin_uiui (want, mpz_get_ui (n), data[i].k);
130 }
131
132 mpz_clear (n);
133 mpz_clear (want);
134 }
135
136
137 /* Test some bin(2k,k) cases. This produces some biggish numbers to
138 exercise the limb accumulating code. */
139 void
140 twos (int count)
141 {
142 mpz_t n, want;
143 unsigned long k;
144
145 mpz_init (n);
146
147 mpz_init_set_ui (want, (unsigned long) 2);
148 for (k = 1; k < count; k++)
149 {
150 mpz_set_ui (n, 2*k);
151 try_mpz_bin_ui (want, n, k);
152
153 try_mpz_bin_uiui (want, 2*k, k);
154
155 mpz_mul_ui (want, want, 2*(2*k+1));
156 mpz_fdiv_q_ui (want, want, k+1);
157 }
158
159 mpz_clear (n);
160 mpz_clear (want);
161 }
162
163 /* Test some random bin(n,k) cases. This produces some biggish
164 numbers to exercise the limb accumulating code. */
165 void
166 randomwalk (int count)
167 {
168 mpz_t n_z, want, tmp;
169 unsigned long n, k, i, r;
170 int tests;
171 gmp_randstate_ptr rands;
172
173 rands = RANDS;
174 mpz_init (n_z);
175
176 k = 3;
177 n = 12;
178 mpz_init_set_ui (want, (unsigned long) 220); /* binomial(12,3) = 220 */
179
180 for (tests = 1; tests < count; tests++)
181 {
182 r = gmp_urandomm_ui (rands, 62) + 1;
183 for (i = r & 7; i > 0; i--)
184 {
185 n++; k++;
186 mpz_mul_ui (want, want, n);
187 mpz_divexact_ui (want, want, k);
188 }
189 for (i = r >> 3; i > 0; i--)
190 {
191 n++;
192 mpz_mul_ui (want, want, n);
193 mpz_divexact_ui (want, want, n - k);
194 }
195
196 mpz_set_ui (n_z, n);
197 try_mpz_bin_ui (want, n_z, k);
198
199 try_mpz_bin_uiui (want, n, k);
200 }
201
202 k = 2;
203 mpz_urandomb (n_z, rands, 200);
204 mpz_mul (want, n_z, n_z); /* want = n_z ^ 2 */
205 mpz_sub (want, want, n_z); /* want = n_z ^ 2 - n_z = n_z (n_z- 1) */
206 mpz_tdiv_q_2exp (want, want, 1); /* want = n_z (n_z- 1) / 2 = binomial (n_z, 2) */
207 mpz_init (tmp);
208 for (tests = 1; tests < count; tests++)
209 {
210 r = gmp_urandomm_ui (rands, 62) + 1;
211 for (i = r & 7; i > 0; i--)
212 {
213 k++;
214 mpz_add_ui (n_z, n_z, 1);
215 mpz_mul (want, want, n_z);
216 mpz_divexact_ui (want, want, k);
217 }
218 for (i = r >> 3; i > 0; i--)
219 {
220 mpz_add_ui (n_z, n_z, 1);
221 mpz_mul (want, want, n_z);
222 mpz_sub_ui (tmp, n_z, k);
223 mpz_divexact (want, want, tmp);
224 }
225
226 try_mpz_bin_ui (want, n_z, k);
227 }
228
229 mpz_clear (tmp);
230 mpz_clear (n_z);
231 mpz_clear (want);
232 }
233
234 /* Test some random bin(n,k) cases. This produces some biggish
235 numbers to exercise the limb accumulating code. */
236 void
237 randomwalk_down (int count)
238 {
239 mpz_t n_z, want, tmp;
240 unsigned long n, k, i, r;
241 int tests;
242 gmp_randstate_ptr rands;
243
244 rands = RANDS;
245 mpz_init (n_z);
246 mpz_init (tmp);
247
248 k = 2;
249 n = ULONG_MAX;
250 mpz_init_set_ui (want, n);
251 mpz_mul_ui (want, want, n >> 1);
252
253 for (tests = 1; tests < count; tests++)
254 {
255 r = gmp_urandomm_ui (rands, 62) + 1;
256 for (i = r & 7; i > 0; i--)
257 {
258 mpz_mul_ui (want, want, n - k);
259 ++k;
260 mpz_divexact_ui (want, want, k);
261 }
262 for (i = r >> 3; i > 0; i--)
263 {
264 mpz_mul_ui (want, want, n - k);
265 mpz_divexact_ui (want, want, n);
266 --n;
267 }
268
269 mpz_set_ui (n_z, n);
270 try_mpz_bin_ui (want, n_z, n - k);
271
272 try_mpz_bin_uiui (want, n, n - k);
273 }
274
275 mpz_clear (tmp);
276 mpz_clear (n_z);
277 mpz_clear (want);
278 }
279
280
281 /* Test all bin(n,k) cases, with 0 <= k <= n + 1 <= count. */
282 void
283 smallexaustive (unsigned int count)
284 {
285 mpz_t n_z, want;
286 unsigned long n, k;
287
288 mpz_init (n_z);
289 mpz_init (want);
290
291 for (n = 0; n < count; n++)
292 {
293 mpz_set_ui (want, (unsigned long) 1);
294 mpz_set_ui (n_z, n);
295 for (k = 0; k <= n; k++)
296 {
297 try_mpz_bin_ui (want, n_z, k);
298 try_mpz_bin_uiui (want, n, k);
299 mpz_mul_ui (want, want, n - k);
300 mpz_fdiv_q_ui (want, want, k + 1);
301 }
302 try_mpz_bin_ui (want, n_z, k);
303 try_mpz_bin_uiui (want, n, k);
304 }
305
306 mpz_clear (n_z);
307 mpz_clear (want);
308 }
309
310 int
311 main (int argc, char **argv)
312 {
313 int count;
314
315 count = COUNT;
316 TESTS_REPS (count, argv, argc);
317
318 tests_start ();
319
320 samples ();
321 smallexaustive (count >> 4);
322 twos (count >> 1);
323 randomwalk (count - (count >> 1));
324 randomwalk_down (count >> 1);
325
326 tests_end ();
327 exit (0);
328 }