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

[beldmit]

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

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

Comments

[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 обозвал, прошу прощения. Там выше было небольшое обсуждение, я ещё лицензию спутал.

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