← Back to branch summary

~ubuntu-branches/ubuntu/intrepid/ecl/intrepid

« back to all changes in this revision

Viewing changes to src/gmp/gen-fib.c

  • Committer: Bazaar Package Importer
  • Author(s): Peter Van Eynde
  • Date: 2007-04-09 11:51:51 UTC
  • mfrom: (1.1.3 upstream)
  • Revision ID: james.westby@ubuntu.com-20070409115151-ql8cr0kalzx1jmla
Tags: 0.9i-20070324-2
Upload to unstable. 

Show diffs side-by-side

added added

removed removed

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