1 /* Test mpz_fib_ui and mpz_fib2_ui.
2
3 Copyright 2000-2002 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-impl.h"
23 #include "tests.h"
24
25
26 /* Usage: t-fib_ui [x|num]
27
28 Run with no arguments, tests goes up to the initial value of "limit"
29 below. With a number argument tests are carried up that far, or with a
30 literal "x" tests are continued without limit (this being only meant for
31 development purposes).
32
33 The size tests performed are designed to partially replicate what will be
34 going on in mpz_fib_ui. There's plenty of ASSERTs there, but of course
35 they're not normally enabled.
36
37 Misfeatures:
38
39 The tests on MPN_FIB2_SIZE are a bit useless, since that macro includes a
40 +2 for the internal purposes of mpn_fib2_ui. It's probably better to
41 give mpn_fib2_ui a run with assertion checking enabled. */
42
43
44 #define MPZ_FIB_SIZE_FLOAT(n) \
45 ((mp_size_t) ((n) * 0.6942419 / GMP_NUMB_BITS + 1))
46
47
48 void
49 check_fib_table (void)
50 {
51 int i;
52 mp_limb_t want;
53
54 ASSERT_ALWAYS (FIB_TABLE(-1) == 1);
55 ASSERT_ALWAYS (FIB_TABLE(0) == 0);
56
57 for (i = 1; i <= FIB_TABLE_LIMIT; i++)
58 {
59 want = FIB_TABLE(i-1) + FIB_TABLE(i-2);
60 if (FIB_TABLE(i) != want)
61 {
62 printf ("FIB_TABLE(%d) wrong\n", i);
63 gmp_printf (" got %#Nx\n", &FIB_TABLE(i), 1);
64 gmp_printf (" want %#Nx\n", &want, 1);
65 abort ();
66 }
67 }
68 }
69
70
71 int
72 main (int argc, char *argv[])
73 {
74 unsigned long n;
75 unsigned long limit = 100 * GMP_LIMB_BITS;
76 mpz_t want_fn, want_fn1, got_fn, got_fn1;
77
78 tests_start ();
79 mp_trace_base = -16;
80 if (argc > 1 && argv[1][0] == 'x')
81 limit = ULONG_MAX;
82 else
83 TESTS_REPS (limit, argv, argc);
84
85 check_fib_table ();
86
87 /* start at n==0 */
88 mpz_init_set_ui (want_fn1, 1); /* F[-1] */
89 mpz_init_set_ui (want_fn, 0); /* F[0] */
90 mpz_init (got_fn);
91 mpz_init (got_fn1);
92
93 for (n = 0; n < limit; n++)
94 {
95 /* check our float formula seems right */
96 if (MPZ_FIB_SIZE_FLOAT (n) < SIZ(want_fn))
97 {
98 printf ("MPZ_FIB_SIZE_FLOAT wrong at n=%lu\n", n);
99 printf (" MPZ_FIB_SIZE_FLOAT %ld\n", MPZ_FIB_SIZE_FLOAT (n));
100 printf (" SIZ(want_fn) %d\n", SIZ(want_fn));
101 abort ();
102 }
103
104 /* check MPN_FIB2_SIZE seems right, compared to actual size and
105 compared to our float formula */
106 if (MPN_FIB2_SIZE (n) < MPZ_FIB_SIZE_FLOAT (n))
107 {
108 printf ("MPN_FIB2_SIZE wrong at n=%lu\n", n);
109 printf (" MPN_FIB2_SIZE %ld\n", MPN_FIB2_SIZE (n));
110 printf (" MPZ_FIB_SIZE_FLOAT %ld\n", MPZ_FIB_SIZE_FLOAT (n));
111 abort ();
112 }
113 if (MPN_FIB2_SIZE (n) < SIZ(want_fn))
114 {
115 printf ("MPN_FIB2_SIZE wrong at n=%lu\n", n);
116 printf (" MPN_FIB2_SIZE %ld\n", MPN_FIB2_SIZE (n));
117 printf (" SIZ(want_fn) %d\n", SIZ(want_fn));
118 abort ();
119 }
120
121 mpz_fib2_ui (got_fn, got_fn1, n);
122 MPZ_CHECK_FORMAT (got_fn);
123 MPZ_CHECK_FORMAT (got_fn1);
124 if (mpz_cmp (got_fn, want_fn) != 0 || mpz_cmp (got_fn1, want_fn1) != 0)
125 {
126 printf ("mpz_fib2_ui(%lu) wrong\n", n);
127 mpz_trace ("want fn ", want_fn);
128 mpz_trace ("got fn ", got_fn);
129 mpz_trace ("want fn1", want_fn1);
130 mpz_trace ("got fn1", got_fn1);
131 abort ();
132 }
133
134 mpz_fib_ui (got_fn, n);
135 MPZ_CHECK_FORMAT (got_fn);
136 if (mpz_cmp (got_fn, want_fn) != 0)
137 {
138 printf ("mpz_fib_ui(%lu) wrong\n", n);
139 mpz_trace ("want fn", want_fn);
140 mpz_trace ("got fn", got_fn);
141 abort ();
142 }
143
144 mpz_add (want_fn1, want_fn1, want_fn); /* F[n+1] = F[n] + F[n-1] */
145 mpz_swap (want_fn1, want_fn);
146 }
147
148 mpz_clear (want_fn);
149 mpz_clear (want_fn1);
150 mpz_clear (got_fn);
151 mpz_clear (got_fn1);
152
153 tests_end ();
154 exit (0);
155 }