Возведение двойки в миллиардную степень

@JluMoH4uK · Регистрация: 05.07.2013

Студворк — интернет-сервис помощи студентам

Наверное, этот вопрос уже задавался тысячу раз, но все же. Как возвести 2 в степень миллиард? Я пробовал воспользоваться !bc, но смог вычислить только 2 в миллионной. Дальше видимо уже сожралась вся ОЗУ. Что делать?
P.S.
нужно точное значение.

@Thinker · 06.07.2013, 15:46

Сообщение от JluMoH4uK

оно сожрало 2,5 Гб, записалось в файл, а вывести его все равно сложно.

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

Рекомендую использовать бинарное возведение в степень, так намного быстрее получится.

@CPlusPlusBest · 06.07.2013, 16:41

Это будет адски долго надо подумать...

@Thinker · 06.07.2013, 17:19

по поводу времени вычисления. предположим, что схема вычисления следующая:
2=1+1 ,4 = 2+2, 8 = 4+4, 16 = 8+8 и т.д. Пусть у нас имеется массив для хранения больших чисел. На быстрых компьютерах с частотой ~3200 МГц и скоростью памяти ~1600 МГц каждые 500 000 000 элементов массива обрабатываются не быстрее одной секунды (то есть это просто пробежать по массиву, без арифметических операций).
Искомое число занимает более 250 000 000 и менее 350 000 000 десятичных цифр.
Теперь считаем.
на первых четырех шагах обрабатывается не менее чем по одной десятичной цифре,
на следующих четырех шагах обрабатывается не менее чем по две десятичные цифры
и т.д.
итого, таким алгоритмом придется обработать более
$https://www.cyberforum.ru/cgi-bin/latex.cgi?4(1 + 2 + ... + 50\,000\,000) \approx 2\cdot 50\,000\,000^2$ десятичных цифр (элементов массива). чтобы получить искомое число понадобится более чем
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{2\cdot 50\,000\,000^2}{500\,000\,000}$ = 10 000 000 секунд $https://www.cyberforum.ru/cgi-bin/latex.cgi?\approx$ 115 суток.

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

Вывод: для данной задачи нужен продвинутый способ.

Добавлено через 5 минут

Не по теме:

easybudda, вот для чего нужно оценивать алгоритмы;)

@JluMoH4uK · 06.07.2013, 19:59 **[ТС]**

Сообщение от Байт

лучше, наверное в миллиардичной системе счисления.

Пока катался на электричке мне стало интересно, как работать с сс, где даже для записи числа элементарно не хватит символов?

Croessmah · 06.07.2013, 20:54

JluMoH4uK, Вопрос не в записи, вопрос в восприятии

Байт · 07.07.2013, 10:17

Сообщение от JluMoH4uK

будет ли такой метод хорош с точки зрения памяти и скорости?

Тут ничего утешительного сказать не могу. Задачи такого типа - на пределе возможностей наших домашних компьютеров. ИМХО, все что можно сделать, это сначала реализовать "как-нибудь", а потом искать узкие места по скорости и памяти.
Ну а вывод гигабайтых файлов по определению штука неприятная. Если вопрос стоит именно в получении бумажного результата, тогда остается только искать более скорострельный принтер.
Может быть не стоит заморачиваться на печати результата? Ответ получен в виде файла, любой интересующийся может посмотреть любую цифру, может даже поиграться с ними (проверить, например). А гигабайтную распечатку последовательности цифр все равно смотреть никто не будет, это зрелище не для человека, а для компьютера.

@Thinker · 07.07.2013, 10:45

Сообщение от Байт

все что можно сделать, это сначала реализовать "как-нибудь", а потом искать узкие места по скорости и памяти.

если как-нибудь, то результата придется несколько месяцев ждать

ну здесь же моментально считает
2^1000000000

желательно здесь использовать бинарное возведение в степень и алгоритм Шёнхаге — Штрассена, тогда самих умножений будет не более 62. если никаких математических ухищрений нет в этой задаче, то такой способ может подойти (наверное). JluMoH4uK, можете попробовать на досуге

@JluMoH4uK · 07.07.2013, 20:06 **[ТС]**

Сообщение от Thinker

ну здесь же моментально считает
2^1000000000

Хм, надо же. Будет с чем сравнивать

Правда, не совсем понятно, можно ли посмотреть, что там в первых разрядах.

@Thinker · 07.07.2013, 20:53

Сообщение от JluMoH4uK

Правда, не совсем понятно, можно ли посмотреть, что там в первых разрядах.

там же есть кнопка "more digits"

Кликните здесь для просмотра всего текста

