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.