1:  package de.luschny.math.factorial;
   2:   
   3:  import de.luschny.math.arithmetic.Xint;
   4:   
   5:  public class FactorialSwingDouble implements IFactorialFunction
   6:  {
   7:   
   8:      public FactorialSwingDouble()
   9:      {
  10:      }
  11:   
  12:      public String getName()
  13:      {
  14:          return "SwingDouble       ";
  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:          return recFactorial(n / 2).square().multiply(swing(n));
  34:      }
  35:   
  36:      private Xint swing(int n)
  37:      {
  38:          boolean oddN = (n & 1) == 1;
  39:          boolean div = false;
  40:          long h = n / 2;
  41:   
  42:          switch ((n / 2) % 4)
  43:              {
  44:              case 0:
  45:                  h = oddN ? h + 1 : 1;
  46:                  break;
  47:              case 1:
  48:                  h = oddN ? 2 * (h + 2) : 2;
  49:                  break;
  50:              case 2:
  51:                  h = oddN ? 2 * (h + 1) * (h + 3) : 2 * (h + 1);
  52:                  div = n > 7;
  53:                  break;
  54:              case 3:
  55:                  h = oddN ? 4 * (h + 2) * (h + 4) : 4 * (h + 2);
  56:                  div = n > 7;
  57:                  break;
  58:              }
  59:   
  60:          Xint b = Xint.valueOf(h);
  61:   
  62:          long D = 1, N = oddN ? 2 * n : 2 * (n - 1);
  63:   
  64:          for (int i = n / 8; i > 0; --i)
  65:          {
  66:              long num = N * (N - 4), g = num;
  67:              long den = D * (D + 1), f = den;
  68:   
  69:              N -= 8;
  70:              D += 2;
  71:   
  72:              while (f != 0)
  73:              {
  74:                  long t = g % f;
  75:                  g = f;
  76:                  f = t;
  77:              }
  78:   
  79:              b = b.multiply(num / g).divide(den / g);
  80:          }
  81:   
  82:          if (div)
  83:          {
  84:              b = b.divide(n / 4);
  85:          }
  86:   
  87:          return b;
  88:      }
  89:  } // endOfSwingDouble