Начинаю проект по вычислению длинного факториала (!) Поскоку тема 2007 сдохла, буду писать здесь. Баловался этим в школе... Тогда считал по основанию 10^9. Позднее стал несколько опытнее, сейчас хотел было считать в HEX, чтобы не делить на степеня десятки, но столкнулся с проблемой перевода конечного результата в DEC. Этож жуть сколько вычислений придется делать для перевода из одной системы в другую! Факториал планируется подписывать сигнатурой, вычисляемой как из полученного фака, так и независимо, что весьма и весьма ценно! Возможно, факториал так бы не приколол меня, если бы не возможность получать его несколько первых и последних цифр НЕЗАВИСИМО, что позволит потом делать верификацию. В подходящей системе счисления можно добиться, чтобы последние цифры были не тривиальными нулями, а своего рода цифровой сигнатурой. Вопщем, я начинаю свою прогу, а вы постите сюда свои проги и сырцы.
1 независимо от системы счисления (ели она позиционная и содержит 0) начиная с определенного числа факториал всегда заканчивается на 0 2 для чего нужно факториал подписывать если не секрет?
Как же без подписи то? Подпись нужна для того, для чего нужна любая контрольная сумма, а именно с высокой вероятностью подтвердить оригинальность документа не имея полнообъемного дубликата. Если для N! взять простое р>N то остаток будет не нулем. Это то же самое, что в системе с основанием р последняя цифра будет не ноль.
persicum но по условию в связи с тем что N велико брать систему счисления с P>N не удобно - цифирей слишком много получается
реализовать длинные числа, как число в 256-ричной системе счисления (каждый разряд такого числа представляется одним байтом)... все операции реализовывать поразрядно, включая перевод в разные системы счисления...
Rel универсальный подход загнется уже при 30000!. Достаточно взять калькулятор Виндос и посмотреть. Мне интересно написать прогу, которая считала бы очень большие факториалы.
Rockphorr Ну N планируется брать одинарной точности, скажем тыщща или лимон. Алгоритма для вычисления факториала от чисел криптографического размера не существует, иначе можно было мгновенно на множители раскладывать.
почему он должен загнуться?... у тебя бесконечное число разрядов по 256 значений каждый... единственный косяк в том, что поразрядная арифметика при больших значениях займет больше времени, и канеш о рекурсии даже говорить не стоит, только циклом... приводить к разным системам счисления поразрядно будет довольно просто... я так вычислял миллионный член последовательности Фибоначчи на первом курсе института на спор с преподавателем программирования)))
Rel все как раз наоборот, рекурсия рулит, я делаю рекурсивный алгоритм чемто похожий на быструю сортировку. Хехе, это как раз в цикле запаришься вычислять... Воспщем, прога в основном уже готова, осталось добавить сброс анналов в текстовый файл.
hxxp://file.qip.ru/file/127606882/a5ec9865/SuperFac.html Выкладываю первую рабочую версию. Считает до 50000000!, дальше просит 3.2G RAMa, чего я ей дать не могу при всем желании... Есть идея в перспективе добавить подсчет нулей в конце, эт тоже можно сделать не прибегая к длинным вычислениям. Видимо, просто посчитать сколько пар 2 и 5 встречается. Опыт показывает, что нулей там 4% в хвосте для больших чисел. Еще есть праймориалы, и самое прикольное вроде для них тоже сушествует что-то наподобие формулы Стирлинга! (аппроксимации функции Чебышева 1 рода).
подсчет нулей в конце Code (Text): int alpha(int p, int n) { if (n <= p) return 0; else { int c = div(n, p).quot; return c + alpha(p, c); } alpha(5, n) - число нулей
ijon_tichy Эт чего, логарифм по основанию 5? попробую. А ты попробуй еще получить 8 последних цифр, что идут сразу перед нулями. Будет тогда с чем обновлять прогу помимо исправления написания фамилии Стирлинга =(((
ijon_tichy Ну понятное дело, это и без рекурсии легко программируется в цикле, но вопрос не в этом. Как это у тебя так лихо получилось? Цепные дроби замаскированные? Ей бо не пойму, как оно работает. Возьмет к примеру 100. 100/5=20 20/5=4 И того 100! имеет 24 нуля на конце.
Это поиск степени простого p в разложении факториала на простые множители. У тебя, конечно, алгоритм мегакрутой. Респект. Возникла мысль попробовать самому, но несколько другим путем. 1) факторизирую факториал 2) ищу степени простых быстрым способам 3) перемножаю все, для всех умножений метод Карацубы Факторизация готова, для миллиона на недобуке считается за 0.2 секунды. Для десяти 2.4 секунды. Причем большую часть времени занимает как раз поиск простых. Потом для них считается функция alpha. Алгоритм функции придумал как раз глядя на поиск простых: когда прохожу по списку чисел - двойка встречается n/2 раз. Четверка - n/4 раз. И так далее по степеням двойки. Допустим n = 11, p = 2. Множители 11! : 1 2 3 2*2 5 2*3 7 2*2*2 3*3 2*5 Получается что-то типа пирамидки для степеней двойки 2 2 2 2 2 4 4 8 Четверки встречаются среди двоек, восьмерки среди четверок и так далее. Т.е. представь последовательность чисел кратных 2. Выносим общий множитель. Первый вызов функции - посчитали двойки, второй - четверки и т. д. Количество нулей в факториале определяется степенью пятерки в его разложении. Как напишу свой вариант, напишу вычисление k чисел перед нулями. Там очень быстро можно считать, если по модулю.
Да не, у меня простейший, пополам, потом еще пополам и так далее. О карацубе представление имею, но там память вроде нужна для промежуточных переменных... Пока не прикидывал. Вроде делить на четыре части, а умножать три из них. В анлисской Вики куча серьезнейших ссылок на статьи по этой теме, самые крутые алгосы действительно используют простые числа. И зачем такое баловство кому-то нужно? пока не знаю, как это поможет, зная степень простого числа можно его в степень возвести быстро? Но результат будет длинный... Жду с нетерпением Карацубу с простыми числами!!!
Не надо изобретать велосипед. В GMP уже есть функция вычисления факториала, и она неплохо работает. Code (Text): #include <stdio.h> #include <stdlib.h> #include <gmp.h> int main(int argc, char* argv[]) { if (argc != 2) { printf("Usage: %s <number>\n", argv[0]); return 1; } mpz_t result; mpz_init(result); mpz_fac_ui(result, strtoul(argv[1])); gmp_printf("Factorial is %Zd\n", result); mpz_clear(result); } Полностью печатает факториал в десятичной системе. У меня при вычислении 1000000! работает примерно 12 секунд, в то время как SuperFac.exe - около 45 секунд. Алгоритм, кстати, описан в руководстве по GMP, http://gmplib.org/gmp-man-5.0.1.pdf (раздел 16.7.2).
Да, и процент нулей в конце десятичной записи n! с ростом n убывает как O(1/ln(n)), точнее, примерно равен ln(10)/4/(ln(n)-1). Например, в случае 123456! точное значение 30860/574965, что примерно равно 0.053673, а ln(10)/4/(ln(123456)-1) = 0.053680.
Мы тут просто развлекаемся. Не надо вообще с C++ связываться, факториал есть в какой нить приятной среде Математика-Мэпл. У меня новая версия будет считать и от 100 млн. GMP не загнется?
Почитал. Это карацуба с простыми числами, над чем как раз ijon_tichy работает сейчас. А для 10 млн. можно сравнить быстродействие с SuperFac?
