1:  package de.luschny.math.factorial;

   2:   

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

   4:   

   5:  public class FactorialBoitenSplit implements IFactorialFunction

   6:  {

   7:   

   8:      public FactorialBoitenSplit()

   9:      {

  10:      }

  11:   

  12:      public String getName()

  13:      {

  14:          return "BoitenSplit       ";

  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:          if (n < 2)

  25:          {

  26:              return Xint.ONE;

  27:          }

  28:   

  29:          Xint p = Xint.ONE;

  30:          Xint r = Xint.ONE;

  31:   

  32:          // log2n = floor(log2(n));

  33:          int log2n = 31 - Integer.numberOfLeadingZeros(n);

  34:          int h = 0, shift = 0, k = 1;

  35:   

  36:          while (h != n)

  37:          {

  38:              shift += h;

  39:              h = n >>> log2n--;

  40:              int high = (h & 1) == 1 ? h : h - 1;

  41:   

  42:              while (k != high)

  43:              {

  44:                  k += 2;

  45:                  p = p.multiply(k);

  46:              }

  47:              r = r.multiply(p);

  48:          }

  49:          return r.shiftLeft(shift);

  50:      }

  51:  } // endOfFactorialSplitBoiten