@all sorry .. 21 is prime :-)
hw can above algo be well implemented to get mpow function...
On 1/18/12, Sourabh Singh <singhsourab...@gmail.com> wrote:
> @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.
