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 <dave_and_da...@juno.com> 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 <ak4u2...@gmail.com> wrote:
> > On Thu, Apr 14, 2011 at 9:08 PM, Dave <dave_and_da...@juno.com> 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 <ak4u2...@gmail.com> 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 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.- 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 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.
>
>
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT ALLAHABAD
--
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.
