Moltiplicazione veloce di interi molto grandi

Question

Come moltiplicare due numeri molto grandi superiori a 32 caratteri, ad esempio la moltiplicazione di 100! con 122! o 22^122 con 11^200 con l'aiuto di divide e conquista, qualsiasi corpo ha codice java o codice C#?

Answer 1

Ne ho scritto uno anch'io che utilizza gli array per realizzare proprio questo, solo per divertimento. Credo che la classe BigInteger di Java faccia la stessa cosa però.

Here è un esempio in C# che potrebbe esserti utile.

Answer 2

Here's some integer multiplication algorithms

Here's a class library for numbers

Esso comprende gli algoritmi Karatsuba e Schonhage-Strassen per moltiplicare i grandi numeri interi.

Answer 3

Probabilmente si dovrebbe usare java.math.BigInteger. Ciò consente rappresentazioni di valori interi ben superiori a 2^32 o persino a 2^64. I valori di BigInteger sono essenzialmente limitati solo dalla quantità di memoria disponibile per il programma, vale a dire ~ 4 GB su un sistema a 32 bit e memoria fisico + virutale praticamente disponibile per i sistemi a 64 bit.

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: Ecco un BigInteger factorial function se ne avrete bisogno

Answer 4

Here is a patched version di java.lang.BigInteger che utilizza Karatsuba e Toom-Cook:

And here is a Java class in grado di moltiplicare BigIntegers utilizzando Schönhage-Strassen: