@ Terence
I belive nw its giving wrong answer for n>41 onwards
due to error's in pow and x*x over flow as u already stated...
i guess algo is right nw.. ;-)
thanx again..
On 1/18/12, Sourabh Singh <singhsourab...@gmail.com> wrote:
> @ thanx got it.. silly mistakes ;-) . missed thought it ws + between s and
> d.
>
>
> //suggested corrections made.. still not working..
> #include<iostream>
> #include<conio.h>
> #include<math.h>
> using namespace std;
> 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 j,s,d=n-1; while((d&1)==0) d>>=1;
>
> s=n/d;for(j=0;1<<j<s;j++); s=j;
>
> int primes[6]={2,3,7,31,61,73},i,a,flag;
> uint64_t x;
> for(i=0;i<6;i++)
> { if(primes[i]>=n)
> break;
> a=primes[i];
> x=uint64_t(pow(a,d))%n;
> if(x==1 || x==n-1)
> continue;
> int r;
> for(r=1;r<s;r++)
> { x=(x*x)%n;
> if(x==1)
> return 0;
> if(x==n-1)
> break;
> }
> if(x!=n-1)
> return 0;
> }
> return 1;
> }
> main()
> {for(int k=1;k<2000;k++)
> if(is_prime(k))
> printf("%d is %d\n",k,is_prime(k));
> getch();
> }
>
>
> On 1/18/12, Terence <technic....@gmail.com> wrote:
>> @Sourabh
>>
>> m=2^s***d
>> primes[i]*<*n
>>
>>
>>
>> On 2012-1-18 19:39, Sourabh Singh wrote:
>>> @Terrence
>>>
>>> sry i didn't explain what s,d were they were also wrong i ws
>>> calculating for n not n-1
>>> earlier n=2^s+d
>>>
>>> nw m=n-1; for odd n
>>> m=2^s+d;
>>>
>>> //suggested corrections made.. still not working..
>>> #include<iostream>
>>> #include<conio.h>
>>> #include<math.h>
>>> using namespace std;
>>> 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 m=n-1;
>>> int s,d;
>>> for(s=0;1<<s<m;++s); s--;d=(m%(1<<s));
>>>
>>> int primes[6]={2,3,7,31,61,73},i,a,flag;
>>> uint64_t x;
>>> for(i=0;i<6;i++)
>>> { if(primes[i]>n)
>>> break;
>>> 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;
>>> if(x==1)
>>> return 0;
>>> if(x==n-1)
>>> break;
>>> }
>>> if(x!=n-1)
>>> return 0;
>>> }
>>> return 1;
>>> }
>>> main()
>>> {for(int k=1;k<20;k++) printf("%d is %d\n",k,is_prime(k)); getch();}
>>>
>>>
>>> On 1/18/12, Sourabh Singh<singhsourab...@gmail.com> wrote:
>>>> @ 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.
>>
>>
>
--
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.
