Какие есть варианты для представления чисел с более чем 2 ^ 81 цифр?

Question

Я натолкнулся на интересную математическую задачу, которая потребовала бы от меня выполнения некоторой арифметики с числами, которые имеют более 2 ⁸¹ цифр. Я знаю, что невозможно представить такое большое число с помощью системы, в которой для каждой цифры существует один блок памяти, но мне было интересно, есть ли какие-то способы обойти это.

Моя первоначальная мысль заключалась в том, чтобы использовать чрезвычайно большую базу вместо базы 10 (десятичной). После некоторых размышлений я считаю (но не могу проверить), что оптимальной базой будет квадратный корень из числа цифр (поэтому для числа с 2 ⁸¹ цифрами вы должны использовать базу 2 ⁴⁰ иш), что является улучшением, но не очень хорошо масштабируется и все же не очень практично.

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

Спасибо, o7

РЕДАКТИРОВАТЬ: подумав еще немного, я понимаю, что могу быть совершенно неправ в отношении «оптимального основания - квадратный корень из числа цифр», но а) поэтому я спрашиваю и б) я слишком устал, чтобы вспомнить свои первоначальные рассуждения для предположения.

РЕДАКТИРОВАТЬ 2: 1000 000 в базе 10 = F4240 в базе 16 = 364110 в базе 8. В базе 16 вам нужно 20 бит, чтобы сохранить число в базе 8, вам нужно 21, поэтому может показаться, что при увеличении базы вы уменьшает общее количество необходимых бит (опять же это может быть неправильно)

Answer 1

Это действительно проблема сжатия, представляющая собой арифметическую проблему.Что вы можете сделать с таким большим числом, целиком зависит от его сложности Колмогорова .Если вам необходимо выполнять вычисления для такого большого числа, очевидно, что оно не будет получено в виде 2 ^ 81 десятичных цифр;в этом случае сложность Колмогорова будет слишком высокой, и вы даже не сможете закончить читать вводные данные до того, как погаснет солнце.Лучший способ справиться с таким числом - это отложенная оценка и символические рациональные типы, которые предоставляет такой язык, как Scheme .Таким образом, программа может ответить на некоторые вопросы о результате вычисления числа без необходимости записывать все эти цифры в память.

Answer 2

, которые имеют более 2 ^ 81 цифр

Нефракционное число с 2 ^ 81 битами, займет 3 * 10 ^ 11 терабайт данных.За число.

Это при условии , что вы хотите, чтобы каждая цифра и данные не сжимались.

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

Такая точность бесполезна и невозможна в современных аппаратных средствах.2 ^ 81 бит займет безумное количество времени, чтобы просто пройтись по числу (9584 триллиона лет, при условии, что 1 байт занимает 1 миллисекунду), не говоря уже о умножении / делении.Я также не могу представить ни одной проблемы, которая требовала бы такой точности.

Ваш единственный вариант - снизить точность до первых N значащих цифр и использовать числа с плавающей запятой.Поскольку данные не помещаются в double, вам придется использовать библиотеку bignum с поддержкой чисел с плавающей запятой, которая обеспечивает чрезвычайно большие числа с плавающей запятой.Поскольку вы можете представить 2 ^ 81 (экспонента) в битах, вы можете сохранить начало числа, используя очень большую плавающую точку.

1000 000 в базовой десятке

Независимо от вашей базы положительное число займет минимум пол (log2 (число)) + 1 бит, чтобы сохранить его.Если base не равен 2, то для его хранения потребуется больше, чем floor (log2 (число)) + 1 бит.Числовая база не уменьшит количество требуемых бит.

Answer 3

Я думаю, вы должны просто использовать научную запись .Вы потеряете точность, но вы не можете хранить большие числа без потери точности, потому что для хранения 2 ^ 81 цифр потребуется более 10 ^ 24 бит (около тысячи миллиардов терабайт), что намного больше, чем вы можете иметь в настоящее время.