1 /* Exercise mpz_fac_ui and mpz_bin_uiui.
2
3 Copyright 2000-2002, 2012, 2013, 2017-2018 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
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
32 void
try_mpz_bin_uiui(mpz_srcptr want,unsigned long n,unsigned long k)33 try_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. */
52 void
bin_smallexaustive(unsigned int count)53 bin_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. */
76 void
fac_smallexaustive(unsigned int limit)77 fac_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
checkWilson(mpz_t f,unsigned long n)103 void 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
128 void
checkprimes(unsigned long p1,unsigned long p2,unsigned long p3)129 checkprimes (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
162 void
testmain(int argc,char * argv[])163 testmain (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