Nhân nhanh các số nguyên rất lớn

Question

Cách nhân hai số rất lớn lớn hơn 32 ký tự ví dụ nhân với 100! với 122! hoặc 22^122 với 11^200 bởi sự giúp đỡ của phân chia và chinh phục, làm bất kỳ cơ thể có mã java hoặc mã C#?

Answer 1

Tôi đã viết một bản thân mình sử dụng Mảng để thực hiện điều đó, chỉ để cho vui. Tôi tin rằng lớp BigInteger của Java cũng vậy.

Here là ví dụ trong C# có thể hữu ích cho bạn.

Answer 2

Here's some integer multiplication algorithms

Here's a class library for numbers

Nó bao gồm các thuật toán Karatsuba và Schonhage-Strassen cho nhân số nguyên lớn.

Answer 3

Có thể bạn nên sử dụng java.math.BigInteger. Điều này cho phép biểu diễn các giá trị số nguyên vượt quá 2^32 hoặc thậm chí 2^64. Giá trị BigInteger về bản chất chỉ giới hạn bởi lượng bộ nhớ có sẵn cho chương trình, tức là ~ 4 GB trên hệ thống 32 bit và bộ nhớ vật lý + virut có sẵn cho hệ thống 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: Dưới đây là một BigInteger factorial function nếu bạn cần một

Answer 4

Here is a patched version của java.lang.BigInteger sử dụng Karatsuba và Toom-Cook:

And here is a Java class rằng có thể nhân BigIntegers sử dụng Schönhage-Strassen: