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 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.
