Обсуждение:Тест Люка — Лемера (KQvr';yuny&Myvm LZtg — Lybyjg)
Проект «Математика» (уровень ХС)
Эта статья тематически связана с вики-проектом «Математика», цель которого — создание и улучшение статей по темам, связанным с математикой. Вы можете её отредактировать, а также присоединиться к проекту, принять участие в его обсуждении и поработать над требуемыми статьями. |
![]() ![]() | Эта статья была признана добротной статьёй русской Википедии. См. страницу номинации (статус присвоен 22 декабря 2016 года). Позднее получила статус хорошей. |
![]() | Эта статья входит в число хороших статей русской Википедии. См. страницу номинации (статус присвоен 10 февраля 2017 года). |
Вопрос: для данный тест не работает (). На основании чего получено простое число Мерсенна ? Dark Magus 05:58, 10 апреля 2006 (UTC)
- Добавил условие . Maxal 13:33, 16 декабря 2009 (UTC)
Нужно переименовать в Т л.-л. для чисел мерсенна, поскольку существует более общий вариант этого теста: en:Lucas–Lehmer test `a5b 09:59, 12 июня 2006 (UTC)
- Когда будет статья об общем варианте теста — тогда и переименуем. Maxal 13:33, 16 декабря 2009 (UTC)
- Пожалуй уже можно переименовать :-) Статья об общем варианте теста уже есть. Sonic86 09:18, 13 января 2012 (UTC)Sonic86
- Но общий вариант называет тестом Люка, так что разночтений здесь нет. Maxal 14:01, 13 января 2012 (UTC)
Циклический сдвиг
[править код]- причём умножение на 2 k {\displaystyle 2^{k}} 2^k по модулю M p {\displaystyle M_{p}} M_{p} равносильно левому циклическому сдвигу на k {\displaystyle k} k бит
В АИ явная опечатка. Почитайте где угодно (хотя бы тут), умножение на 2^k эквивалентно ОБЫЧНОМУ сдвигу на k бит, а не циклическому (соответственно, деление — сдвигу вправо). Что, кстати, подтверждается и самим АИ, т.к дальше (512 страница) приводится алгоритм 9.2.13, где используется самый обычный сдвиг вправо. Алгоритм прошу не удалять, он взят из АИ (только там он приведен в общем виде, для чисел вида 2^n+c, в случае чисел Мерсена c=-1) 212.73.99.89 05:46, 18 сентября 2019 (UTC)
- Вы апеллируете к АИ, соответственно, сперва следует опровергнуть утверждение из АИ, после чего вносить правки. Ссылка на другую статью из Википедии, равно как и рекомендация «почитать где угодно», не может являться опровержением чего-либо. Указание на алгоритм 9.2.13 также не является опровержением корректности формулировки теоремы, поскольку в нем не используется вторая часть теоремы (в явном виде). Опровержением может быть, например, ссылка на другие АИ. А пока настоятельно рекомендую отменить свою последнюю правку, которая является прямым нарушением ВП:ПТО и ВП:ВПР. Derise (обс.) 11:18, 18 сентября 2019 (UTC)
- Видите ли, то что умножение-деление на степень двойки n эквивалентно сдвигам на n бит — настолько очевидный факт для любого программиста (и вообще любого знакомого с двоичной системой счисления), что мне и в голову не пришло это доказывать, это как доказывать что 2*2=4. Но если вам нужна ссылка, то [вот] пожалуйста. "Указание на алгоритм 9.2.13 также не является опровержением корректности формулировки теоремы, поскольку в нем не используется вторая часть теоремы (в явном виде)." — теорема заключается в том, что деление по модулю на 2^n-1 можно заменить указанной суммой. Второе утверждение это уже не теорема, а пояснение, чем именно полезно такое разложение — а полезно оно тем, что обе части можно вычислить быстрыми битовыми операциями. В принципе, согласен, что эту расшифровку лучше вынести из самой теоремы, т.к. она относится уже не столько к теореме сколько к реализации алгоритма на компьютере. 212.73.99.89 05:34, 19 сентября 2019 (UTC)
- Желательно, конечно, ссылаться на сам источник, а не на его перепечатку на каком-то сайте (собственно, вверху статьи эта ссылка и указана). В любом случае, содержание приведенной статьи не имеет никакого отношения к обсуждаемому вопросу. Вам нужно, ссылаясь на АИ, опровергнуть ту часть теоремы, с формулировкой которой вы не согласны. Derise (обс.) 07:39, 19 сентября 2019 (UTC)
- Видите ли, то что умножение-деление на степень двойки n эквивалентно сдвигам на n бит — настолько очевидный факт для любого программиста (и вообще любого знакомого с двоичной системой счисления), что мне и в голову не пришло это доказывать, это как доказывать что 2*2=4. Но если вам нужна ссылка, то [вот] пожалуйста. "Указание на алгоритм 9.2.13 также не является опровержением корректности формулировки теоремы, поскольку в нем не используется вторая часть теоремы (в явном виде)." — теорема заключается в том, что деление по модулю на 2^n-1 можно заменить указанной суммой. Второе утверждение это уже не теорема, а пояснение, чем именно полезно такое разложение — а полезно оно тем, что обе части можно вычислить быстрыми битовыми операциями. В принципе, согласен, что эту расшифровку лучше вынести из самой теоремы, т.к. она относится уже не столько к теореме сколько к реализации алгоритма на компьютере. 212.73.99.89 05:34, 19 сентября 2019 (UTC)
- В АИ не опечатка. При подсчёте остатка по модулю вида умножение на действительно эквивалентно циклическому сдвигу. adamant (обс./вклад) 21:05, 3 октября 2019 (UTC)