Re: [algogeeks] Re: Square of Large integer
bro u r currect but what happen when result exceed greater then integer range? here sq variable is not bery large -- 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.
Re: [algogeeks] Re: Square of Large integer
Hi hary, when do you think that there can be problem? The sq is never made to store a value 10^9 (for previous sq) +9*10^9 (for new sum) hence the sum never exceeds 10^10 which is under the range of int. Correct me if i go wrong somewhere. On Thu, Apr 28, 2011 at 12:26 PM, hary rathor harry.rat...@gmail.comwrote: bro u r currect but what happen when result exceed greater then integer range? here sq variable is not bery large -- 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.
[algogeeks] Re: Square of Large integer
Algo can be derived from these equations: (x + 1) * y = (x * y) + y (2*x) * y = 2 * (x * y). Runs in O(log number). -- 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.
[algogeeks] Re: Square of Large integer
On Apr 14, 9:52 pm, saurabh singh saurab...@gmail.com wrote: For much larger numbers than this try Exponentiation by squaring method Just how much improvement should the OP expect from the exponentiation by squaring method... when the exponent is 2? -- 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.
[algogeeks] Re: Square of Large integer
*Output:*
0
0
On Thu, Apr 14, 2011 at 7:01 PM, AAMIR KHAN ak4u2...@gmail.com wrote:
#includecstdio
#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.
Re: [algogeeks] Re: Square of Large integer
search nd read chinese remainder theorem
On Thu, Apr 14, 2011 at 7:04 PM, AAMIR KHAN ak4u2...@gmail.com wrote:
*Output:*
0
0
On Thu, Apr 14, 2011 at 7:01 PM, AAMIR KHAN ak4u2...@gmail.com wrote:
#includecstdio
#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.
--
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.
Re: [algogeeks] Re: Square of Large integer
On Thu, Apr 14, 2011 at 7:40 PM, Akash Mukherjee akash...@gmail.com wrote:
search nd read chinese remainder theorem
please elaborate how can i use chinese remainder theorem.
On Thu, Apr 14, 2011 at 7:04 PM, AAMIR KHAN ak4u2...@gmail.com wrote:
*Output:*
0
0
On Thu, Apr 14, 2011 at 7:01 PM, AAMIR KHAN ak4u2...@gmail.com wrote:
#includecstdio
#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.
--
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.
[algogeeks] Re: Square of Large integer
@AAmir: The easiest way is to declare A as long long int. Be sure to
change the printf format string.
Dave
On Apr 14, 8:31 am, AAMIR KHAN ak4u2...@gmail.com wrote:
#includecstdio
#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.
Re: [algogeeks] Re: Square of Large integer
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:
#includecstdio
#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.
--
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.
Re: [algogeeks] Re: Square of Large integer
i strongly believe that you should have tried harder . still , here goes
#includeiostream
#includecstdio
#includestdlib.h
using namespace std;
int mulmod ( int a , int b , int c )
{
int x = 0 , y = a % c ;
while ( b 0 )
{
if ( b % 2 == 1 )
{
x = ( x + y ) % c ;
}
y = ( y * 2 ) % c ;
b /= 2 ;
}
return x % c ;
}
int modulo ( int a , int b , int c )
{
int x = 1 , y = a ;
while ( b )
{
if ( b 1)
{
x = mulmod ( x , y , c ) ;
}
y = mulmod ( y ,y, c ) ;
b /= 2 ;
}
return x % c ;
}
int main ()
{
printf ( %d , modulo ( 33554432 , 2 , 10 ) ) ;
}
On Thu, Apr 14, 2011 at 9:39 PM, 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:
#includecstdio
#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.
--
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.
--
Regards
Anurag Atri
II year
Computer Engineering
Delhi College Of Engineering
--
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.
[algogeeks] Re: Square of Large integer
@Aamir: Okay. How about this:
Write A = 1 * ahi + alo, where 0 alo 1; i.e.
ahi = A/1 and alo = A%1.
Then A*A = 1 * ahi * ahi + 2 * ahi * alo + alo * alo,
so A*A%Mod = (1 * ((ahi * ahi) % (Mod/1)) + 1 *
((2 * ahi * alo) % (Mod/1)) + alo * alo % Mod) % Mod
This simplifies to (1*(ahi*ahi)%10) + 1*((2*ahi*alo)
%10 + (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:
#includecstdio
#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.
Re: [algogeeks] Re: Square of Large integer
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
methodThis does the same in o(log n)
timehttp://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 = 1 * ahi + alo, where 0 alo 1; i.e.
ahi = A/1 and alo = A%1.
Then A*A = 1 * ahi * ahi + 2 * ahi * alo + alo * alo,
so A*A%Mod = (1 * ((ahi * ahi) % (Mod/1)) + 1 *
((2 * ahi * alo) % (Mod/1)) + alo * alo % Mod) % Mod
This simplifies to (1*(ahi*ahi)%10) + 1*((2*ahi*alo)
%10 + (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:
#includecstdio
#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.
