contrib/gmp/gen-fib.c

   1 /* Generate Fibonacci table data.
   2
   3 Copyright 2001, 2002, 2004 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 "dumbmp.c"
  22
  23 mpz_t  *f;
  24 int    fnum, fib_limit, luc_limit;
  25
  26 void
  27 generate (int numb_bits)
  28 {
  29   mpz_t  limit, l;
  30   int    falloc, i;
  31
  32   mpz_init_set_ui (limit, 1L);
  33   mpz_mul_2exp (limit, limit, numb_bits);
  34
  35   /* fib(2n) > 2^n, so use 2n as a limit for the table size */
  36   falloc = 2 * numb_bits;
  37   f = (mpz_t *) xmalloc (falloc * sizeof (*f));
  38
  39   mpz_init_set_ui (f[0], 1L);  /* F[-1] */
  40   mpz_init_set_ui (f[1], 0L);  /* F[0] */
  41
  42   mpz_init (l);
  43
  44   for (i = 2; ; i++)
  45     {
  46       ASSERT (i < falloc);
  47
  48       /* F[i] = F[i-1] + F[i-2] */
  49       mpz_init (f[i]);
  50       mpz_add (f[i], f[i-1], f[i-2]);
  51       if (mpz_cmp (f[i], limit) >= 0)
  52         break;
  53
  54       fnum = i+1;
  55       fib_limit = i-1;
  56
  57       /* L[i] = F[i]+2*F[i-1] */
  58       mpz_add (l, f[i], f[i-1]);
  59       mpz_add (l, l, f[i-1]);
  60
  61       if (mpz_cmp (l, limit) < 0)
  62         luc_limit = i-1;
  63     }
  64
  65   mpz_clear (limit);
  66 }
  67
  68
  69 void
  70 header (int numb_bits)
  71 {
  72   printf ("/* This file generated by gen-fib.c - DO NOT EDIT. */\n");
  73   printf ("\n");
  74   printf ("#if GMP_NUMB_BITS != %d\n", numb_bits);
  75   printf ("Error, error, this data is for %d bits\n", numb_bits);
  76   printf ("#endif\n");
  77   printf ("\n");
  78   printf ("#define FIB_TABLE_LIMIT         %d\n", fib_limit);
  79   printf ("#define FIB_TABLE_LUCNUM_LIMIT  %d\n", luc_limit);
  80 }
  81
  82 void
  83 table (int numb_bits)
  84 {
  85   int  i;
  86
  87   printf ("/* This file generated by gen-fib.c - DO NOT EDIT. */\n");
  88   printf ("\n");
  89   printf ("#include \"gmp.h\"\n");
  90   printf ("#include \"gmp-impl.h\"\n");
  91   printf ("\n");
  92   printf ("#if GMP_NUMB_BITS != %d\n", numb_bits);
  93   printf ("Error, error, this data is for %d bits\n", numb_bits);
  94   printf ("#endif\n");
  95   printf ("\n");
  96   printf ("const mp_limb_t\n");
  97   printf ("__gmp_fib_table[FIB_TABLE_LIMIT+2] = {\n");
  98
  99   for (i = 0; i < fnum; i++)
 100     {
 101       printf ("  CNST_LIMB (0x");
 102       mpz_out_str (stdout, 16, f[i]);
 103       printf ("),  /* %d */\n", i-1);
 104     }
 105   printf ("};\n");
 106 }
 107
 108 int
 109 main (int argc, char *argv[])
 110 {
 111   int  limb_bits, nail_bits, numb_bits;
 112
 113   if (argc != 4)
 114     {
 115       fprintf (stderr, "Usage: gen-bases <header|table> <limbbits> <nailbits>\n");
 116       exit (1);
 117     }
 118
 119   limb_bits = atoi (argv[2]);
 120   nail_bits = atoi (argv[3]);
 121
 122   if (limb_bits <= 0
 123       || nail_bits < 0
 124       || nail_bits >= limb_bits)
 125     {
 126       fprintf (stderr, "Invalid limb/nail bits: %d %d\n",
 127                limb_bits, nail_bits);
 128       exit (1);
 129     }
 130   numb_bits = limb_bits - nail_bits;
 131
 132   generate (numb_bits);
 133
 134   if (strcmp (argv[1], "header") == 0)
 135     header (numb_bits);
 136   else if (strcmp (argv[1], "table") == 0)
 137     table (numb_bits);
 138   else
 139     {
 140       fprintf (stderr, "Invalid header/table choice: %s\n", argv[1]);
 141       exit (1);
 142     }
 143
 144   return 0;
 145 }