Существуют ли общие стратегии реализации для арифметики произвольной точности, которые действительны независимо от конкретного языка?

Я думаю о различных способах реализации арифметики произвольной точности (иногда называемой Bignum, Integer или BigInt).

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

Точнее, кажется, что размер битов элементов массива часто является вторым по величине обычно поддерживаемым размером (возможно, чтобы облегчить выполнение вычислений с переполнением?), E. грамм. язык / платформа поддерживает 128-битные числа -> массив 64-битных чисел + 128-битная переменная для обработки переполнения.

Существуют ли принципиально разные способы реализации арифметики произвольной точности, или описанный выше способ является «испытанным и верным» способом реализовать это без огромных потерь производительности?

Мой вопрос касается базовой структуры данных, а не алгоритмов для операций . Я знаю Карацубу, Тоом-Кука и др.

16
задан soc 24 October 2011 в 15:59
поделиться