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

[beldmit]

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

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

Comments

[mochalkina.livejournal.com]

факториалы забыты.

С другой стороны, тогда можно устроить вечную музыку.

[beldmit.livejournal.com]

Не, там есть лишние восклицательные знаки.

[mochalkina.livejournal.com]

просто обычно под "тремя девятками" подразумевается "и любые арифметические знаки тоже". А так - чем факториал хуже плюса?

[bbb28.livejournal.com]

Кажется, у Перельмана было именно ТОЛЬКО тремя цифрами.

[slobin.livejournal.com]

А если "и любые арифметические знаки тоже", то любое натуральное число записывается тремя двойками ("задача Дирака"). ;-)

... Инструкций? Какой вид, какой род? ...

[mochalkina.livejournal.com]

кстати, да.

Но для не-двоек это не так! ;-)

[shaplov.livejournal.com]

Ммм... а умножить строку на строку в столбик?

[beldmit.livejournal.com]

Алгоритм придется реализовывать :-)

[shaplov.livejournal.com]

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

Оптимальности нам ведь не особо нужно, нам только одно число посчитать...

[beldmit.livejournal.com]

Коля, окстись! Грубая оценка числа операций - ln 387420489.

[yakov-sirotkin.livejournal.com]

И чему же равно это страшное число?

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

[spamsink]

Как писал Уэзерелл, алгоритм быстрого умножения можно позаимствовать у кроликов.

[fdo-eq.livejournal.com]

Я для такого использую Perl (с модулем BigInt)

[beldmit.livejournal.com]

Тоже можно.

[zabivator.livejournal.com]

erlang

[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 под дебианом будет быстрее, если нормально собрать? И да, библиотека упомянута не выше, а ниже, это я сперва комментарий в другом месте писал. ;-)

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

[mikeiva.livejournal.com]

Мысль любопытная. В cache object script тип данных на самом деле один - строка. Просто дальше эти данные по контексту обрабатываются - если она начинается с цифры, то рассматривается как число (до тех пор, пока не встретится не-цифра). В описании типов для конкретного класса длину строки, в принципе, можно переопределить (по умолчанию стоит 50 символов, я везде использую 1024). Правда, что получится, если попытаться 300М задать - не знаю. Но это и не надо, пожалуй: так как это строки, к ним можно конкатенацию применять. Нужное число для очередного пермножения - набор строк [разряды 1..1000][разряды 1001-2000]..., дальше как-нибудь уж реализуем умножение и перенос результатов между разрядами.

[sysprg.livejournal.com]

Из общедоступного быстрее всего (по времени счета :)) это можно сделать с помощью GNU MP Bignum Library (C, C++) (лучше собрать ее под 64-битную машинку).

[beldmit.livejournal.com]

А можно обосновать?

[sysprg.livejournal.com]

Она по факту самая быстрая (использует Toom-Cook и FFT алгоритмы умножения, сильно оптимизирована как в целом, так и под конкретные платформы) и я не знаю более быстрой библиотеки для общего случая, а не для специфических расчетов.

[slobin.livejournal.com]

Тем более что большинство языков, у которые не боятся проблем с лицензией (эта библиотека именно GPL, не LGPL, и потому заразна), именно через неё длинную арифметику и реализуют. ;-)

... Интересно, а что же случилось с той чайкой? ...

w00t?

[some41.livejournal.com]

GMP is distributed under the GNU LGPL
http://gmplib.org/

Re: w00t?

[slobin.livejournal.com]

Гм. И правда. Тогда совсем хорошо. ;-)

... Audio vocem de mirabili futuro ...

[slobin.livejournal.com]

Ну вот смотри, что у меня получается: допустим, мы будем реализовывать свою "очень длинную" арифметику над clisp'овской "просто длинной". То есть у нас "цифрой" будет, ну, скажем, 250000-значное число (считать удобнее сразу в десятичной системе, иначе потом переводить замучаешься). Итоговый ответ должен состоять из примерно 9⁹×log₁₀9=369693100 обычных десятичных цифр, или 1500 наших длинных. Умножать будем методом Карацубы, потому что для программной реализации (при наличии в языке рекурсии, но у нас, чай, не ФОРТРАН-IV) он даже проще, чем "в столбик". Сложность меньше n^1.6, то есть, нам потребуется меньше 120000 "просто длинных" умножений на одно "очень длинное". Количество умножений для возведения в степень примерно равно числу бит в записи показателя, то есть log₂387420489=29. Тут мы спокойно оцениваем сверху, что все промежуточные результаты будут такой же длины, как ответ (на самом деле большая их часть заметно короче). Пусть 30. На всю задачу потребуется 120000*30=3600000 "просто длинных" умножений. Одно такое умножение на моей машине занимает (замеряет) 0.75 секунды. 3600000*0.75/86400 -- в общем, месяц.

... Эльфийский ислам - это религия нордических халифов ...

[beldmit.livejournal.com]

9⁹⁷ с помощью bc посчитано за 18 минут. Поставил 9⁹⁸ на ночь.

[beldmit.livejournal.com]

beldmit@manul2$ cat tmp/exp.txt
9^9^8
quit
beldmit@manul2$ time bc tmp/exp.txt > tmp/9_9_8

real 511m52.674s
user 456m19.427s
sys 3m45.418s

То есть на моей машине оценка времени для 9⁹⁹ - наверное, неделя.

Зашедший сегодня ко мне Ран предложил использовать emacs-овый calc.

Однако

[beldmit.livejournal.com]

beldmit@manul2$ time pure !$ > tmp/9_9_7_pure
time pure tmp/997.pure > tmp/9_9_7_pure

real 0m21.070s
user 0m17.429s
sys 0m0.408s

Re: Однако

[slobin.livejournal.com]

На моей машине отношение bc и pure составило 24 раза. Правда, bc был под дебианом, а pure под виндой -- если pure под дебиан поставить, будет, наверное, как у тебя. Понятное дело, что фишка не в языке, просто он линкуется с правильными библиотеками (с уже упомянутой здесь кем-то mpz). Но это очень удобный интерфейс к этим библиотекам. ;-) А 9^9^8 у тебя посчиталось? У меня под виндой падает. (затаив дыхание) А 9^9^9?

... Ускорение темпов роста повышения производительности труда ...

Re: Однако

[slobin.livejournal.com]

В смысле GMP. Я её спросонья mpz обозвал, прошу прощения. Там выше было небольшое обсуждение, я ещё лицензию спутал.

... Административное нарушение и порицание ...