@ sunny agrawal
you are right. but i have used check a>n also . no improvement .
i think algo is wrong in later part.. somewhere..
@ Terence
1) pow may not work for big n but , m just checking for n=1..200
just to check wether algo is right.. and it's not working even for n=7,19...
2) d,s are also coming fine for small values.. of n
3) for x i have used... 64bit integer.. uint64_t in it's declaration.
i just want to get algo right first then bother about big n ;-)
On 1/18/12, Terence <technic....@gmail.com> wrote:
> 1. the computing of d is incorrect.
> d = n-1;
> while((d&1)==0) d>>=1;
>
> 2. the accuracy of pow is far from enough. you should implement your own
> pow-modulo-n method.
>
> 3. for big n, (exceed 32bit), x=(x*x)%n can be overflow also. you may
> need to implement your own multiply method in this case.
>
>
> On 2012-1-18 18:15, Sourabh Singh wrote:
>> @all output's to above code are just random.. some prime's. found
>> correctly while some are not
>>
>> why i used certain primes to check ie.(2,3,31,73,61,7) coz.. its given
>> n wiki for about 10^15 checking with these is enough..
>>
>> On 1/18/12, Sourabh Singh<singhsourab...@gmail.com> wrote:
>>> @ALL hi everyone m trying to make prime checker based on miller-rabin
>>> test . can some1 point out . wat's wrong with the code. thank's alot
>>> in advance...
>>>
>>> //prime checker based on miller-rabin test
>>> #include<iostream>
>>> #include<conio.h>
>>> #include<math.h>
>>> int is_prime(int n)
>>> {
>>> if(n==2 | n==3)
>>> return 1;
>>> if(((n-1)%6!=0& (n+1)%6!=0) || n<2)
>>> return 0;
>>> int s,d;
>>> for(s=0;1<<s<n;++s); s--;d=(n%(1<<s));
>>>
>>> int primes[6]={2,3,7,31,61,73},i,a,flag;
>>> uint64_t x;
>>> for(i=0;i<6;i++)
>>> { flag=0;
>>>
>>> a=primes[i];
>>> x=uint64_t(pow(a,d))%n;
>>> if(x==1 | x==n-1)
>>> continue;
>>> for(int r=1;r<s;r++)
>>> { x=(x*x)%n;
>>> printf("x is %llu\n",x);
>>> if(x==1)
>>> return 0;
>>> else
>>> flag=1;
>>> }
>>> if(flag)
>>> continue;
>>> return 0;
>>> }
>>> return 1;
>>> }
>>> main()
>>> {
>>> for(int k=1;k<100;k++)
>>> {
>>> printf("%d is %d\n",k,is_prime(k));
>>> }
>>> getch();
>>> }
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
