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

[beldmit]

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

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

Comments

[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 ...