@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 <[email protected]> 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 <[email protected]>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 <[email protected]> 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 [email protected].
>>>> To unsubscribe from this group, send email to
>>>> [email protected].
>>>> 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 [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected].
>>> 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 [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
