?

Log in

No account? Create an account

Сравнить несравнимое - Общество дровосеков Бердичева по изучению Мишны

Jun. 12th, 2010

12:48 am - Сравнить несравнимое

Previous Entry Share Next Entry

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

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

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

Tags:

Comments:

[User Picture]
From:kcmamu
Date:June 12th, 2010 09:46 am (UTC)
(Link)
Это может и посчитаться. Вот кабы еще один этаж добавить...
(Reply) (Thread)
[User Picture]
From:spamsink
Date:June 13th, 2010 01:48 am (UTC)
(Link)
Посчитать 999-ю цифру (это всего в 300 тысяч раз меньше гугола) девятеричного разложения пи? Ох, вряд ли...

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

(Reply) (Parent) (Thread)
[User Picture]
From:kcmamu
Date:June 13th, 2010 02:51 am (UTC)
(Link)
N знаков пи вроде как считаются за O(N log2 N log log N) на машине Тьюринга -- что-то типа гугола операций и потребуется. Распараллеливаем на 1080 атомов Вселенной -- и считаем.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:June 13th, 2010 04:38 am (UTC)
(Link)
Программа в атом не поместится.
(Reply) (Parent) (Thread)
[User Picture]
From:kcmamu
Date:June 13th, 2010 04:40 am (UTC)
(Link)
При такой точности прикидок -- что атом, что миллиард атомов...
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:June 13th, 2010 04:56 am (UTC)
(Link)
Вопрос, хорошо ли распараллеливается это вычисление, тоже представляет интерес. Получение цифр пи, вроде, не очень, а гугол фемтосекунд - долговато будет.
(Reply) (Parent) (Thread)