1 /* Test mpz_gcd_ui.
2
3 Copyright 2003 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 "gmp-impl.h"
24 #include "tests.h"
25
26 /* Check mpz_gcd_ui doesn't try to return a value out of range.
27 This was wrong in gmp 4.1.2 with a long long limb. */
28 static void
29 check_ui_range (void)
30 {
31 unsigned long got;
32 mpz_t x;
33 int i;
34
35 mpz_init_set_ui (x, ULONG_MAX);
36
37 for (i = 0; i < 20; i++)
38 {
39 mpz_mul_2exp (x, x, 1L);
40 got = mpz_gcd_ui (NULL, x, 0L);
41 if (got != 0)
42 {
43 printf ("mpz_gcd_ui (ULONG_MAX*2^%d, 0)\n", i);
44 printf (" return %#lx\n", got);
45 printf (" should be 0\n");
46 abort ();
47 }
48 }
49
50 mpz_clear (x);
51 }
52
53 static void
54 check_ui_factors (void)
55 {
56 #define NUM_FACTORS 9
57 static const char* factors[NUM_FACTORS] = {
58 "641", "274177", "3", "5", "17", "257", "65537",
59 "59649589127497217", "1238926361552897" };
60 unsigned long got;
61 mpz_t x, b, d, f, g;
62 int i, j;
63 gmp_randstate_ptr rands;
64
65 if (GMP_NUMB_BITS < 5 || GMP_NUMB_BITS == 8
66 || GMP_NUMB_BITS == 16 || GMP_NUMB_BITS > 511)
67 {
68 printf ("No usable factors for 2^%i+1.\n", GMP_NUMB_BITS);
69 return;
70 }
71
72 mpz_init (x);
73 mpz_init (d);
74 mpz_init (f);
75 mpz_init (g);
76
77 mpz_setbit (x, GMP_NUMB_BITS);
78 mpz_add_ui (x, x, 1);
79
80 for (i = 0; i < NUM_FACTORS; ++i)
81 {
82 mpz_set_str (f, factors[i], 10);
83 if (mpz_divisible_p (x, f))
84 {
85 mpz_mul_2exp (f, f, 1);
86 /* d is an odd multiple of the factor f, exactly filling a limb. */
87 mpz_sub (d, x, f);
88 /* f = 2^GMP_NUMB_BITS mod d. */
89 mpz_sub_ui (f, f, 1);
90 break;
91 }
92 }
93
94 mpz_gcd (g, f, d);
95 if (mpz_even_p (d) || mpz_cmp (d, f) <= 0 || mpz_cmp_ui (g, 1) != 0)
96 {
97 printf ("No usable factor found.\n");
98 abort ();
99 }
100
101 rands = RANDS;
102 mpz_mul_ui (x, d, gmp_urandomm_ui (rands, 30000) + 1);
103
104 mpz_init (b);
105 mpz_setbit (b, GMP_NUMB_BITS - 1);
106 for (j = 0; j < 4; ++j)
107 {
108 mpz_add (x, x, b);
109
110 for (i = 1; i >= -1; --i)
111 {
112 if (mpz_fits_ulong_p (d)
113 && ((got = mpz_gcd_ui (NULL, x, mpz_get_ui (d)))
114 != (i != 0 ? 1 : mpz_get_ui (d))))
115 {
116 printf ("mpz_gcd_ui (f, kV+%i*2^%i, V): error (j = %i)\n", i, GMP_NUMB_BITS - 1, j);
117 printf (" return %#lx\n", got);
118 printf (" should be %#lx\n", (i != 0 ? 1 : mpz_get_ui (d)));
119 abort ();
120 }
121
122 mpz_gcd (g, x, d);
123 if ((mpz_cmp_ui (g, 1) == 0) != (i != 0))
124 {
125 printf ("mpz_gcd (f, kV+%i*2^%i, V): error (j = %i)\n", i, GMP_NUMB_BITS - 1, j);
126 printf (" should%s be one.\n",(i != 0 ? "" : " not"));
127 abort ();
128 }
129
130 mpz_sub (x, x, b);
131 }
132 /* Back to the original x. */
133 mpz_addmul_ui (x, b, 2);
134 mpz_mul (b, b, f);
135 mpz_mod (b, b, d);
136 }
137
138 mpz_clear (g);
139 mpz_clear (x);
140 mpz_clear (f);
141 mpz_clear (d);
142 mpz_clear (b);
143 }
144
145
146 int
147 main (void)
148 {
149 tests_start ();
150
151 check_ui_range ();
152 check_ui_factors ();
153
154 tests_end ();
155 exit (0);
156 }