Комментарии 8
(97! mod (2 ** 256 - 2 ** 32 - 977)) в двоичном виде 1110101100010111000101111101011111011000010100111011111110100010100110010111011011000101110110110100111011010101000100000101010111001000110000010001101001111001111100011110101011100001111110101011110111111000101100001111011111001110101000100101111001100101000000000101110110101011000010011010101011001111100011010111111100111010011000000001110111100101100001110000110000001100011000110001110111100100101110101110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000, что дает 506 бит, что не около 500.
Хотя в целом идея для степеней двойки разобрана в большом количестве учебников, но на других языках программирования.
506 отличается от 500 всего на 1,2 %, так что вполне себе около. :)
Но только не в двоичной системе счисления.
2^506-2^500=206223608297456937810830950900138746589648448900713081737447356190056429173494496957646015816531961900505861100036284473580687162390779762359697238130688, что как раз и дает 1% погрешности :)).
Если мы говорим о числах, представимых с помощью 506 и 500 бит, то она большая, но это не значит, что 506 и 500 сильно отличаются.
Не очень понял, почему вы вычитаете одно из другого. Тут уместнее деление. Правда, разница в 6 двоичных порядков уже не так смотрится, как ворох цифр. :)
Ну хорошо, давайте делить. (2^506)/(2^500)=2^6=64 раза. То есть автор статьи ошибся в 64 раза в своем утверждении о битности. В жизни, допустим, вам никогда сдачу в магазине в 64 раза не уменьшали?
И что? Цель — передать порядок числа, показать, что оно очень большое. Точное значение никакого интереса не представляет и на дальнейшие рассуждения никак не влияет.
Заметьте, что речь идёт о порядке, а не о значении. Это разные вещи. Так что ошибка именно около процента, а не в 64 раза.
Аналогия со сдачей неуместна, так как там как раз нужна точность.
Да, спасибо. Вот тут есть хорошее объяснение этого метода: https://codeforces.com/blog/entry/103374
Ну и про метод Барретта стоит упомянуть: https://en.wikipedia.org/wiki/Barrett_reduction
Быстрое нахождениe остатка от деления больших чисел для делителей специального вида