Занимательная математика.

[beldmit]

Помните задачку, встреченную мной впервые у Перельмана - про самое большое число, записываемое тремя девятками, 9⁹⁹?

Если подумать, то представление этого числа как строки - это всего-то 300 Мб. Наверняка его получится вычислить на современных компьютерах "в лоб" за разумное время. Осталось понять, какие языки поддерживают соответствующие типы данных.

Comments

[vitus_wagner]

Первая мысль - попробовать bc.

[beldmit.livejournal.com]

Тоже можно

[beldmit.livejournal.com]

На моей машине 9^1000000 вычислилось за совсем малое время (меньше минуты).

[vitus_wagner]

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

[vitus_wagner]

9^3
729
729^3
387420489
387420489^3
58149737003040059690390169
58149737003040059690390169^3
19662705047555291361807590852691211628310345094421476692731541553796\
6391196809
19662705047555291361807590852691211628310345094421476692731541553796\
6391196809^3
76020337568296881795356121019273424347980062229133458820966717184620\
26450847558385638399133044640009857513126790996106341658482736771462\
69252266341608361370939719058347391410024303791987065214304600142120\
7236044960360057945209303129
76020337568296881795356121019273424347980062229133458820966717184620\
26450847558385638399133044640009857513126790996106341658482736771462\
69252266341608361370939719058347391410024303791987065214304600142120\
7236044960360057945209303129^3
43932850369646432982977478265707271205801030817712671062167669775046\
63447447640297733014126124825637294350648543542990955703795034525158\
53238520182740967398746503532324400000659505126023955913142968176998\
36487769908966617129727595624540745303319016864489485057634649269145\
86951742817895579949236077834614864264486176670763939011044773249826\
31297641034277093818692823488603426279473674368943609268871793467206\
67728568847845849823500285925670638904303084794550657708062343006628\
35043975837890442454295859829645717746058684661603795674327257041212\
60940939343217905975847365096315872153240969882363435363449775254393\
01036826734397042623080139025090339914700165083187866517279846858750\
9747439118815689
...

[slobin.livejournal.com]

Я бы не стал -- оптимизаторы обычно умнее тебя. Ну вот, например, J (наследник APL):

   timespace 'x =: 9^9^5x'
3.90109 448128
   timespace 'y =: (((((((((9x^3)^3)^3)^3)^3)^3)^3)^3)^3)^3'
4.85335 574720
   timespace 'z =: ^~/(10$3),9x'
4.82759 559872
   10^.x,y,z
56347.1 56347.1 56347.1

z -- это сокращённая запись для y. Последняя строчка -- десятичный логарифм (количество цифр). 9^9^6 пока не посчиталось (10 минут прошло), но у меня машинка наверняка слабее Димкиной.

... На очень высоких путях ...

[slobin.livejournal.com]

Ага, J оказалась не лучшим для этого инструментом. CLISP считает 9^9^6 (именно 6, не 5) примерно за секунду. Правда, вскоре после этого дохнет: у него предельная длина целого 2^21 бит. Я не знаю, можно ли там пошевелить какую-нибудь константу в исходниках, или это гвоздями прибито. Но в пределах двух миллионов бит он считает БЫСТРО. ;-)

P.S. Правда, печаталка в десятичном виде ломается немного раньше: 10^400000 она мне печатает, 10^500000 уже нет. Поэтому разве что так:

[1]> (* (integer-length (expt 9 (expt 9 6))) (log 2 10))
507123.88

... Дежурный оптимист слушает ...

[slobin.livejournal.com]

Продолжаем разговор. ;-)

C:\Program Files\Pure>cat zz.pure
using system;
puts(str(pow 9 (pow 9 7)));

C:\Program Files\Pure>zztimer.cmd pure zz.pure > zz.txt
Fri Oct 23 01:15:22 2009
102

C:\Program Files\Pure>dir zz.txt
 Volume in drive C has no label.
 Volume Serial Number is 608F-C9D4

 Directory of C:\Program Files\Pure

23.10.2009  01:17         4 564 116 zz.txt
               1 File(s)      4 564 116 bytes
               0 Dir(s)   9 556 246 528 bytes free

102 секунды (Pentium III 800 MHz, 768M). zztimer.cmd написан на коленке, потому что нормального time у меня в винде не оказалось. Белявскому: если будешь сравнивать длину ответа -- у меня там в конце буква L (потому что длинное целое) и \r\n, итого три лишних байта. Pure в данном случае выступал как обёртка к упомянутой выше GNU MP library (самого языка я вообще не знаю, подсмотрел в примерах синтаксис, не более того). Правда, на 9^9^8 упал. Подозреваю, что это особенность виндовой сборки, и под Линуксом посчитает.

... Powered by МОСЭНЕРГО ...

[slobin.livejournal.com]

Вдогонку, для сравнения: bc под дебианом -- 40 минут (сравнимо с Белявскими 18). 24 раза разницы. Правда, справедливости ради, у pure был разброс 117-135-102, я нескромно написал лучший результат. А bc под виндами (MSYSовский) вообще тормоз. Хотя, может, и pure под дебианом будет быстрее, если нормально собрать? И да, библиотека упомянута не выше, а ниже, это я сперва комментарий в другом месте писал. ;-)

(фортунки остались в другой системе)