Возведение в очень большую степень (Pascal)

[Wade2xxx]

Прошу помочь найти способ возвести в степень 2^n, причём n>10^20. Много чего перепробовал, но найти какой-то рациональний способ так и не смог.

[meduza]

Wade2xxx в сообщении #285115 писал(а):

2^n, причём n>10^20

Ого! Если у вас фигирируют такие числа (которые даже астрономическирми нельзя назвать, во вселенной атомов меньше), то значит что-то неправильно.

[Maslov]

Wade2xxx в сообщении #285115 писал(а):

Прошу помочь найти способ возвести в степень 2^n, причём n>10^20.

Ответ будет содержать более $3 \cdot 10^{19}$ десятичных цифр. Куда Вы его записывать планируете?

[arseniiv]

Даже не всякий мат. пакет такими числами может оперировать. Уж тем более язык, не дополненный каким-нибудь модулем для поддержки больших чисел. Но даже и они не помогут при таких числах!

[Wade2xxx]

Но все же меня уверяют, что решение есть)
Пробовал возводить в степень, используя процедуры и функции длинной арифметики, как результат, получил 2^100000, но дальше выбивало ошибку, вероятно уже пошла перегрузка оперативки. Число выводил в текстовый файлик, конечно, результат поражал воображение, а каким тогда должно быть решение.

Автор задания уверял меня, что такое возведение можно сделать методом сложения (т.е. заменить возведение в степень сложением). Но я затрудняюсь в его реализации, да и понял, в принципе, не так хорошо, как хотелось бы, т.к. сложно первокурснику с этим всем разобраться

все ли так безнадёжно?

[meduza]

Wade2xxx в сообщении #285198 писал(а):

Число выводил в текстовый файлик, конечно

Вы его в десятичном виде сохраняете или как? Хотя как не сохраняй, диска не хватит (более того, придполагаю, что всех существующих в мире жёстких жисков не хватит). ($2^{100000}$ хоть и нереальное число, но вполне считаемое и даже выводимое на экран (в несколько страниц), а вот $2^{10^{20}}$ -- уже перебор, можете смело коруглять до $+\infty$).

[gris]

Запишите это число в двоичном виде. Для больших чисел основание системы счисления не особенно важно.
Например, вот так $100000.....000000$

[ewert]

Wade2xxx в сообщении #285198 писал(а):

все ли так безнадёжно?

Всё. Даже предельная ёмкость винчестера -- условно говоря, один терабайт -- это порядка $10^{12}$ десятичных цифр (ну пусть даже вдвое больше, неважно). Но производить вычисления непосредственно на винчестере -- никаких жизней не хватит. Если же внутри оперативной памяти -- (опять же условно) один гигабайт -- то т всего-то $10^{9}$ цифр.

И опять же прикиньте: сколько лесу придётся вырубить, чтобы все эти цифры напечатать?...

-- Вт фев 02, 2010 18:36:42 --

meduza в сообщении #285206 писал(а):

(более того, придполагаю, что всех существующих в мире жёстких жисков не хватит)

Всех -- скорее всего, хватит. Всего-то и нужно, что несколько сот миллионов компьютеров, тьфу.

(Вот, нагуглил: в 2008-м году мировой рынок ПК составил около 300 миллионов штук, и этого уже достаточно -- средний размер жёсткого диска уже тогда, наверное, зашкаливал за сотню гигабайт. И это только ПК, и только выпущенные за год.)

[venco]

А может, в задании есть ньюанс, типа вычислить по модулю?

[Wade2xxx]

Увы, такого нюанса нет Есть только два примера, которые надо решить:

$2^{n+1}-1=$ и $2^n/(3^{n+1}-1)$, причём n>$10^{20}$

[arseniiv]

Wade2xxx в сообщении #285198 писал(а):

но дальше выбивало ошибку, вероятно уже пошла перегрузка оперативки

На самом деле оперативная память не может "перегрузиться". Она будет записываться на диск, пока место под файл подкачки не кончится. Ошибка может быть только высокоуровневой, раз компьютер не вис и не вылетал в BSOD. Это может быть, например, нехватка памяти, отведённой паскалю как 16-разрядному процессу (если имелся в виду именно Pascal, а не Delphi).

Wade2xxx в сообщении #285198 писал(а):

методом сложения (т.е. заменить возведение в степень сложением)

Вряд ли вы его правильно поняли. Заменять возведение в степень сложением — очень глупо. Замена его умножение и то быстрее выполняться будет (на "длинных" числах тоже), а размер нужной памяти не увеличит нисколько. Может, имелись в виду числа с плавающей точкой и какие-нибудь логарифмические безобразия?

Кстати, зачем такое число?

P.S. А это точно надо вычислять программно?

[begin2009]

А если так. Берем пользовательский тип данных: запись с полями мантисса и степень. Первое вещественное, второе целое. И разрабатываем арифметику для этого типа. (Умножение и деление легко, а при сложении и вычитании - приводим степени к одному числу). Так же разрабатываем необходимые для задачи функции с этим типом данных. В этом подходе минус один - точность. Меньшие разряды будут округляться автоматически.

[arseniiv]

А у автора, кажется, надо именно точно. А то зачем тогда там от громаааадного числа отнимается $1$?

[juna]

Wade2xxx в сообщении #285234 писал(а):

Увы, такого нюанса нет Есть только два примера, которые надо решить:

$2^{n+1}-1=$ и $2^n/(3^{n+1}-1)$, причём n>$10^{20}$

Бред какой-то. Причем тут паскаль? Число $2^{n+1}$ в двоичной системе --- это 1 и еще n+1 нуль, соответсвенно число $2^{n+1}-1$ - это n+1 единица. Для его записи потребуется более 10 эксабайт двоичной памяти.

[tolstopuz]

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