Multiplicación rápida de enteros muy grandes

Question

Cómo multiplicar dos números muy grandes de más de 32 caracteres, por ejemplo, la multiplicación de 100! con 122! o 22^122 con 11^200 con la ayuda de dividir y conquistar, ¿algún cuerpo tiene código Java o código C#?

Answer 1

Escribí uno que usa Arrays para lograr eso, solo por diversión. Creo que la clase BigInteger de Java hace lo mismo.

Here es un ejemplo en C# que podría ser útil para usted.

Answer 2

Here's some integer multiplication algorithms

Here's a class library for numbers

Incluye los algoritmos Karatsuba y Schonhage-Strassen para multiplicar números enteros grandes.

Answer 3

Probablemente deberías usar java.math.BigInteger. Esto permite representaciones de valores enteros muy por encima de 2^32 o incluso 2^64. Los valores de BigInteger están esencialmente limitados solo por la cantidad de memoria disponible para el programa, es decir ~ 4 GB en un sistema de 32 bits y prácticamente disponible memoria física + virutal para sistemas de 64 bits.

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: He aquí un BigInteger factorial function si lo necesita

Answer 4

Here is a patched version de java.lang.BigInteger que utiliza Karatsuba y Toom-cocción:

And here is a Java class, capaces de multiplicar BigIntegers usando Schönhage-Strassen: