Search code examples
mathexponentiationzoho

How to implement exponentiation of a rational number without nth root?


Its available for me only log(base "e"), sin, tan and sqrt (only square root) functions and the basic arithmetical operators (+ - * / mod). I have also the "e" constant.

I'm experimenting several problems with Deluge (zoho.com) for these restrictions. I must implement exponentiation of rational (fraction) bases and exponents.


Solution

  • Say you want to calculate pow(A, B)

    Consider the representation of B in base 2:

    B = b[n]   * pow(2, n    ) +
        b[n-1] * pow(2, n - 1) +
        ...
        b[2]   * pow(2, 2    ) +
        b[1]   * pow(2, 1    ) +
        b[0]   * pow(2, 0    ) +
        b[-1]  * pow(2, -1   ) +
        b[-2]  * pow(2, -2   ) +
        ...
    
     = sum(b[i] * pow(2, i))
    

    where b[x] can be 0 or 1 and pow(2, y) is an integer power of two (i.e., 1, 2, 4, 1/2, 1/4, 1/8).

    Then,

    pow(A, B) = pow(A, sum(b[i] * pow(2, i)) = mul(pow(A, b[i] * pow(2, i)))
    

    And so pow(A, B) can be calculated using only multiplications and square root operations