При умножении очень больших чисел вы используете умножение на основе FFT (см. алгоритм Schönhage-Strassen). По соображениям производительности я кэширую факторы twiddle. Проблема в огромных количествах (размер Gigabyte) Мне нужны таблицы FFT размером 2 ^ 30 и более, которые занимают слишком много ОЗУ (16 ГБ и выше). Поэтому мне кажется, что я должен использовать другой алгоритм.
Существует программное обеспечение, называемое y-cruncher, которое используется для вычисления Pi и других констант, которые могут умножать числа на терабайт. Он использует алгоритм под названием Hybrid NTT и другой алгоритм под названием VST (см. A Пик в y-cruncher v0.6.1 в разделе Алгоритм умножения VST).
Может кто-нибудь пролить свет на эти алгоритмы или любой другой алгоритм, который можно использовать для умножить на терабайтные числа?
