Как в BigInteger хранятся числа?

245

01 марта 2017, 18:09

Я вот пишу для своих нужд небольшую библиотеку для работы с длинными числами. Написал и сложение, и умножение методом Карацубы. Считает то правильно, но вот я храню данные в векторе uint в 1000 * 1000 * 1000 системе счисления, то есть 9 десятичных цифр на один элемент вектора: {123456789, 987654321, 456789123} Но вот вижу что в Java и С# уже есть готовые классы BigInteger, и методы там такие bitCount и конструктор принимающий число в двоичном виде. То есть числа хранятся в двоичном виде, а не в десятичном? Не могу понять, зачем хранить в двоичном виде? Это быстрей будет? Просто инфы по этому поводу найти не могу, везде о длинной арифметике где не читал, числа для длинной арифметике представляются в десятичном виде. Вот если хранить в двоичном виде, то как перевести число длиной 500 знаков в десятичную строку? Сначала переводят в десятичный вид, а потом в строку? Буду благодарен если дадите ссылку где описывается длинная арифметика представленная в двоичном виде.

Answer 1

«Длинные» числа хранятся внутри не «в двоичном» или «десятичном» виде. Числа во внутреннем представлении вовсе не являются числами в какой-то системе счисления. Система счисления появляется лишь при переводе числа в строковое представление.

Окей, как же всё-таки хранятся числа? В .NET вы можете видеть в исходниках, что они хранятся как список чисел типа Int32, то есть, список 32-битных чисел.

При этом каждое 32-битное число выступает в роли одной цифры, так что можно считать, что используется внутри представление в системе счисления по основанию 2³².

Почему не используются десятичные цифры, по одной цифре? Дело в том, что при этом хранение будет менее эффективно: для 32-битного числа используются все его возможные значения, а для представления одной десятичной цифры расходуется минимум байт (который мог бы хранить до 256 различных значений).

Далее, операции с нативными 32-битыми словами намного эффективнее операций с 10-ичными цифрами. При вычислении в 10-ичной системе для вычисления суммы отделение разряда результата от переноса требует деления на 10. А при вычислении с 32-битными словами результат получается сам собой, ведь процессор при сложении 32-битных чисел автоматически выдаёт 32-битный результат и перенос, деление вовсе не нужно.

То же относится и к умножению.

А переводится большая десятичная строка в «длинное» число точно так же, как и маленькая десятичная строка в число типа int или long.