1:  package de.luschny.math.factorial;
   2:   
   3:  import de.luschny.math.Xmath;
   4:  import de.luschny.math.arithmetic.Xint;
   5:  import de.luschny.math.primes.IPrimeIteration;
   6:  import de.luschny.math.primes.PrimeSieve;
   7:   
   8:  import java.util.ArrayList;
   9:  import java.util.List;
  10:  import java.util.concurrent.*;
  11:   
  12:  public class FactorialParallelPrimeSplit implements IFactorialFunction
  13:  {
  14:   
  15:      public FactorialParallelPrimeSplit()
  16:      {
  17:      }
  18:   
  19:      public String getName()
  20:      {
  21:          return "ParallelPrimeSplit";
  22:      }
  23:   
  24:      public Xint factorial(int n)
  25:      {
  26:          // For very small n the 'NaiveFactorial' is OK.
  27:          if (n < 20)    { return Xmath.Factorial(n); }
  28:   
  29:          PrimeSieve sieve = new PrimeSieve(n);
  30:   
  31:          int proc = Runtime.getRuntime().availableProcessors();
  32:          int log2n = 31 - Integer.numberOfLeadingZeros(n);
  33:   
  34:          ExecutorService exe = Executors.newFixedThreadPool(proc);
  35:          ArrayList<Callable<Xint>> swingTasks = new ArrayList<Callable<Xint>>(log2n);
  36:   
  37:          Xint r = Xint.ONE, p = Xint.ONE;
  38:          Xint rl = Xint.ONE, t;
  39:   
  40:          int h = 0, shift = 0;
  41:   
  42:          while (h != n)
  43:          {
  44:              shift += h;
  45:              h = n >> log2n--;
  46:              if (h > 2)
  47:              {
  48:                  swingTasks.add(new Swing(sieve, h));
  49:              }
  50:          }
  51:   
  52:          try
  53:          {
  54:              List<Future<Xint>> swings = exe.invokeAll(swingTasks);
  55:              int taskCounter = swings.size();
  56:   
  57:              for (int i = 0; i < taskCounter; i++)
  58:              {
  59:                  t = rl.multiply(swings.get(i).get());
  60:                  p = p.multiply(t);
  61:                  rl = r;
  62:                  r = r.multiply(p);
  63:              }
  64:          }
  65:          catch (Throwable e)
  66:          {
  67:              e.printStackTrace();
  68:          }
  69:   
  70:          exe.shutdownNow();
  71:          return r.shiftLeft(shift);
  72:      }
  73:   
  74:      private static int[] smallOddSwing =
  75:          { 1, 1, 1, 3, 3, 15, 5, 35, 35, 315, 63, 693, 231, 3003, 429, 
  76:            6435, 6435, 109395, 12155, 230945, 46189, 969969, 88179, 2028117,
  77:            676039, 16900975, 1300075, 35102025, 5014575, 145422675, 9694845, 
  78:            300540195, 300540195 };
  79:   
  80:      // -- Concurrent execution of this Class should not fail.
  81:      final class Swing implements Callable<Xint>
  82:      {
  83:   
  84:          private final PrimeSieve Sieve;
  85:          private final int N;
  86:   
  87:          public Swing(PrimeSieve sieve, int n)
  88:          {
  89:              Sieve = sieve;
  90:              N = n;
  91:          }
  92:   
  93:          // -- Returns swing(n)
  94:          public Xint call() throws Exception
  95:          {
  96:              if (N < 33)
  97:              {
  98:                  return Xint.valueOf(smallOddSwing[N]);
  99:              }
 100:   
 101:              FutureTask<Xint> Primorial = new FutureTask<Xint>(new Callable<Xint>()
 102:              {
 103:                  public Xint call()
 104:                  {
 105:                      return Sieve.getPrimorial(N / 2 + 1, N);
 106:                  }
 107:              });
 108:   
 109:              new Thread(Primorial).start();
 110:              Xint primeProduct = lowSwing();
 111:              return primeProduct.multiply(Primorial.get());
 112:          }
 113:   
 114:          private Xint lowSwing()
 115:          {
 116:              int sqrtN = (int) Math.floor(Math.sqrt(N));
 117:              IPrimeIteration pIter0 = Sieve.getIteration(3, sqrtN);
 118:              IPrimeIteration pIter1 = Sieve.getIteration(sqrtN + 1, N / 3);
 119:   
 120:              int piN = pIter0.getNumberOfPrimes() + pIter1.getNumberOfPrimes();
 121:              final int[] primeList = new int[piN];
 122:              int count = 0;
 123:   
 124:              for (int prime : pIter0)
 125:              {
 126:                  int q = N, p = 1;
 127:   
 128:                  while ((q /= prime) > 0)
 129:                  {
 130:                      if ((q & 1) == 1)
 131:                      {
 132:                          p *= prime;
 133:                      }
 134:                  }
 135:   
 136:                  if (p > 1)
 137:                  {
 138:                      primeList[count++] = p;
 139:                  }
 140:              }
 141:   
 142:              for (int prime : pIter1)
 143:              {
 144:                  if (((N / prime) & 1) == 1)
 145:                  {
 146:                      primeList[count++] = prime;
 147:                  }
 148:              }
 149:   
 150:              return Xint.product(primeList, 0, count);
 151:   
 152:          } // endOfLowSwing
 153:      } // endOfSwing
 154:  } // endOfFactorial