4.61297600116906939311611922103731601870 4689765158218586254214245826256398377936 8760542473832919454797396248839846698299 4884373635802480893458587783790128767693 8540349173655314398812091032767308660103 3236321433429160251440993143429536510962 6073494971618082585617774494417629615723 3154734554788023201338190792778625712844 9653176995723704999802319244843824462664 8060461911000698619126614776615488812498 5892363957367265011576721424242203129481 1262383783682566329693584112302073198027 8394561063245328653731353445642043287928 1240975710342399411242228861967668160612 7303103776769269323509280428144454927922 1371223395264480550950875548871182437925 5070803106724282267932069295109783295895 2137069126239014073507404713441843214008 8884846898171426078952133484922068087172 6235148878664592185902250183355622581345 5995214748577394915639366619589252516890 6303010403425279600404430516019982567383 7139240528868949378895685091903449279592 4716246547836130186894097183038048193606 1497171735829268402101458442233244460480 8963408477408981913111183927428306344901 5589670503651573479652290132415855653951 2735096830250712509602177448026567121202 5691263720367655845700754970300817567696 2440699739357590208099882648505860900083 7193214153280103684443344103448857811369 4558571498867698211831497043888336881251 6751716827869472047703826716399733418824 0724798672303404141066429617988094253863 0988660559064933155325960417996779381115 4577709951633614823712275769691911657521 4228517030727996859083464057852268038716 9585996511665043680046352479623421968762 0173749232882200537280758054515054059259 2243354201091924305987333576214770741089 8084479233370987052696262989267506163450 9825372760262889071774769496673592043575 7796103835225762829056486339042747721876 0845838916419612415517380781778384745026 0738625985251190698678527981261871954786 6354742932145717233561943173651652461878 1763414697315923769072799418114937706289 1328896159429017985495909773653781052043 9869641365903585957945246333307238929974 3014156440530202972865919360891227409877 4051218451325489819208632440211280259451 8727918991630804514863053438961678947006 5405071928203810134854979230138156468761 5032614853864959974241677810465939266477 7614649460257588866558226883330782838609 0828091009669051233888301956525233847098 2967574480486228385741603354672389624348 7879874254186854000374510042286718515007 6510041693874774108059344375180102053173 3761395116433085257538916030724609638547 5698238124685686599194516050820068753955 8343008432208716721374412595846833905213 5353800176924146868710181598433786750796 7499788480197317800994274118568286209457 6852592258803607339944931151378987782338 6357216234194046025567374076511705562853 6838142512679697676548964862288589194784 4551373234975221514025499589619108524379 2141892634089223343386624271095508554735 6099034623346492552841224373908788779110 1140253680991219578987614714313484805919 2668631698721347763607209664948053608277 9842858796351217885102360555640772580205 9071024918100766507216486104341128280662 2318595045948860046255574210488404030141 6194380779263335876528648843666800780402 7519592077899305978003062849268496484507 3057044286439616225130095766904115396190 1210760272906247291686802387545842340232 3656927895164422239816571352166040107845 8633688211767738592550284919900207854872 1140689842220354998813245815433959410556 6472857967062931965792774514596393876076 6015264781079624523123489300296224872224 2794534461635544036853631279948677071127 1160402156044551466599797240568338885038 5809441700685626233434080710244488132827 2189971919164473808092552327525832472498 2931213078604641588983597065205371753839 0523263038678209696086670302362723054552 2160070986875629763912786583542123775735 1917668666331992174837008449478431421134 6538706797770844729003367380642603722165 1807927531046493870818650470508425810033 7520818351860124446018514164703708822764 7577363630367344230454617206246865395860 1642740041692927851551721882592082194217 0641454203282... × 10^301029995

младшие цифры тоже указаны: ...1787109376

Новые блоги и статьи Все статьи Все блоги /
Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .	Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .
Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .	Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .	мат медиц модель 30. презентация проекта anaschu 27.08.2026 хоп хоп хоп хидахоп, а я кладую))

@JluMoH4uK 0 / 0 / 0 Регистрация: 05.07.2013 Сообщений: 8

	Возведение двойки в миллиардную степень 05.07.2013, 00:24. Показов 13919. Ответов 28 Метки нет (Все метки) Наверное, этот вопрос уже задавался тысячу раз, но все же. Как возвести 2 в степень миллиард? Я пробовал воспользоваться !bc, но смог вычислить только 2 в миллионной. Дальше видимо уже сожралась вся ОЗУ. Что делать? P.S. нужно точное значение. 0

@CPlusPlusBest 0 / 0 / 0 Регистрация: 14.04.2013 Сообщений: 23
	06.07.2013, 16:41
	Это будет адски долго надо подумать... 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	06.07.2013, 17:19
	по поводу времени вычисления. предположим, что схема вычисления следующая: 2=1+1 ,4 = 2+2, 8 = 4+4, 16 = 8+8 и т.д. Пусть у нас имеется массив для хранения больших чисел. На быстрых компьютерах с частотой ~3200 МГц и скоростью памяти ~1600 МГц каждые 500 000 000 элементов массива обрабатываются не быстрее одной секунды (то есть это просто пробежать по массиву, без арифметических операций). Искомое число занимает более 250 000 000 и менее 350 000 000 десятичных цифр. Теперь считаем. на первых четырех шагах обрабатывается не менее чем по одной десятичной цифре, на следующих четырех шагах обрабатывается не менее чем по две десятичные цифры и т.д. итого, таким алгоритмом придется обработать более $https://www.cyberforum.ru/cgi-bin/latex.cgi?4(1 + 2 + ... + 50\,000\,000) \approx 2\cdot 50\,000\,000^2$ десятичных цифр (элементов массива). чтобы получить искомое число понадобится более чем $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{2\cdot 50\,000\,000^2}{500\,000\,000}$ = 10 000 000 секунд $https://www.cyberforum.ru/cgi-bin/latex.cgi?\approx$ 115 суток. Эти оценки не учитывают многочисленные арифметические операции данной задачи, а только обращения к элементам. Вывод: для данной задачи нужен продвинутый способ. Добавлено через 5 минут Не по теме: easybudda, вот для чего нужно оценивать алгоритмы;) 1

Croessmah Неэпический 18150 / 10732 / 2067 Регистрация: 27.09.2012 Сообщений: 27,047 Записей в блоге: 1
	06.07.2013, 20:54
	JluMoH4uK, Вопрос не в записи, вопрос в восприятии 0