べき乗演算のアルゴリズムについて

580 ワード

今日、xを求めるn乗の演算に関する再帰アルゴリズムと反復アルゴリズムを見て、わざわざ記録します.
再帰アルゴリズム:
int fun(int x, int n)
{
    int val;
    val = 1;
    
    if(n>0)
    {
        if(n%2 == 1)
            val = val * x;
        val = val * fun(x*x, n/2);
    }
    return val;
}

反復アルゴリズム:
int fun(int x, int n)
{
    int val;
    int product;
    product = 1;
    
    val = x;
    while(n>0)
    {
        if(n%2 == 1)
            product = product * val;

        val = val * val;
        n = n/2;
    }
    return product;
}