← Back to branch summary

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

« back to all changes in this revision

Viewing changes to src/gmp/mpz/perfpow.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/mpz/perfpow.c
1
1
/* mpz_perfect_power_p(arg) -- Return non-zero if ARG is a perfect power,
2
2
   zero otherwise.
3
3
 
4
 
Copyright 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
 
4
Copyright 1998, 1999, 2000, 2001, 2005 Free Software Foundation, Inc.
5
5
 
6
6
This file is part of the GNU MP Library.
7
7
 
17
17
 
18
18
You should have received a copy of the GNU Lesser General Public License
19
19
along with the GNU MP Library; see the file COPYING.LIB.  If not, write to
20
 
the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
21
 
MA 02111-1307, USA. */
 
20
the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
 
21
MA 02110-1301, USA. */
22
22
 
23
23
/*
24
24
  We are to determine if c is a perfect power, c = a ^ b.
72
72
  int exact;
73
73
  mp_size_t uns;
74
74
  mp_size_t usize = SIZ (u);
75
 
  TMP_DECL (marker);
 
75
  TMP_DECL;
76
76
 
77
77
  if (usize == 0)
78
78
    return 1;                   /* consider 0 a perfect power */
84
84
  if (n2 != 0 && (n2 & 1) == 0 && usize < 0)
85
85
    return 0;                   /* 2 has even multiplicity with negative U */
86
86
 
87
 
  TMP_MARK (marker);
 
87
  TMP_MARK;
88
88
 
89
89
  uns = ABS (usize) - n2 / BITS_PER_MP_LIMB;
90
90
  MPZ_TMP_INIT (q, uns);
98
98
  for (i = 1; primes[i] != 0; i++)
99
99
    {
100
100
      prime = primes[i];
101
 
      rem = mpz_tdiv_ui (u2, prime);
102
 
      if (rem == 0)             /* divisable by this prime? */
 
101
 
 
102
      if (mpz_divisible_ui_p (u2, prime))       /* divisible by this prime? */
103
103
        {
104
104
          rem = mpz_tdiv_q_ui (q, u2, prime * prime);
105
105
          if (rem != 0)
106
106
            {
107
 
              TMP_FREE (marker);
 
107
              TMP_FREE;
108
108
              return 0;         /* prime divides exactly once, reject */
109
109
            }
110
110
          mpz_swap (q, u2);
119
119
 
120
120
          if ((n & 1) == 0 && usize < 0)
121
121
            {
122
 
              TMP_FREE (marker);
 
122
              TMP_FREE;
123
123
              return 0;         /* even multiplicity with negative U, reject */
124
124
            }
125
125
 
126
126
          n2 = gcd (n2, n);
127
127
          if (n2 == 1)
128
128
            {
129
 
              TMP_FREE (marker);
 
129
              TMP_FREE;
130
130
              return 0;         /* we have multiplicity 1 of some factor */
131
131
            }
132
132
 
133
133
          if (mpz_cmpabs_ui (u2, 1) == 0)
134
134
            {
135
 
              TMP_FREE (marker);
 
135
              TMP_FREE;
136
136
              return 1;         /* factoring completed; consistent power */
137
137
            }
138
138
 
158
158
            exact = mpz_root (q, u2, nth);
159
159
          if (exact)
160
160
            {
161
 
              TMP_FREE (marker);
 
161
              TMP_FREE;
162
162
              return 1;
163
163
            }
164
164
          if (mpz_cmp_ui (q, SMALLEST_OMITTED_PRIME) < 0)
165
165
            {
166
 
              TMP_FREE (marker);
 
166
              TMP_FREE;
167
167
              return 0;
168
168
            }
169
169
        }
186
186
            exact = mpz_root (q, u2, nth);
187
187
          if (exact)
188
188
            {
189
 
              TMP_FREE (marker);
 
189
              TMP_FREE;
190
190
              return 1;
191
191
            }
192
192
          if (mpz_cmp_ui (q, SMALLEST_OMITTED_PRIME) < 0)
193
193
            {
194
 
              TMP_FREE (marker);
 
194
              TMP_FREE;
195
195
              return 0;
196
196
            }
197
197
        }
198
198
 
199
 
      TMP_FREE (marker);
 
199
      TMP_FREE;
200
200
      return 0;
201
201
    }
202
202
 
203
203
n2prime:
204
204
  exact = mpz_root (NULL, u2, n2);
205
 
  TMP_FREE (marker);
 
205
  TMP_FREE;
206
206
  return exact;
207
207
}
208
208