Форум программистов, компьютерный форум CyberForum.ru

тест миллера-рабина, pascal -> c++ - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 64, средняя оценка - 4.89
amiserio
1 / 1 / 0
Регистрация: 18.10.2008
Сообщений: 11
28.03.2009, 16:14     тест миллера-рабина, pascal -> c++ #1
собсно, кто знает дельфи и с++, обьясните где я не прав пожалуйста=)
дельфи:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
{IsPrime.Pas ver. 2.0 (c) Max Alekseyev <relf@os2.ru>, 2:5015/60@FidoNet}
{Реализация вероятностного алгоритма Миллера-Рабина с 20 раундами.
Для примера выдает простые на отрезке [1000000000,1000100000].
Вероятность ошибки (то, что составное число будет названо простым) меньше
4^(-Rounds).}
 
const Rounds=20;
 
function mulmod(x,y,m:longint):longint; assembler;
asm
{$IFDEF USE32}
  mov eax,x
  mul y
  div m
  mov eax,edx
{$ELSE}
  db $66; mov ax,word ptr x
  db $66; mul word ptr y
  db $66; div word ptr m
  mov ax,dx
  db $66; shr dx,16
{$ENDIF}
end;
 
function powmod(x,a,m:longint):longint;
var r:longint;
begin
  r:=1;
  while a>0 do
  begin
    if odd(a) then r:=mulmod(r,x,m);
    a:=a shr 1;
    x:=mulmod(x,x,m);
  end;
  powmod:=r;
end;
 
function isprime(p:longint):boolean;
var q,i,a:longint;
begin
if odd(p) and (p>1) then
begin
  isprime:=true;
  q:=p-1;
  repeat q:=q shr 1; until odd(q);
  for i:=1 to Rounds do
  begin
    {$IFDEF USE32}
     a:=Random(p-2)+2; {$ELSE} a:=2+Trunc(Random*(p-2)); {$ENDIF}
    if powmod(a,p-1,p)<>1 then
    begin
      isprime:=false; break;
    end;
    a:=powmod(a,q,p);
    if a<>1 then
    begin
      while (a<>1) and (a<>p-1) do a:=mulmod(a,a,p);
      if a=1 then
      begin
        isprime:=false; break;
      end;
    end;
  end;
end else isprime:=(p=2);
end;
 
