@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(prev<result)" 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(b<prev) > return -1; //OVERFLOW > e >>= 1; > if( e & 1 ) > { > prev=result; > result = (result * b); > if(prev<result) > return -1; //OVERFLOW > } > return result; > } > -- > > > Amol Sharma > Third Year Student > Computer Science and Engineering > MNNIT Allahabad > <http://gplus.to/amolsharma99> > <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://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.com>wrote: >> >>> 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/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://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 (n>0) >>>> { >>>> 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.