@All
pow() mod is giving problem...
found an algo .. is some1 intrested to discuss...
Example:
Take 3^21 (mod 7)
3^2 = 9 = 2(mod 7),
3^4 = (3^2)^2 = 2^2 = 4(mod 7)
3^8 = (3^4)^2 = 4^2 = 16 = 2(mod 7)
3^16 = (3^8)^2 = 2^2 = 4(mod 7)
So now we have 3^21 = 3^16 * 3^4 * 3 = 4 * 4 * 3 = 48 = 6 (mod 7).
basically.. we can split the power and take individual a^d%n for each
then multiply to get result..
but my question is what if power is prime and big...????
On 1/18/12, Terence <technic....@gmail.com> wrote:
> error in pow.
> as long as n < 2^31, x*x fits into int64_t, since x<n.
>
> On 2012-1-18 20:51, Sourabh Singh wrote:
>> @ 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.
>
>
--
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.
