Вопрос по тесту Миллера Рабина

[wcl.AleX]

Здравствуйте уважаемые участники форума
Недавно написал программу , основанную на псевдокоде в википедии
http://ru.wikipedia.org/wiki/Тест_Миллера_—_Рабина
Столкнулся с некоторыми сложностями. После 45000 программа начинает многие Простые числа считать составными.
Сначала я думал, что не правильно написал код программы, но потом решил взять в руки ручку выполнить все операции вручную на бумаге, для одного из простых чисел , которые программа считает составным. Самая большая странность заключается в том, что исходя из псевдокода, написанного в википедии , это простое число должно быть составным.
Вот что у меня получилось .
Число 47057 m-1 равно 47056 s равно 4 t равно 2941
Так если взять случайное число А равное 3 то программа завалит тест на простоту
3 в степени 2941 мод 47057 равно 46552
Возводя последнее число в квадрат и взяв остаток от деления даже НАМНОГО больше чем 3 раза(s-1) , я никак не получал число 47056.
Либо я неправильно понял псевдокод, либо он неправильно написан. Может кто-то сталкивался с подобной проблемой. Дело в том, что если взять число больше 100000 то очень большое колличество простых у меня отсеивается.
Заранее благодарен за ответ.

[Xaositect]

wcl.AleX в сообщении #734465 писал(а):

Возводя последнее число в квадрат и взяв остаток от деления даже НАМНОГО больше чем 3 раза(s-1) , я никак не получал число 47056.

У меня получилось как раз на третий раз.

Prelude> 3^2941 `mod` 47057
46552
Prelude> it^2 `mod` 47057
19740
Prelude> it^2 `mod` 47057
35640
Prelude> it^2 `mod` 47057
47056

[venco]

У вас переполнение int. Максимальное возможное значение - $2^{31}-1$, корень из него - $46340$. Большие числа надо считать в 64 битах или больше.

[Deggial]

Тема перемещена из форума «Дискуссионные темы (М)» в форум «Программирование»
Перенёс в более соответствующий раздел

[wcl.AleX]

У меня есть программа, нужно улучшить, можете помочь?
http://rghost.ru/46663071

[arseniiv]

Главное же вот в чём:

venco в сообщении #734529 писал(а):

Большие числа надо считать в 64 битах или больше.

Используйте long, или как там 64-разрядный тип называется в C++. Для чисел больше и больше вам нужна будет арифметика многократной точности. Впрочем, о ней вам, кажется, уже писали.

Небольшое ускорение может дать замена x % 2 на x & 1.

[wcl.AleX]

Используйте long, или как там 64-разрядный тип называется в C++. Для чисел больше и больше вам нужна будет арифметика многократной точности. Впрочем, о ней вам, кажется, уже писали.
можно об этом поподробнее, хоть небольшой примерчик
Небольшое ускорение может дать замена x % 2 на x & 1.
это только на %2 или можно как-то на другие числа тоже? Например, как будет выглядеть x%y?

[arseniiv]

wcl.AleX в сообщении #735603 писал(а):

это только на %2 или можно как-то на другие числа тоже? Например, как будет выглядеть x%y?

Посмотрите на двоичные записи чисел, дающих одинаковые остатки по конкретному модулю и решите сами, как изменится производительность.

wcl.AleX в сообщении #735603 писал(а):

можно об этом поподробнее, хоть небольшой примерчик

О чём конкретно подробнее?

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

[Zealint]

arseniiv в сообщении #735585 писал(а):

Небольшое ускорение может дать замена x % 2 на x & 1.

Мне кажется, что современные компиляторы уже стали чуть-чуть умнее тех, что были 15 лет назад. Не должно это ничего ускорить.

[arseniiv]

Так потому я и написал «может дать», а не «даст».

[Zealint]

Так в том-то и дело, что скорее всего не может. Вы только дали человеку надежду, что можно любой остаток заменить таким универсальным хитрым трюком. Так рождаются мифы : )

Разговаривать про оптимизацию нужно с тем человеком, который хоть примерно представляет себе работу компьютера. В противном случае ваши советы для него будут как библейская догма. Единственный совет, который тут уместно дать wcl.AleX - пойти учиться программировать, решить пару сотен классических упражнений и только после этого начинать разговоры про сложные вещи. Всё остальное я считаю, будет во вред его целям.

[arseniiv]

Zealint в сообщении #736048 писал(а):

Вы только дали человеку надежду, что можно любой остаток заменить таким универсальным хитрым трюком.

Нет, надежду он дал себе сам. Никто ж не мешает захотеть разобраться (в том, что можно сделать с остатками) и разобраться.

Zealint в сообщении #736048 писал(а):

В противном случае ваши советы для него будут как библейская догма.

Если бы я собирался советовать что-то посерьёзнее насчёт программы в архиве с названием «Лучший алгоритм миллера рабина»! Можете не опасаться за wcl.AleX.

[Zealint]

(Я понял, что происходит.)

arseniiv в сообщении #736055 писал(а):

Если бы я собирался советовать что-то посерьёзнее насчёт программы в архиве с названием «Лучший алгоритм миллера рабина»! Можете не опасаться за wcl.AleX.

Я долго пытался вспомнить, что же мне напоминает наше общение с автором темы. И ваш ответ наконец помог это сделать. Вот что (первый пост). Нашёл через Лурк, когда пытался разобраться с тем, кто такие программисты, но попал немного не на ту страничку.

По ссылке писал(а):

привет я чайник. я на бейсике програмировать начал давайте зделаем игру все вместе
чтоб она была онлайн наподобе варкрафта. Только круче. Я такие игру програмировать не умею поэтому прошу вашей помощи мы обеденим усилия и сделаем игру под моим руководством.Это круто будет. когда игра будет распространена по свету там будут ваши имена и мое имя руководителя. а еще можно зделать крутую гонку но это уже потом или типа контер страйка вобще можно тысячу игр вместе зделать

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