How to implement square root and exponentiation on arbitrary length numbers?

Question

I'm working on new data type for arbitrary length numbers (only non-negative integers) and I got stuck at implementing square root and exponentiation functions (only for natural exponents). Please help.

I store the arbitrary length number as a string, so all operations are made char by char.

Please don't include advices to use different (existing) library or other way to store the number than string. It's meant to be a programming exercise, not a real-world application, so optimization and performance are not so necessary.

If you include code in your answer, I would prefer it to be in either pseudo-code or in C++. The important thing is the algorithm, not the implementation itself.

Thanks for the help.

Answer 1

Square root: Babylonian method. I.e.

function sqrt(N):
    oldguess = -1
    guess = 1
    while abs(guess-oldguess) > 1:
        oldguess = guess
        guess = (guess + N/guess) / 2
    return guess

Exponentiation: by squaring.

function exp(base, pow):
    result = 1
    bits = toBinary(powr)
    for bit in bits:
        result = result * result
        if (bit):
            result = result * base
    return result

where toBinary returns a list/array of 1s and 0s, MSB first, for instance as implemented by this Python function:

def toBinary(x):
    return map(lambda b: 1 if b == '1' else 0, bin(x)[2:])

Note that if your implementation is done using binary numbers, this can be implemented using bitwise operations without needing any extra memory. If using decimal, then you will need the extra to store the binary encoding.

However, there is a decimal version of the algorithm, which looks something like this:

function exp(base, pow):
    lookup = [1, base, base*base, base*base*base, ...] #...up to base^9
     #The above line can be optimised using exp-by-squaring if desired

    result = 1
    digits = toDecimal(powr)
    for digit in digits:
        result = result * result * lookup[digit]
    return result

Answer 2

Exponentiation is trivially implemented with multiplication - the most basic implementation is just a loop,

result = 1;    
for (int i = 0; i < power; ++i) result *= base;

You can (and should) implement a better version using squaring with divide & conquer - i.e. a^5 = a^4 * a = (a^2)^2 * a.

Square root can be found using Newton's method - you have to get an initial guess (a good one is to take a square root from the highest digit, and to multiply that by base of the digits raised to half of the original number's length), and then to refine it using division: if a is an approximation to sqrt(x), then a better approximation is (a + x / a) / 2. You should stop when the next approximation is equal to the previous one, or to x / a.