Представление чисел в алгоритмах. Длинные числа.

Определение

Длинная арифметика — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных.

Любой исполнитель алгоритма имеет дело не с числами, а с их представлением.

Цифры могут использоваться из той или иной системы счисления, обычно применяются десятичная система счисления и её степени (десять тысяч, миллиард), либо двоичная система счисления.

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

• Быстрое преобразование Фурье
• Алгоритм Карацубы