Алгоритм поиска наиболее эффективной базы для хранения больших целых чисел

Очень большие целые числа часто хранятся как массивы цифр переменной длины в памяти, в отличие от простого двоичного представления, как в случае с большинством примитивных типов 'int' или 'long', как в Java или C. Имея это в виду, Мне было бы интересно узнать алгоритм (ы), который может вычислить:

  1. При каком значении должно достигаться целое число, прежде чем оно станет более эффективным для хранения его в виде BigInteger (или эквивалентной арифметической конструкции произвольной точности) с заданным основанием для целых чисел;

  2. Какой основание будет наиболее эффективным для хранения цифр этого большого целого числа.

Я упомянул "эффективность"; под этим я подразумеваю, что меня больше всего интересует количество места, которое потребляет BigInteger, хотя мне также было бы интересно услышать какие-либо комментарии по поводу скорости обработки или сложности времени.

Источник

2 ответа

Решение

Целое число должно занимать наименьшее пространство, если оно хранится в необработанном двоичном формате (если, возможно, оно не является маленьким целым числом и тип данных слишком широка для него - для хранения 1 в 128-битном long long). Хранение по-другому не экономит память и используется для облегчения работы с такими целыми числами.

Если байт за байтом, это переводится в 256-кратное основание - 256 возможных значений, столько, сколько может содержать байт.

Источник
  1. BigInt никогда не бывает более эффективным, чем один из целочисленных типов, напрямую поддерживаемых оборудованием. Если вы можете использовать то, что поддерживается напрямую, используйте его.
  2. Что поддерживается аппаратным обеспечением наиболее эффективно, вероятно, степень 2 или, что то же самое, двоичное.
Источник
Другие вопросы по тегам