Szybkie mnożenie bardzo dużych liczb całkowitych

Question

Jak pomnożyć dwie bardzo duże liczby większe niż 32 znaki, na przykład mnożenie 100! z 122! lub 22^122 z 11^200 przy pomocy dzielenia i podbijania, czy jakiekolwiek ciało ma kod java lub kod C#?

Answer 1

Napisałem jeden, który używa Arrays, aby to osiągnąć, tylko dla zabawy. Sądzę, że klasa Java w języku BigInteger robi to samo.

Here to przykład w języku C#, który może ci się przydać.

Answer 2

Here's some integer multiplication algorithms

Here's a class library for numbers

Zawiera algorytmy Karatsuba i Schonhage-Strassen do mnożenia dużych liczb całkowitych.

Answer 3

Powinieneś prawdopodobnie używać java.math.BigInteger. Pozwala to na reprezentację wartości całkowitych znacznie przekraczających 2^32 lub nawet 2^64. Wartości BigInteger są zasadniczo ograniczone jedynie ilością pamięci dostępnej dla programu, tj. ~ 4 GB w systemie 32-bitowym i prawie dostępną fizyczną + wirtualną pamięcią dla systemów 64-bitowych.

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: Oto BigInteger factorial function jeśli zajdzie taka potrzeba

Answer 4

Here is a patched version z java.lang.BigInteger który używa Karatsuba i toom-Cook

And here is a Java class które można mnożyć BigIntegers użyciu Schönhage-Strassen: