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 FactorialParallelPrimeSwing implements IFactorialFunction
  13:  {
  14:   
  15:      // Same algorithm as FactorialPrimeSwing
  16:      // but computing swing(n) concurrently
  17:   
  18:      public FactorialParallelPrimeSwing()
  19:      {
  20:      }
  21:   
  22:      public String getName()
  23:      {
  24:          return "ParallelPrimeSwing";
  25:      }
  26:   
  27:      private List<Future<Xint>> swings;
  28:      private int taskCounter;
  29:   
  30:      public Xint factorial(int n)
  31:      {
  32:          // For very small n the 'NaiveFactorial' is OK.
  33:          if (n < 20)    { return Xmath.Factorial(n); }
  34:   
  35:          int proc = Runtime.getRuntime().availableProcessors();
  36:          ExecutorService poolExe = Executors.newFixedThreadPool(proc);
  37:   
  38:          PrimeSieve sieve = new PrimeSieve(n);
  39:   
  40:          int log2n = 31 - Integer.numberOfLeadingZeros(n);
  41:          ArrayList<Callable<Xint>> swingTasks = new ArrayList<Callable<Xint>>(log2n);
  42:   
  43:          taskCounter = 0;
  44:          int N = n;
  45:   
  46:          // -- It is more efficient to add the big swings
  47:          // -- first and the small ones later!
  48:          while (N > 32)
  49:          {
  50:              swingTasks.add(new Swing(sieve, N));
  51:              N >>= 1;
  52:              taskCounter++;
  53:          }
  54:   
  55:          Xint fact = null;
  56:          try
  57:          {
  58:              swings = poolExe.invokeAll(swingTasks);
  59:              fact = recFactorial(n).shiftLeft(n - Integer.bitCount(n));
  60:          }
  61:          catch (Throwable e)
  62:          {
  63:              e.printStackTrace();
  64:          }
  65:   
  66:          poolExe.shutdownNow();
  67:          return fact;
  68:      }
  69:   
  70:      private Xint recFactorial(int n) throws Throwable
  71:      {
  72:          if (n < 2)
  73:          {
  74:              return Xint.ONE;
  75:          }
  76:   
  77:          Xint recFact = recFactorial(n / 2).square();
  78:          Xint swing;
  79:   
  80:          if (n <= 32)
  81:          {
  82:              swing = Xint.valueOf(smallOddSwing[n]);
  83:          }
  84:          else
  85:          {
  86:              swing = swings.get(--taskCounter).get();
  87:          }
  88:   
  89:          return recFact.multiply(swing);
  90:      }
  91:   
  92:      private static int[] smallOddSwing =
  93:          { 1, 1, 1, 3, 3, 15, 5, 35, 35, 315, 63, 693, 231, 3003, 429, 
  94:            6435, 6435, 109395, 12155, 230945, 46189, 969969, 88179, 
  95:            2028117, 676039, 16900975, 1300075, 35102025, 5014575, 
  96:            145422675, 9694845, 300540195, 300540195 };
  97:   
  98:      // -- Concurrent execution of this Class should not fail.
  99:      final class Swing implements Callable<Xint>
 100:      {
 101:   
 102:          private final PrimeSieve Sieve;
 103:          private final int N;
 104:   
 105:          public Swing(PrimeSieve sieve, int n)
 106:          {
 107:              Sieve = sieve;
 108:              N = n;
 109:          }
 110:   
 111:          // -- Returns swing(n)
 112:          public Xint call() throws Exception
 113:          {
 114:              FutureTask<Xint> Primorial = new FutureTask<Xint>(new Callable<Xint>()
 115:              {
 116:                  public Xint call()
 117:                  {
 118:                      return Sieve.getPrimorial(N / 2 + 1, N);
 119:                  }
 120:              });
 121:   
 122:              new Thread(Primorial).start();
 123:              Xint primeProduct = lowSwing();
 124:              return primeProduct.multiply(Primorial.get());
 125:          }
 126:   
 127:          private Xint lowSwing()
 128:          {
 129:              int sqrtN = (int) Math.floor(Math.sqrt(N));
 130:              IPrimeIteration pIter0 = Sieve.getIteration(3, sqrtN);
 131:              IPrimeIteration pIter1 = Sieve.getIteration(sqrtN + 1, N / 3);
 132:   
 133:              int piN = pIter0.getNumberOfPrimes() + pIter1.getNumberOfPrimes();
 134:              final int[] primeList = new int[piN];
 135:              int count = 0;
 136:   
 137:              for (int prime : pIter0)
 138:              {
 139:                  int q = N, p = 1;
 140:   
 141:                  while ((q /= prime) > 0)
 142:                  {
 143:                      if ((q & 1) == 1)
 144:                      {
 145:                          p *= prime;
 146:                      }
 147:                  }
 148:   
 149:                  if (p > 1)
 150:                  {
 151:                      primeList[count++] = p;
 152:                  }
 153:              }
 154:   
 155:              for (int prime : pIter1)
 156:              {
 157:                  if (((N / prime) & 1) == 1)
 158:                  {
 159:                      primeList[count++] = prime;
 160:                  }
 161:              }
 162:   
 163:              return Xint.product(primeList, 0, count);
 164:   
 165:          } // endOfLowSwing
 166:      } // endOfSwing
 167:  } // endOfFactorialPrimeSwingConcurrent
 168: