cannam@127: /*
cannam@127:  * Copyright (c) 2003, 2007-14 Matteo Frigo
cannam@127:  * Copyright (c) 2003, 2007-14 Massachusetts Institute of Technology
cannam@127:  *
cannam@127:  * This program is free software; you can redistribute it and/or modify
cannam@127:  * it under the terms of the GNU General Public License as published by
cannam@127:  * the Free Software Foundation; either version 2 of the License, or
cannam@127:  * (at your option) any later version.
cannam@127:  *
cannam@127:  * This program is distributed in the hope that it will be useful,
cannam@127:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
cannam@127:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
cannam@127:  * GNU General Public License for more details.
cannam@127:  *
cannam@127:  * You should have received a copy of the GNU General Public License
cannam@127:  * along with this program; if not, write to the Free Software
cannam@127:  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
cannam@127:  *
cannam@127:  */
cannam@127: 
cannam@127: 
cannam@127: #include "ifftw.h"
cannam@127: 
cannam@127: /***************************************************************************/
cannam@127: 
cannam@127: /* Rader's algorithm requires lots of modular arithmetic, and if we
cannam@127:    aren't careful we can have errors due to integer overflows. */
cannam@127: 
cannam@127: /* Compute (x * y) mod p, but watch out for integer overflows; we must
cannam@127:    have 0 <= {x, y} < p.
cannam@127: 
cannam@127:    If overflow is common, this routine is somewhat slower than
cannam@127:    e.g. using 'long long' arithmetic.  However, it has the advantage
cannam@127:    of working when INT is 64 bits, and is also faster when overflow is
cannam@127:    rare.  FFTW calls this via the MULMOD macro, which further
cannam@127:    optimizes for the case of small integers. 
cannam@127: */
cannam@127: 
cannam@127: #define ADD_MOD(x, y, p) ((x) >= (p) - (y)) ? ((x) + ((y) - (p))) : ((x) + (y))
cannam@127: 
cannam@127: INT X(safe_mulmod)(INT x, INT y, INT p)
cannam@127: {
cannam@127:      INT r;
cannam@127: 
cannam@127:      if (y > x) 
cannam@127: 	  return X(safe_mulmod)(y, x, p);
cannam@127: 
cannam@127:      A(0 <= y && x < p);
cannam@127: 
cannam@127:      r = 0;
cannam@127:      while (y) {
cannam@127: 	  r = ADD_MOD(r, x*(y&1), p); y >>= 1;
cannam@127: 	  x = ADD_MOD(x, x, p);
cannam@127:      }
cannam@127: 
cannam@127:      return r;
cannam@127: }
cannam@127: 
cannam@127: /***************************************************************************/
cannam@127: 
cannam@127: /* Compute n^m mod p, where m >= 0 and p > 0.  If we really cared, we
cannam@127:    could make this tail-recursive. */
cannam@127: 
cannam@127: INT X(power_mod)(INT n, INT m, INT p)
cannam@127: {
cannam@127:      A(p > 0);
cannam@127:      if (m == 0)
cannam@127: 	  return 1;
cannam@127:      else if (m % 2 == 0) {
cannam@127: 	  INT x = X(power_mod)(n, m / 2, p);
cannam@127: 	  return MULMOD(x, x, p);
cannam@127:      }
cannam@127:      else
cannam@127: 	  return MULMOD(n, X(power_mod)(n, m - 1, p), p);
cannam@127: }
cannam@127: 
cannam@127: /* the following two routines were contributed by Greg Dionne. */
cannam@127: static INT get_prime_factors(INT n, INT *primef)
cannam@127: {
cannam@127:      INT i;
cannam@127:      INT size = 0;
cannam@127: 
cannam@127:      A(n % 2 == 0); /* this routine is designed only for even n */
cannam@127:      primef[size++] = (INT)2;
cannam@127:      do {
cannam@127: 	  n >>= 1;
cannam@127:      } while ((n & 1) == 0);
cannam@127: 
cannam@127:      if (n == 1)
cannam@127: 	  return size;
cannam@127: 
cannam@127:      for (i = 3; i * i <= n; i += 2)
cannam@127: 	  if (!(n % i)) {
cannam@127: 	       primef[size++] = i;
cannam@127: 	       do {
cannam@127: 		    n /= i;
cannam@127: 	       } while (!(n % i));
cannam@127: 	  }
cannam@127:      if (n == 1)
cannam@127: 	  return size;
cannam@127:      primef[size++] = n;
cannam@127:      return size;
cannam@127: }
cannam@127: 
cannam@127: INT X(find_generator)(INT p)
cannam@127: {
cannam@127:     INT n, i, size;
cannam@127:     INT primef[16];     /* smallest number = 32589158477190044730 > 2^64 */
cannam@127:     INT pm1 = p - 1;
cannam@127: 
cannam@127:     if (p == 2)
cannam@127: 	 return 1;
cannam@127: 
cannam@127:     size = get_prime_factors(pm1, primef);
cannam@127:     n = 2;
cannam@127:     for (i = 0; i < size; i++)
cannam@127:         if (X(power_mod)(n, pm1 / primef[i], p) == 1) {
cannam@127:             i = -1;
cannam@127:             n++;
cannam@127:         }
cannam@127:     return n;
cannam@127: }
cannam@127: 
cannam@127: /* Return first prime divisor of n  (It would be at best slightly faster to
cannam@127:    search a static table of primes; there are 6542 primes < 2^16.)  */
cannam@127: INT X(first_divisor)(INT n)
cannam@127: {
cannam@127:      INT i;
cannam@127:      if (n <= 1)
cannam@127: 	  return n;
cannam@127:      if (n % 2 == 0)
cannam@127: 	  return 2;
cannam@127:      for (i = 3; i*i <= n; i += 2)
cannam@127: 	  if (n % i == 0)
cannam@127: 	       return i;
cannam@127:      return n;
cannam@127: }
cannam@127: 
cannam@127: int X(is_prime)(INT n)
cannam@127: {
cannam@127:      return(n > 1 && X(first_divisor)(n) == n);
cannam@127: }
cannam@127: 
cannam@127: INT X(next_prime)(INT n)
cannam@127: {
cannam@127:      while (!X(is_prime)(n)) ++n;
cannam@127:      return n;
cannam@127: }
cannam@127: 
cannam@127: int X(factors_into)(INT n, const INT *primes)
cannam@127: {
cannam@127:      for (; *primes != 0; ++primes) 
cannam@127: 	  while ((n % *primes) == 0) 
cannam@127: 	       n /= *primes;
cannam@127:      return (n == 1);
cannam@127: }
cannam@127: 
cannam@127: /* integer square root.  Return floor(sqrt(N)) */
cannam@127: INT X(isqrt)(INT n)
cannam@127: {
cannam@127:      INT guess, iguess;
cannam@127: 
cannam@127:      A(n >= 0);
cannam@127:      if (n == 0) return 0;
cannam@127: 
cannam@127:      guess = n; iguess = 1;
cannam@127: 
cannam@127:      do {
cannam@127:           guess = (guess + iguess) / 2;
cannam@127: 	  iguess = n / guess;
cannam@127:      } while (guess > iguess);
cannam@127: 
cannam@127:      return guess;
cannam@127: }
cannam@127: 
cannam@127: static INT isqrt_maybe(INT n)
cannam@127: {
cannam@127:      INT guess = X(isqrt)(n);
cannam@127:      return guess * guess == n ? guess : 0;
cannam@127: }
cannam@127: 
cannam@127: #define divides(a, b) (((b) % (a)) == 0)
cannam@127: INT X(choose_radix)(INT r, INT n)
cannam@127: {
cannam@127:      if (r > 0) {
cannam@127: 	  if (divides(r, n)) return r;
cannam@127: 	  return 0;
cannam@127:      } else if (r == 0) {
cannam@127: 	  return X(first_divisor)(n);
cannam@127:      } else {
cannam@127: 	  /* r is negative.  If n = (-r) * q^2, take q as the radix */
cannam@127: 	  r = 0 - r;
cannam@127: 	  return (n > r && divides(r, n)) ? isqrt_maybe(n / r) : 0;
cannam@127:      }
cannam@127: }
cannam@127: 
cannam@127: /* return A mod N, works for all A including A < 0 */
cannam@127: INT X(modulo)(INT a, INT n)
cannam@127: {
cannam@127:      A(n > 0);
cannam@127:      if (a >= 0)
cannam@127: 	  return a % n;
cannam@127:      else
cannam@127: 	  return (n - 1) - ((-(a + (INT)1)) % n);
cannam@127: }
cannam@127: 
cannam@127: /* TRUE if N factors into small primes */
cannam@127: int X(factors_into_small_primes)(INT n)
cannam@127: {
cannam@127:      static const INT primes[] = { 2, 3, 5, 0 };
cannam@127:      return X(factors_into)(n, primes);
cannam@127: }