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 http://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, i, r; 216 int tests; 217 gmp_randstate_ptr rands; 218 219 mpz_init (n_z); 220 mpz_init (want); 221 222 for (n = 0; n < count; n++) 223 { 224 mpz_set_ui (want, (unsigned long) 1); 225 mpz_set_ui (n_z, n); 226 for (k = 0; k <= n; k++) 227 { 228 try_mpz_bin_ui (want, n_z, k); 229 try_mpz_bin_uiui (want, n, k); 230 mpz_mul_ui (want, want, n - k); 231 mpz_fdiv_q_ui (want, want, k + 1); 232 } 233 try_mpz_bin_ui (want, n_z, k); 234 try_mpz_bin_uiui (want, n, k); 235 } 236 237 mpz_clear (n_z); 238 mpz_clear (want); 239 } 240 241 int 242 main (int argc, char **argv) 243 { 244 int count; 245 246 if (argc > 1) 247 { 248 char *end; 249 count = strtol (argv[1], &end, 0); 250 if (*end || count <= 0) 251 { 252 fprintf (stderr, "Invalid test count: %s.\n", argv[1]); 253 return 1; 254 } 255 } 256 else 257 count = COUNT; 258 259 tests_start (); 260 261 samples (); 262 smallexaustive (count >> 4); 263 twos (count >> 1); 264 randomwalk (count - (count >> 1)); 265 266 tests_end (); 267 exit (0); 268 } 269