1 /* Exercise mpz_bin_ui and mpz_bin_uiui. 2 3 Copyright 2000, 2001, 2010, 2012 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.h" 23 #include "gmp-impl.h" 24 #include "tests.h" 25 26 /* Default number of generated tests. */ 27 #define COUNT 700 28 29 void 30 try_mpz_bin_ui (mpz_srcptr want, mpz_srcptr n, unsigned long k) 31 { 32 mpz_t got; 33 34 mpz_init (got); 35 mpz_bin_ui (got, n, k); 36 MPZ_CHECK_FORMAT (got); 37 if (mpz_cmp (got, want) != 0) 38 { 39 printf ("mpz_bin_ui wrong\n"); 40 printf (" n="); mpz_out_str (stdout, 10, n); printf ("\n"); 41 printf (" k=%lu\n", k); 42 printf (" got="); mpz_out_str (stdout, 10, got); printf ("\n"); 43 printf (" want="); mpz_out_str (stdout, 10, want); printf ("\n"); 44 abort(); 45 } 46 mpz_clear (got); 47 } 48 49 50 void 51 try_mpz_bin_uiui (mpz_srcptr want, unsigned long n, unsigned long k) 52 { 53 mpz_t got; 54 55 mpz_init (got); 56 mpz_bin_uiui (got, n, k); 57 MPZ_CHECK_FORMAT (got); 58 if (mpz_cmp (got, want) != 0) 59 { 60 printf ("mpz_bin_uiui wrong\n"); 61 printf (" n=%lu\n", n); 62 printf (" k=%lu\n", k); 63 printf (" got="); mpz_out_str (stdout, 10, got); printf ("\n"); 64 printf (" want="); mpz_out_str (stdout, 10, want); printf ("\n"); 65 abort(); 66 } 67 mpz_clear (got); 68 } 69 70 71 void 72 samples (void) 73 { 74 static const struct { 75 const char *n; 76 unsigned long k; 77 const char *want; 78 } data[] = { 79 80 { "0", 123456, "0" }, 81 { "1", 543210, "0" }, 82 { "2", 123321, "0" }, 83 { "3", 234567, "0" }, 84 { "10", 23456, "0" }, 85 86 /* negatives, using bin(-n,k)=bin(n+k-1,k) */ 87 { "-1", 0, "1" }, 88 { "-1", 1, "-1" }, 89 { "-1", 2, "1" }, 90 { "-1", 3, "-1" }, 91 { "-1", 4, "1" }, 92 93 { "-2", 0, "1" }, 94 { "-2", 1, "-2" }, 95 { "-2", 2, "3" }, 96 { "-2", 3, "-4" }, 97 { "-2", 4, "5" }, 98 { "-2", 5, "-6" }, 99 { "-2", 6, "7" }, 100 101 { "-3", 0, "1" }, 102 { "-3", 1, "-3" }, 103 { "-3", 2, "6" }, 104 { "-3", 3, "-10" }, 105 { "-3", 4, "15" }, 106 { "-3", 5, "-21" }, 107 { "-3", 6, "28" }, 108 109 /* A few random values */ 110 { "41", 20, "269128937220" }, 111 { "62", 37, "147405545359541742" }, 112 { "50", 18, "18053528883775" }, 113 { "149", 21, "19332950844468483467894649" }, 114 }; 115 116 mpz_t n, want; 117 int i; 118 119 mpz_init (n); 120 mpz_init (want); 121 122 for (i = 0; i < numberof (data); i++) 123 { 124 mpz_set_str_or_abort (n, data[i].n, 0); 125 mpz_set_str_or_abort (want, data[i].want, 0); 126 127 try_mpz_bin_ui (want, n, data[i].k); 128 129 if (mpz_fits_ulong_p (n)) 130 try_mpz_bin_uiui (want, mpz_get_ui (n), data[i].k); 131 } 132 133 mpz_clear (n); 134 mpz_clear (want); 135 } 136 137 138 /* Test some bin(2k,k) cases. This produces some biggish numbers to 139 exercise the limb accumulating code. */ 140 void 141 twos (int count) 142 { 143 mpz_t n, want; 144 unsigned long k; 145 146 mpz_init (n); 147 mpz_init (want); 148 149 mpz_set_ui (want, (unsigned long) 2); 150 for (k = 1; k < count; k++) 151 { 152 mpz_set_ui (n, 2*k); 153 try_mpz_bin_ui (want, n, k); 154 155 try_mpz_bin_uiui (want, 2*k, k); 156 157 mpz_mul_ui (want, want, 2*(2*k+1)); 158 mpz_fdiv_q_ui (want, want, k+1); 159 } 160 161 mpz_clear (n); 162 mpz_clear (want); 163 } 164 165 /* Test some random bin(n,k) cases. This produces some biggish 166 numbers to exercise the limb accumulating code. */ 167 void 168 randomwalk (int count) 169 { 170 mpz_t n_z, want; 171 unsigned long n, k, i, r; 172 int tests; 173 gmp_randstate_ptr rands; 174 175 rands = RANDS; 176 mpz_init (n_z); 177 mpz_init (want); 178 179 k = 3; 180 n = 12; 181 mpz_set_ui (want, (unsigned long) 220); /* binomial(12,3) = 220 */ 182 183 for (tests = 1; tests < count; tests++) 184 { 185 r = gmp_urandomm_ui (rands, 62) + 1; 186 for (i = r & 7; i > 0; i--) 187 { 188 n++; k++; 189 mpz_mul_ui (want, want, n); 190 mpz_fdiv_q_ui (want, want, k); 191 } 192 for (i = r >> 3; i > 0; i--) 193 { 194 n++; 195 mpz_mul_ui (want, want, n); 196 mpz_fdiv_q_ui (want, want, n - k); 197 } 198 199 mpz_set_ui (n_z, n); 200 try_mpz_bin_ui (want, n_z, k); 201 202 try_mpz_bin_uiui (want, n, k); 203 } 204 205 mpz_clear (n_z); 206 mpz_clear (want); 207 } 208 209 210 /* Test all bin(n,k) cases, with 0 <= k <= n + 1 <= count. */ 211 void 212 smallexaustive (unsigned int count) 213 { 214 mpz_t n_z, want; 215 unsigned long n, k; 216 217 mpz_init (n_z); 218 mpz_init (want); 219 220 for (n = 0; n < count; n++) 221 { 222 mpz_set_ui (want, (unsigned long) 1); 223 mpz_set_ui (n_z, n); 224 for (k = 0; k <= n; k++) 225 { 226 try_mpz_bin_ui (want, n_z, k); 227 try_mpz_bin_uiui (want, n, k); 228 mpz_mul_ui (want, want, n - k); 229 mpz_fdiv_q_ui (want, want, k + 1); 230 } 231 try_mpz_bin_ui (want, n_z, k); 232 try_mpz_bin_uiui (want, n, k); 233 } 234 235 mpz_clear (n_z); 236 mpz_clear (want); 237 } 238 239 int 240 main (int argc, char **argv) 241 { 242 int count; 243 244 if (argc > 1) 245 { 246 char *end; 247 count = strtol (argv[1], &end, 0); 248 if (*end || count <= 0) 249 { 250 fprintf (stderr, "Invalid test count: %s.\n", argv[1]); 251 return 1; 252 } 253 } 254 else 255 count = COUNT; 256 257 tests_start (); 258 259 samples (); 260 smallexaustive (count >> 4); 261 twos (count >> 1); 262 randomwalk (count - (count >> 1)); 263 264 tests_end (); 265 exit (0); 266 } 267