Schnelle Multiplikation sehr großer Ganzzahlen

Question

Wie man zwei sehr große Zahlen größer als 32 Zeichen multipliziert, zum Beispiel Multiplikation von 100! mit 122! oder 22^122 mit 11^200 mit Hilfe von teile und herrsche, habe irgendein Körper Java-Code oder C# -Code?

Answer 1

Ich habe selbst eine geschrieben, die Arrays verwendet, um genau das zu erreichen, nur zum Spaß. Ich glaube, dass Javas BigInteger-Klasse das Gleiche tut.

Here ist ein Beispiel in C#, das für Sie nützlich sein könnte.

Answer 2

Here's some integer multiplication algorithms

Here's a class library for numbers

Es umfasst die Karatsuba und Schönhage-Strassen-Algorithmen für große Zahlen multiplizieren.

Answer 3

Sie sollten wahrscheinlich java.math.BigInteger verwenden. Dies ermöglicht Darstellungen von ganzzahligen Werten, die deutlich über 2^32 oder sogar 2^64 liegen. BigInteger-Werte sind im Wesentlichen nur durch die Menge an Speicher begrenzt, die für das Programm verfügbar ist, d.h. ~ 4 GB auf einem 32-Bit-System und ziemlich viel verfügbarer physikalischer + virtueller Speicher für 64-Bit-Systeme.

import java.math.BigInteger; 

class Foo 
{ 
    public static void main(String args[]) 
    { 
     BigInteger bigInteger100Fact = bigFactorial(BigInteger("100")); //where bigFactorial is a user-defined function to calculate a factorial 
     BigInteger bigIntegerBar = new BigInteger("12390347425734985347537986930458903458"); 

     BigInteger product = bigIntegerFact.multiply(bigIntegerBar); 
    } 
} 

EDIT: Hier ist ein BigInteger factorial function wenn Sie benötigen ein

Answer 4

Here is a patched version von java.lang.BigInteger, die Karatsuba und Toom-Cook-Verwendungen:

And here is a Java class die BigIntegers mit Schönhage-Strassen vermehren können: