i assumed the numbers are positive.. --
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 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(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+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. > -- 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.