Berechnung von großen Faktoren genau

Question

Ich muss eine sehr große Fakultät berechnen, aber es muss genau sein. Ich kann keine Näherung verwenden.

Ich möchte 1.000.000.000 !, aber es ist ziemlich langsam. Bis jetzt habe ich die Leistung ein wenig verbessert, aber es ist immer noch nicht genug. Hier ist, was ich habe:

 BigInteger Factor100 = BigInteger.One; 
     BigInteger Factor10000 = BigInteger.One; 
     Status = "Factorising"; 
     for (i++; i <= StartN; i++) 
     { 
      if (Worker.CancellationPending) 
      { 
       e.Cancel = true; 
       break; 
      } 

      if (i % 10000 == 0) 
      { 
       Factor100 = Factor100 * i; 
       Factor10000 = Factor10000 * Factor100; 
       iFactorial = iFactorial * Factor10000; 
       Factor100 = BigInteger.One; 
       Factor10000 = BigInteger.One; 
      } 
      else if (i % 100 == 0) 
      { 
       Factor100 = Factor100 * i; 
       Factor10000 = Factor10000 * Factor100; 
       Factor100 = BigInteger.One; 
      } 
      else 
      { 
       Factor100 = Factor100 * i; 
      } 

      //iFactorial = i * iFactorial; 

      if (i % Updates == 0) 
      { 
       Worker.ReportProgress(50, new Tuple<string, BigInteger>("Factorialising", i)); 
       using (StreamWriter DropWriter = File.CreateText(@FileLocation + "FactorialDropCatcher.dat")) 
       { 
        DropWriter.WriteLine("N: " + i); 
        DropWriter.WriteLine("N!: " + iFactorial); 
       } 
      } 
     } 

Also habe ich versucht, zu bleiben weg von der irrsinnig große Zahl Berechnung, bis es notwendig wurde, die Lauf Factorial Nummer aktualisiert nur einmal alle 10.000 zu halten.

Wie könnte ich das schneller berechnen?

Answer 1

Dafür verwende ich nur eine Erweiterungsmethode für IEnumerable <int> .Product(). Es ist wie IEnumerable <int> .Sum(), aber das Produkt. Für einen Faktor von N, erstellen Sie einfach einen Bereich von 1 bis N und nehmen Sie sein Produkt.

Dies ist überraschend schnell, und wenn Ihre Anforderungen an die Anzahl der Berechnungen eher extrem sind, ist das Ändern von PLINQ ein Kinderspiel!

public class FactorialExample 
{ 
    public static BigInteger Factorial(int n) 
    { 
     return Enumerable.Range(2, n).Product(); 
    }  
} 

public static class IEnumerableExtensionMethods 
{ 
    public static BigInteger Product(this IEnumerable<int> multiplicands) 
    { 
     System.Numerics.BigInteger result = 1; 
     foreach (int multiplier in multiplicands) 
     { 
      result = System.Numerics.BigInteger.Multiply(result, multiplier); 
     } 
     return result; 
    } 
}