факториал

Тема в разделе "WASM.PROJECTS", создана пользователем persicum, 27 апр 2010.

  1. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Начинаю проект по вычислению длинного факториала (!)
    Поскоку тема 2007 сдохла, буду писать здесь.
    Баловался этим в школе... Тогда считал по основанию 10^9.
    Позднее стал несколько опытнее, сейчас хотел было считать в HEX, чтобы не делить на степеня десятки, но столкнулся с проблемой перевода конечного результата в DEC. Этож жуть сколько вычислений придется делать для перевода из одной системы в другую!

    Факториал планируется подписывать сигнатурой, вычисляемой как из полученного фака, так и независимо, что весьма и весьма ценно!

    Возможно, факториал так бы не приколол меня, если бы не возможность получать его несколько первых и последних цифр НЕЗАВИСИМО, что позволит потом делать верификацию.

    В подходящей системе счисления можно добиться, чтобы последние цифры были не тривиальными нулями, а своего рода цифровой сигнатурой.

    Вопщем, я начинаю свою прогу, а вы постите сюда свои проги и сырцы.
     
  2. nds

    nds Member

    Публикаций:
    0
    Регистрация:
    16 июл 2007
    Сообщения:
    157
    1 независимо от системы счисления (ели она позиционная и содержит 0) начиная с определенного числа факториал всегда заканчивается на 0
    2 для чего нужно факториал подписывать если не секрет?
     
  3. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Как же без подписи то? Подпись нужна для того, для чего нужна любая контрольная сумма, а именно с высокой вероятностью подтвердить оригинальность документа не имея полнообъемного дубликата.

    Если для N! взять простое р>N то остаток будет не нулем. Это то же самое, что в системе с основанием р последняя цифра будет не ноль.
     
  4. Rockphorr

    Rockphorr Well-Known Member

    Публикаций:
    0
    Регистрация:
    9 июн 2004
    Сообщения:
    2.615
    Адрес:
    Russia
    persicum

    но по условию в связи с тем что N велико брать систему счисления с P>N не удобно - цифирей слишком много получается
     
  5. Rel

    Rel Well-Known Member

    Публикаций:
    2
    Регистрация:
    11 дек 2008
    Сообщения:
    5.242
    реализовать длинные числа, как число в 256-ричной системе счисления (каждый разряд такого числа представляется одним байтом)... все операции реализовывать поразрядно, включая перевод в разные системы счисления...
     
  6. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Rel
    универсальный подход загнется уже при 30000!.
    Достаточно взять калькулятор Виндос и посмотреть.

    Мне интересно написать прогу, которая считала бы очень большие факториалы.
     
  7. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Rockphorr
    Ну N планируется брать одинарной точности, скажем тыщща или лимон.
    Алгоритма для вычисления факториала от чисел криптографического размера не существует, иначе можно было мгновенно на множители раскладывать.
     
  8. Rel

    Rel Well-Known Member

    Публикаций:
    2
    Регистрация:
    11 дек 2008
    Сообщения:
    5.242
    почему он должен загнуться?... у тебя бесконечное число разрядов по 256 значений каждый... единственный косяк в том, что поразрядная арифметика при больших значениях займет больше времени, и канеш о рекурсии даже говорить не стоит, только циклом... приводить к разным системам счисления поразрядно будет довольно просто... я так вычислял миллионный член последовательности Фибоначчи на первом курсе института на спор с преподавателем программирования)))
     
  9. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Rel
    все как раз наоборот, рекурсия рулит, я делаю рекурсивный алгоритм чемто похожий на быструю сортировку. Хехе, это как раз в цикле запаришься вычислять...
    Воспщем, прога в основном уже готова, осталось добавить сброс анналов в текстовый файл.
     
  10. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    hxxp://file.qip.ru/file/127606882/a5ec9865/SuperFac.html

    Выкладываю первую рабочую версию.
    Считает до 50000000!, дальше просит 3.2G RAMa, чего я ей дать не могу при всем желании...
    Есть идея в перспективе добавить подсчет нулей в конце, эт тоже можно сделать не прибегая к длинным вычислениям. Видимо, просто посчитать сколько пар 2 и 5 встречается.
    Опыт показывает, что нулей там 4% в хвосте для больших чисел.

    Еще есть праймориалы, и самое прикольное вроде для них тоже сушествует что-то наподобие формулы Стирлинга!
    (аппроксимации функции Чебышева 1 рода).
     
  11. ijon_tichy

    ijon_tichy New Member

    Публикаций:
    0
    Регистрация:
    23 фев 2010
    Сообщения:
    17
    подсчет нулей в конце
    Код (Text):
    1. int alpha(int p, int n)
    2. {
    3. if (n <= p) return 0;
    4. else {
    5. int c = div(n, p).quot;
    6. return c + alpha(p, c);
    7. }
    alpha(5, n) - число нулей
     
  12. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    ijon_tichy
    Эт чего, логарифм по основанию 5? попробую.

    А ты попробуй еще получить 8 последних цифр, что идут сразу перед нулями.
    Будет тогда с чем обновлять прогу помимо исправления написания фамилии Стирлинга =(((
     
  13. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    ijon_tichy
    Ну понятное дело, это и без рекурсии легко программируется в цикле, но вопрос не в этом.
    Как это у тебя так лихо получилось? Цепные дроби замаскированные? Ей бо не пойму, как оно работает.
    Возьмет к примеру 100.
    100/5=20
    20/5=4
    И того 100! имеет 24 нуля на конце.
     
  14. ijon_tichy

    ijon_tichy New Member

    Публикаций:
    0
    Регистрация:
    23 фев 2010
    Сообщения:
    17
    Это поиск степени простого 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 чисел перед нулями. Там очень быстро можно считать, если по модулю.
     
  15. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Да не, у меня простейший, пополам, потом еще пополам и так далее.
    О карацубе представление имею, но там память вроде нужна для промежуточных переменных... Пока не прикидывал.
    Вроде делить на четыре части, а умножать три из них. В анлисской Вики куча серьезнейших ссылок на статьи по этой теме, самые крутые алгосы действительно используют простые числа. И зачем такое баловство кому-то нужно?

    пока не знаю, как это поможет, зная степень простого числа можно его в степень возвести быстро? Но результат будет длинный... Жду с нетерпением Карацубу с простыми числами!!!
     
  16. diamond

    diamond New Member

    Публикаций:
    0
    Регистрация:
    21 май 2004
    Сообщения:
    507
    Адрес:
    Russia
    Не надо изобретать велосипед. В GMP уже есть функция вычисления факториала, и она неплохо работает.
    Код (Text):
    1. #include <stdio.h>
    2. #include <stdlib.h>
    3. #include <gmp.h>
    4.  
    5. int main(int argc, char* argv[])
    6. {
    7.     if (argc != 2) {
    8.         printf("Usage: %s <number>\n", argv[0]);
    9.         return 1;
    10.     }
    11.     mpz_t result;
    12.     mpz_init(result);
    13.     mpz_fac_ui(result, strtoul(argv[1]));
    14.     gmp_printf("Factorial is %Zd\n", result);
    15.     mpz_clear(result);
    16. }
    Полностью печатает факториал в десятичной системе. У меня при вычислении 1000000! работает примерно 12 секунд, в то время как SuperFac.exe - около 45 секунд.

    Алгоритм, кстати, описан в руководстве по GMP, http://gmplib.org/gmp-man-5.0.1.pdf (раздел 16.7.2).
     
  17. diamond

    diamond New Member

    Публикаций:
    0
    Регистрация:
    21 май 2004
    Сообщения:
    507
    Адрес:
    Russia
    Да, и процент нулей в конце десятичной записи 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.
     
  18. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Мы тут просто развлекаемся.

    Не надо вообще с C++ связываться, факториал есть в какой нить приятной среде Математика-Мэпл.

    У меня новая версия будет считать и от 100 млн. GMP не загнется?
     
  19. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Почитал. Это карацуба с простыми числами, над чем как раз ijon_tichy работает сейчас.
    А для 10 млн. можно сравнить быстродействие с SuperFac?
     
  20. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Задача не заменить GMP и не обогнать, а написать самому и не ошибиться =)))
    Приятная головоломка.