tests/mpz/t-fib_ui.c

   1 /* Test mpz_fib_ui and mpz_fib2_ui.
   2
   3 Copyright 2000, 2001, 2002 Free Software Foundation, Inc.
   4
   5 This file is part of the GNU MP Library.
   6
   7 The GNU MP Library is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU Lesser General Public License as published by
   9 the Free Software Foundation; either version 3 of the License, or (at your
  10 option) any later version.
  11
  12 The GNU MP Library is distributed in the hope that it will be useful, but
  13 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  14 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  15 License for more details.
  16
  17 You should have received a copy of the GNU Lesser General Public License
  18 along with the GNU MP Library.  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
  27 /* Usage: t-fib_ui [x|num]
  28
  29    Run with no arguments, tests goes up to the initial value of "limit"
  30    below.  With a number argument tests are carried up that far, or with a
  31    literal "x" tests are continued without limit (this being only meant for
  32    development purposes).
  33
  34    The size tests performed are designed to partially replicate what will be
  35    going on in mpz_fib_ui.  There's plenty of ASSERTs there, but of course
  36    they're not normally enabled.
  37
  38    Misfeatures:
  39
  40    The tests on MPN_FIB2_SIZE are a bit useless, since that macro includes a
  41    +2 for the internal purposes of mpn_fib2_ui.  It's probably better to
  42    give mpn_fib2_ui a run with assertion checking enabled.  */
  43
  44
  45 #define MPZ_FIB_SIZE_FLOAT(n) \
  46   ((mp_size_t) ((n) * 0.6942419 / GMP_NUMB_BITS + 1))
  47
  48
  49 void
  50 check_fib_table (void)
  51 {
  52   int        i;
  53   mp_limb_t  want;
  54
  55   ASSERT_ALWAYS (FIB_TABLE(-1) == 1);
  56   ASSERT_ALWAYS (FIB_TABLE(0) == 0);
  57
  58   for (i = 1; i <= FIB_TABLE_LIMIT; i++)
  59     {
  60       want = FIB_TABLE(i-1) + FIB_TABLE(i-2);
  61       if (FIB_TABLE(i) != want)
  62         {
  63           printf ("FIB_TABLE(%d) wrong\n", i);
  64           gmp_printf ("  got  %#Nx\n", &FIB_TABLE(i), 1);
  65           gmp_printf ("  want %#Nx\n", &want, 1);
  66           abort ();
  67         }
  68     }
  69 }
  70
  71
  72 int
  73 main (int argc, char *argv[])
  74 {
  75   unsigned long  n;
  76   unsigned long  limit = 100 * GMP_LIMB_BITS;
  77   mpz_t          want_fn, want_fn1, got_fn, got_fn1;
  78
  79   tests_start ();
  80   mp_trace_base = -16;
  81   if (argc > 1 && argv[1][0] == 'x')
  82     limit = ULONG_MAX;
  83   else if (argc > 1)
  84     limit = atoi (argv[1]);
  85
  86   check_fib_table ();
  87
  88   /* start at n==0 */
  89   mpz_init_set_ui (want_fn1, 1);  /* F[-1] */
  90   mpz_init_set_ui (want_fn,  0);  /* F[0]   */
  91   mpz_init (got_fn);
  92   mpz_init (got_fn1);
  93
  94   for (n = 0; n < limit; n++)
  95     {
  96       /* check our float formula seems right */
  97       if (MPZ_FIB_SIZE_FLOAT (n) < SIZ(want_fn))
  98         {
  99           printf ("MPZ_FIB_SIZE_FLOAT wrong at n=%lu\n", n);
 100           printf ("  MPZ_FIB_SIZE_FLOAT  %ld\n", MPZ_FIB_SIZE_FLOAT (n));
 101           printf ("  SIZ(want_fn)        %d\n", SIZ(want_fn));
 102           abort ();
 103         }
 104
 105       /* check MPN_FIB2_SIZE seems right, compared to actual size and
 106          compared to our float formula */
 107       if (MPN_FIB2_SIZE (n) < MPZ_FIB_SIZE_FLOAT (n))
 108         {
 109           printf ("MPN_FIB2_SIZE wrong at n=%lu\n", n);
 110           printf ("  MPN_FIB2_SIZE       %ld\n", MPN_FIB2_SIZE (n));
 111           printf ("  MPZ_FIB_SIZE_FLOAT  %ld\n", MPZ_FIB_SIZE_FLOAT (n));
 112           abort ();
 113         }
 114       if (MPN_FIB2_SIZE (n) < SIZ(want_fn))
 115         {
 116           printf ("MPN_FIB2_SIZE wrong at n=%lu\n", n);
 117           printf ("  MPN_FIB2_SIZE  %ld\n", MPN_FIB2_SIZE (n));
 118           printf ("  SIZ(want_fn)   %d\n", SIZ(want_fn));
 119           abort ();
 120         }
 121
 122       mpz_fib2_ui (got_fn, got_fn1, n);
 123       MPZ_CHECK_FORMAT (got_fn);
 124       MPZ_CHECK_FORMAT (got_fn1);
 125       if (mpz_cmp (got_fn, want_fn) != 0 || mpz_cmp (got_fn1, want_fn1) != 0)
 126         {
 127           printf ("mpz_fib2_ui(%lu) wrong\n", n);
 128           mpz_trace ("want fn ", want_fn);
 129           mpz_trace ("got  fn ",  got_fn);
 130           mpz_trace ("want fn1", want_fn1);
 131           mpz_trace ("got  fn1",  got_fn1);
 132           abort ();
 133         }
 134
 135       mpz_fib_ui (got_fn, n);
 136       MPZ_CHECK_FORMAT (got_fn);
 137       if (mpz_cmp (got_fn, want_fn) != 0)
 138         {
 139           printf ("mpz_fib_ui(%lu) wrong\n", n);
 140           mpz_trace ("want fn", want_fn);
 141           mpz_trace ("got  fn", got_fn);
 142           abort ();
 143         }
 144
 145       mpz_add (want_fn1, want_fn1, want_fn);  /* F[n+1] = F[n] + F[n-1] */
 146       mpz_swap (want_fn1, want_fn);
 147     }
 148
 149   mpz_clear (want_fn);
 150   mpz_clear (want_fn1);
 151   mpz_clear (got_fn);
 152   mpz_clear (got_fn1);
 153
 154   tests_end ();
 155   exit (0);
 156 }