/* fft/factorize.c

 * 

 * Copyright (C) 1996, 1997, 1998, 1999, 2000, 2007 Brian Gough

 * 

 * This program is free software; you can redistribute it and/or modify

 * it under the terms of the GNU General Public License as published by

 * the Free Software Foundation; either version 3 of the License, or (at

 * your option) any later version.

 * 

 * This program is distributed in the hope that it will be useful, but

 * WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

 * General Public License for more details.

 * 

 * You should have received a copy of the GNU General Public License

 * along with this program; if not, write to the Free Software

 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.

 */

#include <config.h>

#include <gsl/gsl_errno.h>

#include <gsl/gsl_fft_complex.h>

#include "factorize.h"

static int

fft_complex_factorize (const size_t n,

                           size_t *nf,

                           size_t factors[])

{

  const size_t complex_subtransforms[] =

  {7, 6, 5, 4, 3, 2, 0};

  /* other factors can be added here if their transform modules are

     implemented. The end of the list is marked by 0. */

  int status = fft_factorize (n, complex_subtransforms, nf, factors);

  return status;

}

static int

fft_halfcomplex_factorize (const size_t n,

                               size_t *nf,

                               size_t factors[])

{

  const size_t halfcomplex_subtransforms[] =

  {5, 4, 3, 2, 0};

  int status = fft_factorize (n, halfcomplex_subtransforms, nf, factors);

  return status;

}

static int

fft_real_factorize (const size_t n,

                        size_t *nf,

                        size_t factors[])

{

  const size_t real_subtransforms[] =

  {5, 4, 3, 2, 0};

  int status = fft_factorize (n, real_subtransforms, nf, factors);

  return status;

}

static int

fft_factorize (const size_t n,

                   const size_t implemented_subtransforms[],

                   size_t *n_factors,

                   size_t factors[])

{

  size_t nf = 0;

  size_t ntest = n;

  size_t factor;

  size_t i = 0;

  if (n == 0)

    {

      GSL_ERROR ("length n must be positive integer", GSL_EDOM);

    }

  if (n == 1)

    {

      factors[0] = 1;

      *n_factors = 1;

      return 0;

    }

  /* deal with the implemented factors first */

  while (implemented_subtransforms[i] && ntest != 1)

    {

      factor = implemented_subtransforms[i];

      while ((ntest % factor) == 0)

        {

          ntest = ntest / factor;

          factors[nf] = factor;

          nf++;

        }

      i++;

    }

  /* deal with any other even prime factors (there is only one) */

  factor = 2;

  while ((ntest % factor) == 0 && (ntest != 1))

    {

      ntest = ntest / factor;

      factors[nf] = factor;

      nf++;

    }

  /* deal with any other odd prime factors */

  factor = 3;

  while (ntest != 1)

    {

      while ((ntest % factor) != 0)

        {

          factor += 2;

        }

      ntest = ntest / factor;

      factors[nf] = factor;

      nf++;

    }

  /* check that the factorization is correct */

  {

    size_t product = 1;

    for (i = 0; i < nf; i++)

      {

        product *= factors[i];

      }

    if (product != n)

      {

        GSL_ERROR ("factorization failed", GSL_ESANITY);

      }

  }

  *n_factors = nf;

  return 0;

}

static int 

fft_binary_logn (const size_t n)

{

  size_t ntest ;

  size_t binary_logn = 0 ;

  size_t k = 1;

  while (k < n)

    {

      k *= 2;

      binary_logn++;

    }

  ntest = (1 << binary_logn) ;

  if (n != ntest )       

    {

      return -1 ; /* n is not a power of 2 */

    } 

  return binary_logn;

}