Geek Answers Handbook

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

I am working on a new data type for arbitrary length numbers (only non-negative integers) and I am stuck with the implementation of the square root and exponential functions (only for natural exponents). Please, help.

I save an arbitrary length number as a string, so all char operations on char are performed .

Please do not include tips to use another (existing) library or another way of storing the number, except for the string. This meant a programming exercise, not a real-world application, so optimization and performance are not needed.

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

Thanks for the help.

+5
source share
2 answers

Square root: the 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

Exposure: 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 it toBinaryreturns a list / array of 1s and 0s, first MSB, for example, implemented by this Python function:

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

, , . , .

, :

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
+10

- - ,

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

( ) , , .. a ^ 5 = a ^ 4 * a = (a ^ 2) ^ 2 * a.

- ( - , ), : sqrt (x), (a + x/a)/2. , , x/a.

+3

More articles:


All Articles