var t:longint;
begin
  Randomize; {Don't forget to reset Random Generator!}
  for t:=1000000000 to 1000100000 do if isprime(t) then writeln(t);end.
с++, где large - всеравно что unsigned int:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
int rounds=20;
large mulmod(large x,large y,large m)
{
    return (x*y)%m;
}
large powmod(large x,large a,large m)
{
    large r=1;
    while(a>0)
    {
        if(a%2==0) 
           r=mulmod(r,x,m);
        a=a>>1; 
        x=mulmod(x,x,m);
    }
    return r;
}
 
bool isprime(large p)
{
    large q,a;
    int i;
    cl_randex rand;
    rand.set_max("100000000000"); // макс число для генератора сл. чисел
    if(p%2==0 && p>1)
    {
         q=p-1;
         do q=q>>1; while(q%2==0);
         for(i=1; i<rounds; i++)
         {
               a=rand.lgen(p-2)+2; //rand.lgen - генератор сл. чисел
               if(powmod(a,p-1,p)!=1)
               {
                     return false;
                     break;
               }
               a=powmod(a,q,p);
               if(a!=1)
               {
                    while(a!=1 && a!=p-1) a=mulmod(a,a,p);
                    if(a==1)
                    {
                       return false;
                       break;
                    }
               }
          }
          return true;
    }
    else
     return false;
}
 
int _tmain()
{
  large t;
  for(t="1000000000";t<"1000100000";t+="1")
  {
      if(isprime(t))
         cout<<"t="<<t<<endl;
  }
  system("pause");
  return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Humanitis
 Аватар для Humanitis
170 / 162 / 5
Регистрация: 12.01.2009
Сообщений: 430
28.03.2009, 19:36     тест миллера-рабина, pascal -> c++ #2
Цитата Сообщение от amiserio Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
int rounds=20;
large mulmod(large x,large y,large m)
{
    return (x*y)%m;
}
large powmod(large x,large a,large m)
{
    large r=1;
    while(a>0)
    {
        if(a%2==0) 
           r=mulmod(r,x,m);
        a=a>>1; 
        x=mulmod(x,x,m);
    }
    return r;
}
 
bool isprime(large p)
{
    large q,a;
    int i;
    cl_randex rand;
    rand.set_max("100000000000"); // макс число для генератора сл. чисел
    if(p%2==0 && p>1)
    {
         q=p-1;
         do q=q>>1; while(q%2==0);
         for(i=1; i<rounds; i++)//i<=rounds
         {
               a=rand.lgen(p-2)+2; //rand.lgen - генератор сл. чисел
               if(powmod(a,p-1,p)!=1)
               {
                     return false;
                     break;//break не нужен
               }
               a=powmod(a,q,p);
               if(a!=1)
               {
                    while(a!=1 && a!=p-1) a=mulmod(a,a,p);
                    if(a==1)
                    {
                       return false;
                       break;//break не нужен
                    }
               }
          }
          return true;
    }
    else
     return false;//return t==2
}
 
int _tmain()
{
  large t;
  for(t="1000000000";t<"1000100000";t+="1")
  {
      if(isprime(t))
         cout<<"t="<<t<<endl;
  }
  system("pause");
  return 0;
}
вроде все остальное правильно.
А что не так собстно?
amiserio
1 / 1 / 0
Регистрация: 18.10.2008
Сообщений: 11
28.03.2009, 19:39  [ТС]     тест миллера-рабина, pascal -> c++ #3
function isprime(p:longint):boolean;
вызвала затруднения, я не понял что делает строка:
Pascal
1
end else isprime:=(p=2)
C++
1
return false;//return t==2
тоже не понял о_О что она должна вернуть?
Humanitis
 Аватар для Humanitis
170 / 162 / 5
Регистрация: 12.01.2009
Сообщений: 430
28.03.2009, 19:43     тест миллера-рабина, pascal -> c++ #4
return t==2 -должна вернуть истину если проверяемое число равно 2,т.е. простое число.
И ложь в обратном случае.
amiserio
1 / 1 / 0
Регистрация: 18.10.2008
Сообщений: 11
28.03.2009, 20:42  [ТС]     тест миллера-рабина, pascal -> c++ #5
Цитата Сообщение от Humanitis Посмотреть сообщение
return t==2 -должна вернуть истину если проверяемое число равно 2,т.е. простое число.
И ложь в обратном случае.
понял, спасибо.

Добавлено через 7 минут 0 секунд
но всёже работает он неверно :\ если кто увидит ошибку сообщите пожалуйста.
Airotciv
Сообщений: n/a
07.04.2009, 22:14     тест миллера-рабина, pascal -> c++ #6
Все бы ни чего, но вот odd(x), означает x % 2 != 0, а так вроде все пашет(исправь). Спс кстати, так было лениво перебивать самому).
zhenga
Сообщений: n/a
28.04.2010, 01:35     тест миллера-рабина, pascal -> c++ #7
У меня почему-то не работает (С++). Прсит два раза нажать кнопку чтобы продолжить и всё. У вас вс1 выдаёт правильно?

Добавлено через 3 минуты
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <omp.h>
 
#include <iostream>
#include <sstream>
#include <string>
#include <fstream>
 
using namespace std;
 
int rounds=20;
long mulmod(long x,long y,long m)
{
        return (x*y)%m;
}
long powmod(long x,long a,long m)
{
        long r=1;
        while(a>0)
        {
                if(a%2!=0) 
                   r=mulmod(r,x,m);
                a=a>>1; 
                x=mulmod(x,x,m);
        }
        return r;
}
 
bool isprime(long p)
{
        long q,a;
        int i;
        //cl_randex rand;
        //rand.set_max("100000000000"); // макс число для генератора сл. чисел
        srand ( time(NULL) );
        if(p%2==0 && p>1)
        {
                 q=p-1;
                 do q=q>>1; while(q%2==0);
                 for(i=1; i<rounds; i++)//i<=rounds
                 {
                           a=rand() % (p-1) + 2; //rand.lgen - генератор сл. чисел
                           if(powmod(a,p-1,p)!=1)
                           {
                                         return false;
                                         break;//break не нужен
                           }
                           a=powmod(a,q,p);
                           if(a!=1)
                           {
                                        while(a!=1 && a!=p-1) a=mulmod(a,a,p);
                                        if(a==1)
                                        {
                                           return false;
                                           break;//break не нужен
                                        }
                           }
                  }
                  return true;
        }
        else
         return false;//return t==2
}
 
int main()
{
  long t;
    for(t=100;t<10001000;t++)
  {
          if(isprime(t))
                 cout<<"t="<<t<<endl;
                 //printf (t);
  }
  //system("pause");
  return 0;
 
    /*long t = powmod(3,3,5);
    cout<<t<<endl;*/
Airotciv
Сообщений: n/a
29.04.2010, 16:17     тест миллера-рабина, pascal -> c++ #8
Цитата Сообщение от zhenga Посмотреть сообщение
У меня почему-то не работает (С++). Прсит два раза нажать кнопку чтобы продолжить и всё. У вас вс1 выдаёт правильно?

Добавлено через 3 минуты
Писал же уже выше нада if(p%2!=0 && p>1), а не if(p%2==0 && p>1), а лучше if((P & 1) != 0 && P > 1), так быстрее будет.
zhenga
Сообщений: n/a
30.04.2010, 00:12     тест миллера-рабина, pascal -> c++ #9
Цитата Сообщение от Airotciv Посмотреть сообщение
Писал же уже выше нада if(p%2!=0 && p>1), а не if(p%2==0 && p>1), а лучше if((P & 1) != 0 && P > 1), так быстрее будет.
Спасибо огромное! Очень долго мучился.
pasha0409
54 / 1 / 1
Регистрация: 03.06.2011
Сообщений: 48
24.10.2011, 21:51     тест миллера-рабина, pascal -> c++ #10
Объясните пожалуйста что делает процедура:
C++
1
2
3
4
5
6
7
8
9
10
11
12
long powmod(long x,long a,long m)
{
        long r=1;
        while(a>0)
        {
                if(a%2!=0) 
                   r=mulmod(r,x,m);
                a=a>>1; 
                x=mulmod(x,x,m);
        }
        return r;
}
и ещё где то прочитал что псевдокод на вики не правильный, так ли это? ( тут то чуть другой алгоритм)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.11.2011, 19:58     тест миллера-рабина, pascal -> c++
Еще ссылки по теме:

Усовершенствовать алгоритм Рабина-Карпа, чтобы он искал символьную подматрицу в символьной матрице C++
Генератор псевдослучайных чисел Парка-Миллера C++
Генератор Парка и Миллера. Вывод данных из программы C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
pasha0409
54 / 1 / 1
Регистрация: 03.06.2011
Сообщений: 48
30.11.2011, 19:58     тест миллера-рабина, pascal -> c++ #11
У меня доходит до 46477 и останавливается, у вас такого не было?
Yandex
Объявления
30.11.2011, 19:58     тест миллера-рабина, pascal -> c++
Ответ Создать тему
Опции темы

Текущее время: 09:48. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru