1:  package de.luschny.math.factorial;

   2:   

   3:  import de.luschny.math.arithmetic.Xint;

   4:   

   5:  public class FactorialAdditiveSwing implements IFactorialFunction

   6:  {

   7:   

   8:      public FactorialAdditiveSwing()

   9:      {

  10:      }

  11:   

  12:      public String getName()

  13:      {

  14:          return "AdditiveSwing       ";

  15:      }

  16:   

  17:      public Xint factorial(int n)

  18:      {

  19:          if (n < 0)

  20:          {

  21:              throw new ArithmeticException("Factorial: n has to be >= 0, but was " + n);

  22:          }

  23:   

  24:          return recFactorial(n);

  25:      }

  26:   

  27:      private Xint recFactorial(int n)

  28:      {

  29:          if (n < 2)

  30:          {

  31:              return Xint.ONE;

  32:          }

  33:   

  34:          return recFactorial(n / 2).square().multiply(swing(n));

  35:      }

  36:   

  37:      public Xint swing(int n)

  38:      {

  39:          Xint w = Xint.ONE;

  40:   

  41:          if (n > 1)

  42:          {

  43:              n = n + 2;

  44:              Xint[] s = new Xint[n + 1];

  45:   

  46:              s[0] = s[1] = Xint.ZERO;

  47:              s[2] = w;

  48:   

  49:              for (int m = 3; m <= n; m++)

  50:              {

  51:                  s[m] = s[m - 2];

  52:                  for (int k = m; k >= 2; k--)

  53:                  {

  54:                      s[k] = s[k].add(s[k - 2]);

  55:                      if ((k & 1) == 1) // if k is odd

  56:                      {

  57:                          s[k] = s[k].add(s[k - 1]);

  58:                      }

  59:                  }

  60:              }

  61:              w = s[n];

  62:          }

  63:          return w;

  64:      }

  65:  } // endOfFactorialAdditiveSwing