2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Вопрос по тесту Миллера Рабина
Сообщение08.06.2013, 20:52 


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

 Профиль  
                  
 
 Re: Вопрос по тесту Миллера Рабина
Сообщение08.06.2013, 21:00 
Заслуженный участник
Аватара пользователя


06/10/08
6422
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

 Профиль  
                  
 
 Re: Вопрос по тесту Миллера Рабина
Сообщение09.06.2013, 01:17 
Заслуженный участник


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

 Профиль  
                  
 
 Posted automatically
Сообщение09.06.2013, 07:48 
Супермодератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: Вопрос по тесту Миллера Рабина
Сообщение10.06.2013, 22:44 


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

 Профиль  
                  
 
 Re: Вопрос по тесту Миллера Рабина
Сообщение11.06.2013, 23:06 
Заслуженный участник


27/04/09
28128
Главное же вот в чём:
venco в сообщении #734529 писал(а):
Большие числа надо считать в 64 битах или больше.

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

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

 Профиль  
                  
 
 Re: Вопрос по тесту Миллера Рабина
Сообщение11.06.2013, 23:44 


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

 Профиль  
                  
 
 Re: Вопрос по тесту Миллера Рабина
Сообщение11.06.2013, 23:58 
Заслуженный участник


27/04/09
28128
wcl.AleX в сообщении #735603 писал(а):
это только на %2 или можно как-то на другие числа тоже? Например, как будет выглядеть x%y?
Посмотрите на двоичные записи чисел, дающих одинаковые остатки по конкретному модулю и решите сами, как изменится производительность.

wcl.AleX в сообщении #735603 писал(а):
можно об этом поподробнее, хоть небольшой примерчик
О чём конкретно подробнее?

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

 Профиль  
                  
 
 Re: Вопрос по тесту Миллера Рабина
Сообщение12.06.2013, 08:11 


26/01/10
959
arseniiv в сообщении #735585 писал(а):
Небольшое ускорение может дать замена x % 2 на x & 1.

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

 Профиль  
                  
 
 Re: Вопрос по тесту Миллера Рабина
Сообщение12.06.2013, 14:49 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Вопрос по тесту Миллера Рабина
Сообщение12.06.2013, 21:10 


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

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

 Профиль  
                  
 
 Re: Вопрос по тесту Миллера Рабина
Сообщение12.06.2013, 21:27 
Заслуженный участник


27/04/09
28128
Zealint в сообщении #736048 писал(а):
Вы только дали человеку надежду, что можно любой остаток заменить таким универсальным хитрым трюком.
Нет, надежду он дал себе сам. :-) Никто ж не мешает захотеть разобраться (в том, что можно сделать с остатками) и разобраться.

Zealint в сообщении #736048 писал(а):
В противном случае ваши советы для него будут как библейская догма.
Если бы я собирался советовать что-то посерьёзнее насчёт программы в архиве с названием «Лучший алгоритм миллера рабина»! :lol: Можете не опасаться за wcl.AleX.

 Профиль  
                  
 
 Re: Вопрос по тесту Миллера Рабина
Сообщение14.06.2013, 06:51 


26/01/10
959

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

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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group