факториал

На десяти миллионах: 5 минут у GMP против 18 минут у SuperFac.exe. По памяти несколько удивляет, что внешние счётчики показывают совсем не то, что пишет сама программа в "Memory used", но, как бы то ни было, общие показатели 650K у GMP против 1570K у SuperFac.

А вообще, собственно, скомпилированный вариант программы выше под Win32 (и generic x86 с выбором оптимизированных под конкретный процессор процедур в рантайме) залил на http://diamond.kolibrios.org/prg/factorial.7z (плюс просто .../factorial.exe для не любящих архивы), желающие могут сравнить самостоятельно.

 

diamond
Спасибо за науку и за исполняемые файлы!
К быстродействию пакета GMP следует относится спокойно, первые версии SuperFac оставляют большой простор для алгоритмической оптимизации, это несомненно. Главное, что в этой гонке программа доходит до финиша и не теряет колес по дороге. На очереди извлечение пользы от факторизации факториала, как это ни забавно звучит.

Но не все так плохо, на c2d SuperFac юзает два ядра. Скорее даже хорошо для такого наивного (нативного) алгоритма, который там сейчас.

16 млн.! GMP 8:30, SuperFac 13:30
32 млн.! GMP 20:50, SuperFac 29:21

Как всегда, возникает вопрос, понижает ли SuperFac вселенскую энтропию, производя полезные расчеты, или повышает, поскольку есть другие более эффективные и быстрые средства? Тут надо исходить из того, что прежде всего понижается энтропия в голове автора, поскольку он узнал уже много нового и интересного и узнает еще.

Прога обновилась до версии 0.2
1) Входная планка приподнята до 100 млн. Это достигнуто снапшотом оперативы на винт.
2) Реализован априорный и апостериорный подсчет trailing zeros, спасибо форуму и его обитателям.

 

Называется Polignac's formula и есть в Вики =)))

 

Ну что, кто нить считал 2^27!, самое большое входное число, которое позволяет SuperFac v0.2?

Какая цифра там повторяется 10 раз подряд кроме нулей в конце?
Так я узнаю, ктонить сподобился ли еще на такой подвиг.

 

а (2^(27) - 1)! тоже повторяется?