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

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

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

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

Спасибо о7

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

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


math base arbitrary-precision largenumber
person Letseatlunch    schedule 08.02.2012    source источник
comment
Какие операции вы будете выполнять над этими числами?   -  person templatetypedef    schedule 08.02.2012
comment
@templatetypedef просто простое сложение/вычитание и умножение/деление (и да, я понимаю, что даже с БПФ я был бы чуть менее чем линейно медленным)   -  person Letseatlunch    schedule 08.02.2012
comment
что оптимальным основанием будет квадратный корень из числа оптимальных для чего цифр? Объем информации, которую вам нужно будет хранить, будет одинаковым независимо от используемой вами базы.   -  person Sunny88    schedule 08.02.2012
comment
Можете ли вы описать эту проблему более подробно? Возможно, есть лучший подход к ее решению.   -  person templatetypedef    schedule 08.02.2012
comment
Для точного представления 2^81 десятичной цифры требуется примерно 2^269 бит. Я не думаю, что есть какие-то ярлыки, если вы не знаете, что какая-то значительная часть цифр будет равна нулю.   -  person Mark Ransom    schedule 08.02.2012
comment
@ Sunny88 Количество информации, которую вам нужно будет хранить, будет одинаковым, независимо от используемой вами базы. я не думаю, что это правда, основываясь на моем аргументе в редактировании 2   -  person Letseatlunch    schedule 08.02.2012
comment
Что касается редактирования 2, записываете ли вы число с помощью базы 8 или базы 16, это не влияет на то, сколько битов оно фактически занимает, потому что они оба преобразуются обратно в двоичный код одинаковым образом, а двоичный код - это то, как эти числа на самом деле хранятся. Шестнадцатеричное представление становится 1111 0100 0010 0100 0000, а восьмеричное — 011 110 100 001 001 000 000. Последний имеет начальный нуль из-за того, как вы решили сгруппировать эти биты, но начальный ноль не нужно сохранять.   -  person David Z    schedule 08.02.2012
comment
@MarkRansom Для хранения 2 ^ 81 десятичной цифры не требуется 2 ^ 269 бит. Каждая цифра может храниться не более чем в 4 битах, поэтому число равно не более 4*(2^81) или 2^83, а не 2^269.   -  person Sunny88    schedule 08.02.2012
comment
@ Sunny88, спасибо - я уже поздно написал это, это мое единственное оправдание. Тем не менее 2 ^ 83 — это слишком много бит, чтобы поместиться в памяти.   -  person Mark Ransom    schedule 08.02.2012

Ответы (3)


arrow_upward
3
arrow_downward

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

person Kyle Jones    schedule 08.02.2012

arrow_upward
1
arrow_downward

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

person Sunny88    schedule 08.02.2012
comment
откуда вы взяли 10^24 бита? - person Letseatlunch; 08.02.2012
comment
@ Letseatlunch 24 - это log (2 ^ 84), на самом деле это 25, но все же больше 24. Я только что изменил 2 ^ 84 на нотацию с основанием 10. - person Sunny88; 08.02.2012
comment
@ Sunny88: Для хранения 2 ^ 81 десятичной цифры вам потребуется 2 ^ 269 бит. Для хранения 2 ^ 81 бит вам понадобится 2 ^ 81 бит, даже если они могут быть представлены 10 ^ 24 десятичными цифрами. Цифра занимает более одного бита. Запомни. - person SigTerm; 08.02.2012
comment
@SigTerm Для хранения 2 ^ 81 десятичной цифры не требуется 2 ^ 269 бит. Каждая цифра может храниться не более чем в 4 битах, поэтому число равно не более 4*(2^81) или 2^83, а не 2^269. - person Sunny88; 08.02.2012

arrow_upward
1
arrow_downward

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

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

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

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

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

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

1000000 по основанию десять

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

person SigTerm    schedule 08.02.2012