t-comb.c revision 1.1.1.3
1/* Exercise mpz_fac_ui and mpz_bin_uiui. 2 3Copyright 2000-2002, 2012, 2013, 2017-2018 Free Software Foundation, Inc. 4 5This file is part of the GNU MP Library test suite. 6 7The GNU MP Library test suite is free software; you can redistribute it 8and/or modify it under the terms of the GNU General Public License as 9published by the Free Software Foundation; either version 3 of the License, 10or (at your option) any later version. 11 12The GNU MP Library test suite is distributed in the hope that it will be 13useful, but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General 15Public License for more details. 16 17You should have received a copy of the GNU General Public License along with 18the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */ 19 20#include <stdio.h> 21#include <stdlib.h> 22 23#include "testutils.h" 24 25/* Usage: t-fac_ui [x|num] 26 27 With no arguments testing goes up to the initial value of "limit" below. 28 With a number argument tests are carried that far, or with a literal "x" 29 tests are continued without limit (this being meant only for development 30 purposes). */ 31 32void 33try_mpz_bin_uiui (mpz_srcptr want, unsigned long n, unsigned long k) 34{ 35 mpz_t got; 36 37 mpz_init (got); 38 mpz_bin_uiui (got, n, k); 39 if (mpz_cmp (got, want) != 0) 40 { 41 printf ("mpz_bin_uiui wrong\n"); 42 printf (" n=%lu\n", n); 43 printf (" k=%lu\n", k); 44 printf (" got="); mpz_out_str (stdout, 10, got); printf ("\n"); 45 printf (" want="); mpz_out_str (stdout, 10, want); printf ("\n"); 46 abort(); 47 } 48 mpz_clear (got); 49} 50 51/* Test all bin(n,k) cases, with 0 <= k <= n + 1 <= count. */ 52void 53bin_smallexaustive (unsigned int count) 54{ 55 mpz_t want; 56 unsigned long n, k; 57 58 mpz_init (want); 59 60 for (n = 0; n < count; n++) 61 { 62 mpz_set_ui (want, 1); 63 for (k = 0; k <= n; k++) 64 { 65 try_mpz_bin_uiui (want, n, k); 66 mpz_mul_ui (want, want, n - k); 67 mpz_fdiv_q_ui (want, want, k + 1); 68 } 69 try_mpz_bin_uiui (want, n, k); 70 } 71 72 mpz_clear (want); 73} 74 75/* Test all fac(n) cases, with 0 <= n <= limit. */ 76void 77fac_smallexaustive (unsigned int limit) 78{ 79 mpz_t f, r; 80 unsigned long n; 81 mpz_init_set_si (f, 1); /* 0! = 1 */ 82 mpz_init (r); 83 84 for (n = 0; n < limit; n++) 85 { 86 mpz_fac_ui (r, n); 87 88 if (mpz_cmp (f, r) != 0) 89 { 90 printf ("mpz_fac_ui(%lu) wrong\n", n); 91 printf (" got "); mpz_out_str (stdout, 10, r); printf("\n"); 92 printf (" want "); mpz_out_str (stdout, 10, f); printf("\n"); 93 abort (); 94 } 95 96 mpz_mul_ui (f, f, n+1); /* (n+1)! = n! * (n+1) */ 97 } 98 99 mpz_clear (f); 100 mpz_clear (r); 101} 102 103void checkWilson (mpz_t f, unsigned long n) 104{ 105 unsigned long m, a; 106 107 mpz_2fac_ui (f, 2 * n - 1); 108 109 a = mpz_fdiv_q_ui (f, f, n); 110 m = mpz_fdiv_ui (f, n); 111 if ((m != n - 1) || (a != 0)) 112 { 113 printf ("mpz_2fac_ui(%lu) wrong\n", 2 * n - 1); 114 printf (" Wilson's theorem not verified: got (%lu, %lu), expected (0, %lu).\n", a, m, n - 1); 115 abort (); 116 } 117 118 mpz_fac_ui (f, n - 1); 119 m = mpz_fdiv_ui (f, n); 120 if ( m != n - 1) 121 { 122 printf ("mpz_fac_ui(%lu) wrong\n", n - 1); 123 printf (" Wilson's theorem not verified: got %lu, expected %lu.\n",m ,n - 1); 124 abort (); 125 } 126} 127 128void 129checkprimes (unsigned long p1, unsigned long p2, unsigned long p3) 130{ 131 mpz_t b, f; 132 133 if (p1 - 1 != p2 - 1 + p3 - 1) 134 { 135 printf ("checkprimes(%lu, %lu, %lu) wrong\n", p1, p2, p3); 136 printf (" %lu - 1 != %lu - 1 + %lu - 1 \n", p1, p2, p3); 137 abort (); 138 } 139 140 mpz_init (b); 141 mpz_init (f); 142 143 checkWilson (b, p1); /* b = (p1-1)! */ 144 checkWilson (f, p2); /* f = (p2-1)! */ 145 mpz_divexact (b, b, f); 146 checkWilson (f, p3); /* f = (p3-1)! */ 147 mpz_divexact (b, b, f); /* b = (p1-1)!/((p2-1)!(p3-1)!) */ 148 mpz_bin_uiui (f, p1 - 1, p2 - 1); 149 if (mpz_cmp (f, b) != 0) 150 { 151 printf ("checkprimes(%lu, %lu, %lu) wrong\n", p1, p2, p3); 152 printf (" got "); mpz_out_str (stdout, 10, b); printf("\n"); 153 printf (" want "); mpz_out_str (stdout, 10, f); printf("\n"); 154 abort (); 155 } 156 157 mpz_clear (b); 158 mpz_clear (f); 159 160} 161 162void 163testmain (int argc, char *argv[]) 164{ 165 unsigned long limit = 128; 166 167 if (argc > 1 && argv[1][0] == 'x') 168 limit = ~ limit; 169 else if (argc > 1) 170 limit = atoi (argv[1]); 171 172 checkprimes(1009, 733, 277); 173 fac_smallexaustive (limit); 174 bin_smallexaustive (limit); 175} 176