@Saurabh: I first suggested using long long int, but the original poster, Aamir, rejected it. Thus, I gave a method that can be done with int only.
Dave On Apr 14, 8:52 pm, saurabh singh <[email protected]> wrote: > Probably the best would be to use long long int int this case.Anyhow a few > bytes of memory wont hurt you,rather it will significantly improve your > time. > For much larger numbers than this try Exponentiation by squaring > method....This does the same in o(log n) > time<http://en.wikipedia.org/wiki/Exponentiation_by_squaring> > > > > > > On Fri, Apr 15, 2011 at 1:27 AM, Dave <[email protected]> wrote: > > @Aamir: Okay. How about this: > > Write A = 10000 * ahi + alo, where 0 < alo < 10000; i.e. > > ahi = A/10000 and alo = A%10000. > > Then A*A = 100000000 * ahi * ahi + 20000 * ahi * alo + alo * alo, > > so A*A%Mod = (100000000 * ((ahi * ahi) % (Mod/100000000)) + 10000 * > > ((2 * ahi * alo) % (Mod/10000)) + alo * alo % Mod) % Mod > > > This simplifies to (100000000*(ahi*ahi)%10) + 10000*((2*ahi*alo) > > %100000 + (alo*alo)%Mod)%Mod > > > Dave > > > On Apr 14, 11:09 am, AAMIR KHAN <[email protected]> wrote: > > > On Thu, Apr 14, 2011 at 9:08 PM, Dave <[email protected]> wrote: > > > > @AAmir: The easiest way is to declare A as long long int. Be sure to > > > > change the printf format string. > > > > > I know that. But since i want to have only the last 9 digits of the > > answer > > > > that can be accommodated in int only so there is no need for long long i > > > think. > > > > > Dave > > > > > On Apr 14, 8:31 am, AAMIR KHAN <[email protected]> wrote: > > > > > #include<cstdio> > > > > > #define MOD (int)1e9 > > > > > using namespace std; > > > > > int main() { > > > > > int A = 33554432; > > > > > printf("%d\n",A*A); > > > > > printf("%d\n",((A*A)%MOD)); > > > > > return 0; > > > > > > } > > > > > > How can i calculate, lets say last 9 digits of square of 33554432 ? > > > > > > Thanks, > > > > > Aamir > > > > > -- > > > > You received this message because you are subscribed to the Google > > Groups > > > > "Algorithm Geeks" group. > > > > To post to this group, send email to [email protected]. > > > > To unsubscribe from this group, send email to > > > > [email protected]. > > > > For more options, visit this group at > > > >http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text - > > > > - Show quoted text - > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > > [email protected]. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > Saurabh Singh > B.Tech (Computer Science) > MNNIT ALLAHABAD- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
