CODEWITHSUNDEEP
cperformancearbitrary-precision
iblue
iblue

Reputation: 30434

How to multiply terabyte-sized numbers?

When multiplying very large numbers, you use FFT based multiplication (see Schönhage–Strassen algorithm). For performance reason I'm caching the twiddle factors. The problem is for huge numbers (Gigabyte-sized) I need FFT tables of size 2^30 and more, which occupy too much RAM (16 GB and above). So it seems I should use another algorithm.

There is a software called y-cruncher, which is used to calculate Pi and other constants, which can multiply terabyte-sized numbers. It uses an algorithm called Hybrid NTT and another algorithm called VST (see A Peak into y-cruncher v0.6.1 in section The VST Multiplication Algorithm).

Can anyone shed some light on these algorithms or any other algorithm which can be used to multiply terabyte-sized numbers?

Upvotes: 20

Views: 1059

Answers (1)

DU Jiaen
DU Jiaen

Reputation: 962

FFT can be done on the same array with constant number of additional memory (might need to swap the number smartly). Therefore it can be done on the harddisk as well. At worst case it's a log(N)*N times of disk access. It seems a lot slower then doing it on RAM but the overall complexity remains the same.

Upvotes: 6

Related Questions