Оптимизация вычислений с большими числами

Уровень 0 · материалов: 4

В кластер входят документы, посвященные исключительно методам и сложности умножения больших целых чисел, и не включают расчет последовательностей, проверку на простоту или факторизацию чисел.

Общие признаки: алгоритмы умножения больших целых чисел, снижение временной сложности, математические оптимизации, длинная арифметика

Группа выше: Числа: представление, точность и арифметика

Материалы

• #24079 — Multiplying Large Numbers Using the Karatsuba Algorithm — Представитель этого кластера

  Умножение длинных чисел методом Карацубы — IDY

  Смысл: The text explains the Karatsuba algorithm for fast multiplication of large integers, providing the mathematical theory, a recursive example, and a practical C++ implementation to reduce computational complexity from O(n²) to O(n^1.58).

  A technical guide explaining the Karatsuba fast multiplication algorithm with mathematical proofs and a C++ implementation for handling large numbers.

• #258 — Fast Integer Multiplication Algorithms: From Schoolbook to Schönhage-Strassen

  Алгоритмы быстрого умножения чисел: от столбика до Шенхаге-Штрассена — saluev

  Смысл: The main idea is to demonstrate that integer multiplication, often taken for granted as a primitive operation, is a complex mathematical problem with a rich history of algorithmic optimization. By leveraging polynomials, Fourier transforms, and modular arithmetic, the computational complexity can be reduced from quadratic to nearly linear.

  An educational exploration of integer multiplication algorithms, tracing the path from the simple schoolbook method to the complex, near-linear Schönhage-Strassen and FFT-based approaches.

• #1047 — Implementing Arbitrary-Precision Arithmetic in C++

  Реализация длииииииинной арифметики на C++ — hatred1993

  Смысл: The main idea is to provide a practical educational guide on how to implement a Big Integer library from scratch in C++ using school-book algorithms for basic mathematical operations.

  A technical guide on implementing a Big Integer class in C++ using a vector-based storage system and school-book arithmetic algorithms.

• #16846 — The Evolution of Fast Multiplication Algorithms

  Математики обнаружили идеальный способ перемножения чисел — SLY_G

  Смысл: The main idea is that mathematicians have finally reached a theoretical 'speed limit' for multiplying large integers (n log n complexity), completing a quest that spanned decades of algorithmic refinement from Karatsuba to Harvey and van der Hoeven.

  Mathematicians have discovered the fastest known method for multiplying large numbers, achieving the theoretical complexity of n log n.