2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Возведение в очень большую степень (Pascal)
Сообщение02.02.2010, 11:18 
Прошу помочь найти способ возвести в степень 2^n, причём n>10^20. Много чего перепробовал, но найти какой-то рациональний способ так и не смог.

 
 
 
 Re: Возведение в очень большую степень (Pascal)
Сообщение02.02.2010, 11:29 
Аватара пользователя
Wade2xxx в сообщении #285115 писал(а):
2^n, причём n>10^20

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

 
 
 
 Re: Возведение в очень большую степень (Pascal)
Сообщение02.02.2010, 11:38 
Wade2xxx в сообщении #285115 писал(а):
Прошу помочь найти способ возвести в степень 2^n, причём n>10^20.
Ответ будет содержать более $3 \cdot 10^{19}$ десятичных цифр. Куда Вы его записывать планируете?

 
 
 
 Re: Возведение в очень большую степень (Pascal)
Сообщение02.02.2010, 16:42 
Даже не всякий мат. пакет такими числами может оперировать. Уж тем более язык, не дополненный каким-нибудь модулем для поддержки больших чисел. Но даже и они не помогут при таких числах!

 
 
 
 Re: Возведение в очень большую степень (Pascal)
Сообщение02.02.2010, 18:04 
Но все же меня уверяют, что решение есть)
Пробовал возводить в степень, используя процедуры и функции длинной арифметики, как результат, получил 2^100000, но дальше выбивало ошибку, вероятно уже пошла перегрузка оперативки. Число выводил в текстовый файлик, конечно, результат поражал воображение, а каким тогда должно быть решение.

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

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

 
 
 
 Re: Возведение в очень большую степень (Pascal)
Сообщение02.02.2010, 18:27 
Аватара пользователя
Wade2xxx в сообщении #285198 писал(а):
Число выводил в текстовый файлик, конечно

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

 
 
 
 Re: Возведение в очень большую степень (Pascal)
Сообщение02.02.2010, 18:29 
Аватара пользователя
Запишите это число в двоичном виде. Для больших чисел основание системы счисления не особенно важно.
Например, вот так $100000.....000000$

 
 
 
 Re: Возведение в очень большую степень (Pascal)
Сообщение02.02.2010, 18:30 
Wade2xxx в сообщении #285198 писал(а):
все ли так безнадёжно?

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

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

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

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

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

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

 
 
 
 Re: Возведение в очень большую степень (Pascal)
Сообщение02.02.2010, 19:34 
А может, в задании есть ньюанс, типа вычислить по модулю? ;)

 
 
 
 Re: Возведение в очень большую степень (Pascal)
Сообщение02.02.2010, 20:02 
Увы, такого нюанса нет :( Есть только два примера, которые надо решить:

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

 
 
 
 Re: Возведение в очень большую степень (Pascal)
Сообщение02.02.2010, 20:13 
Wade2xxx в сообщении #285198 писал(а):
но дальше выбивало ошибку, вероятно уже пошла перегрузка оперативки
На самом деле оперативная память не может "перегрузиться". Она будет записываться на диск, пока место под файл подкачки не кончится. Ошибка может быть только высокоуровневой, раз компьютер не вис и не вылетал в BSOD. Это может быть, например, нехватка памяти, отведённой паскалю как 16-разрядному процессу (если имелся в виду именно Pascal, а не Delphi).
Wade2xxx в сообщении #285198 писал(а):
методом сложения (т.е. заменить возведение в степень сложением)
Вряд ли вы его правильно поняли. Заменять возведение в степень сложением — очень глупо. Замена его умножение и то быстрее выполняться будет (на "длинных" числах тоже), а размер нужной памяти не увеличит нисколько. Может, имелись в виду числа с плавающей точкой и какие-нибудь логарифмические безобразия?

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

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

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

 
 
 
 Re: Возведение в очень большую степень (Pascal)
Сообщение03.02.2010, 22:25 
А у автора, кажется, надо именно точно. А то зачем тогда там от громаааадного числа отнимается $1$? :?

 
 
 
 Re: Возведение в очень большую степень (Pascal)
Сообщение04.02.2010, 11:32 
Аватара пользователя
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 эксабайт двоичной памяти.

 
 
 
 Re: Возведение в очень большую степень (Pascal)
Сообщение04.02.2010, 13:24 
А как автор задания убедится в том, что оно сделано? Будет разглядывать в телескоп планету, заполненную цифрами?

 
 
 [ Сообщений: 17 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group