Re: [algogeeks] Amazon : exponentiation(x,n)
i assumed the numbers are positive..
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Fri, Jun 1, 2012 at 1:19 AM, Dave dave_and_da...@juno.com wrote:
@Amol: You've chosen to use -1 as an error return. But -1 is the correct
response if b = -1 and e is odd. Furthermore, isn't the inequality in the
if(prevresult) statement backwards. E.g., if b = 2 and e = 3, then the
code returns -1. Even reversing the inequality doesn't fix the problem when
b = -2 and e = 3, for which the correct response is -8, without overflow.
Dave
On Thursday, May 31, 2012 2:04:24 AM UTC-5, Amol Sharma wrote:
for checking overflow you can check the value after and before the
multiplication..if value after multiplication is less then there is
overflow for sure
now code will look like this :
int pow(int b, int e)
{
int result = (e 1) ? b:1;
int prev;
while( e 1 )
{
prev=b;
b = (b * b);
if(bprev)
return -1; //OVERFLOW
e = 1;
if( e 1 )
{
prev=result;
result = (result * b);
if(prevresult)
return -1; //OVERFLOW
}
return result;
}
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Thu, May 31, 2012 at 12:07 PM, Ashish Goel ashg...@gmail.com wrote:
the return type is int, hence when xpowern becomes bigger than INT_MAX,
it should throw an exception.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, May 31, 2012 at 11:59 AM, Amol Sharma amolsharm...@gmail.comwrote:
i didn't got your problem where is the overflow.. ??
btw i will do the same like this :
int pow(int b, int e)
{
int result = (e 1) ? b:1;
while( e 1 )
{
b = ((long long int)b * b);
e = 1;
if( e 1 )
result = ((long long int)result * b);
}
return result;
}
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Thu, May 31, 2012 at 9:54 AM, Ashish Goel ashg...@gmail.com wrote:
This algo is log(n) algo for finding power. However, this also has a
problem of overflow. How do we control this.
int power(int x, int n) {
int expo =1;
int even=x;
while (n0)
{
while (n 0x1==0) {
n=1; /*divide by 2*/
even*=even;
}
expo = expo*even;
n=1; /*n will be odd here always*/
}
return expo;
}
this is utilizing the fact that n is a binary number and can be
written as x*xE when odd or xE otherwise.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
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+unsubscribe@**
googlegroups.com algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at http://groups.google.com/**
group/algogeeks?hl=en 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+unsubscribe@**
googlegroups.com algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at http://groups.google.com/**
group/algogeeks?hl=en 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+unsubscribe@**
googlegroups.com algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at http://groups.google.com/**
group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/UuSiE5US8SkJ.
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] Amazon : exponentiation(x,n)
the return type is int, hence when xpowern becomes bigger than INT_MAX, it
should throw an exception.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, May 31, 2012 at 11:59 AM, Amol Sharma amolsharm...@gmail.comwrote:
i didn't got your problem where is the overflow.. ??
btw i will do the same like this :
int pow(int b, int e)
{
int result = (e 1) ? b:1;
while( e 1 )
{
b = ((long long int)b * b);
e = 1;
if( e 1 )
result = ((long long int)result * b);
}
return result;
}
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Thu, May 31, 2012 at 9:54 AM, Ashish Goel ashg...@gmail.com wrote:
This algo is log(n) algo for finding power. However, this also has a
problem of overflow. How do we control this.
int power(int x, int n) {
int expo =1;
int even=x;
while (n0)
{
while (n 0x1==0) {
n=1; /*divide by 2*/
even*=even;
}
expo = expo*even;
n=1; /*n will be odd here always*/
}
return expo;
}
this is utilizing the fact that n is a binary number and can be written
as x*xE when odd or xE otherwise.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
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.
Re: [algogeeks] Amazon : exponentiation(x,n)
for checking overflow you can check the value after and before the
multiplication..if value after multiplication is less then there is
overflow for sure
now code will look like this :
int pow(int b, int e)
{
int result = (e 1) ? b:1;
int prev;
while( e 1 )
{
prev=b;
b = (b * b);
if(bprev)
return -1; //OVERFLOW
e = 1;
if( e 1 )
{
prev=result;
result = (result * b);
if(prevresult)
return -1; //OVERFLOW
}
return result;
}
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Thu, May 31, 2012 at 12:07 PM, Ashish Goel ashg...@gmail.com wrote:
the return type is int, hence when xpowern becomes bigger than INT_MAX, it
should throw an exception.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, May 31, 2012 at 11:59 AM, Amol Sharma amolsharm...@gmail.comwrote:
i didn't got your problem where is the overflow.. ??
btw i will do the same like this :
int pow(int b, int e)
{
int result = (e 1) ? b:1;
while( e 1 )
{
b = ((long long int)b * b);
e = 1;
if( e 1 )
result = ((long long int)result * b);
}
return result;
}
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Thu, May 31, 2012 at 9:54 AM, Ashish Goel ashg...@gmail.com wrote:
This algo is log(n) algo for finding power. However, this also has a
problem of overflow. How do we control this.
int power(int x, int n) {
int expo =1;
int even=x;
while (n0)
{
while (n 0x1==0) {
n=1; /*divide by 2*/
even*=even;
}
expo = expo*even;
n=1; /*n will be odd here always*/
}
return expo;
}
this is utilizing the fact that n is a binary number and can be written
as x*xE when odd or xE otherwise.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
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.
Re: [algogeeks] Amazon : exponentiation(x,n)
@Amol: You've chosen to use -1 as an error return. But -1 is the correct
response if b = -1 and e is odd. Furthermore, isn't the inequality in the
if(prevresult) statement backwards. E.g., if b = 2 and e = 3, then the
code returns -1. Even reversing the inequality doesn't fix the problem when
b = -2 and e = 3, for which the correct response is -8, without overflow.
Dave
On Thursday, May 31, 2012 2:04:24 AM UTC-5, Amol Sharma wrote:
for checking overflow you can check the value after and before the
multiplication..if value after multiplication is less then there is
overflow for sure
now code will look like this :
int pow(int b, int e)
{
int result = (e 1) ? b:1;
int prev;
while( e 1 )
{
prev=b;
b = (b * b);
if(bprev)
return -1; //OVERFLOW
e = 1;
if( e 1 )
{
prev=result;
result = (result * b);
if(prevresult)
return -1; //OVERFLOW
}
return result;
}
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Thu, May 31, 2012 at 12:07 PM, Ashish Goel ashg...@gmail.com wrote:
the return type is int, hence when xpowern becomes bigger than INT_MAX,
it should throw an exception.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Thu, May 31, 2012 at 11:59 AM, Amol Sharma amolsharm...@gmail.comwrote:
i didn't got your problem where is the overflow.. ??
btw i will do the same like this :
int pow(int b, int e)
{
int result = (e 1) ? b:1;
while( e 1 )
{
b = ((long long int)b * b);
e = 1;
if( e 1 )
result = ((long long int)result * b);
}
return result;
}
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/
On Thu, May 31, 2012 at 9:54 AM, Ashish Goel ashg...@gmail.com wrote:
This algo is log(n) algo for finding power. However, this also has a
problem of overflow. How do we control this.
int power(int x, int n) {
int expo =1;
int even=x;
while (n0)
{
while (n 0x1==0) {
n=1; /*divide by 2*/
even*=even;
}
expo = expo*even;
n=1; /*n will be odd here always*/
}
return expo;
}
this is utilizing the fact that n is a binary number and can be written
as x*xE when odd or xE otherwise.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
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 view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/UuSiE5US8SkJ.
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] Amazon : exponentiation(x,n)
This algo is log(n) algo for finding power. However, this also has a
problem of overflow. How do we control this.
int power(int x, int n) {
int expo =1;
int even=x;
while (n0)
{
while (n 0x1==0) {
n=1; /*divide by 2*/
even*=even;
}
expo = expo*even;
n=1; /*n will be odd here always*/
}
return expo;
}
this is utilizing the fact that n is a binary number and can be written as
x*xE when odd or xE otherwise.
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
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.
