Сравнить несравнимое

[spamsink]

Задачка у Кости Кнопа, которую я вчера решил опасным для жизни образом - за рулём по дороге на работу, натолкнула меня на идею задачи: найти самую короткую пару арифметических выражений, о которых мы были бы не в состоянии сказать, какое из них больше, за разумное - скажем, сравнимое с временем жизни солнечной системы, время.

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

Мой вариант: frac(9⁹⁹⁹π) и 0.5,
что составит 9 9 ↑ 9 pow 9 pow pi * frac, да . 5, итого 12.

Comments

[kcmamu.livejournal.com]

Это может и посчитаться. Вот кабы еще один этаж добавить...

[spamsink]

Посчитать 9⁹⁹-ю цифру (это всего в 300 тысяч раз меньше гугола) девятеричного разложения пи? Ох, вряд ли...

Пожалуй, можно сократить результат на одно нажатие, вместо * pi взяв просто exp. Возводить в степень почти с гуголом цифр за разумное время вроде пока не научились.

[kcmamu.livejournal.com]

N знаков пи вроде как считаются за O(N log² N log log N) на машине Тьюринга -- что-то типа гугола операций и потребуется. Распараллеливаем на 10⁸⁰ атомов Вселенной -- и считаем.

[spamsink]

Программа в атом не поместится.

[kcmamu.livejournal.com]

При такой точности прикидок -- что атом, что миллиард атомов...

[spamsink]

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