CODEWITHSUNDEEP
c++algorithm
William Thomas
William Thomas

Reputation: 99

Generalizng the Babylonian Square Root Algorithm to nth roots

I have been looking for root algorithms, and came across the Babylonian Algorithm. I really like it since it is simple and easy to understand. But the problem is that it only takes square roots, when I am making a function that can take the root of a number with any power. I am just trying it take take positive integer.

Here is the function:

double functions::rot(double x, double y) {
    double z = x;
    double w = 1;
    double e = 0.000001; 
    while (z - w > e){
        z = (z + w) / 2;
        w = x / z;
    }
    return z;
}

y is the power. Does anyone have a way to change this algorithm so y is the power of the root? For example, if y = 3, it takes the cubed root.

Upvotes: 4

Views: 1001

Answers (2)

IVlad
IVlad

Reputation: 43467

The comment that says to change w = x / z to w = x / z*z is only 1/3 (pun intended) correct. You also need two more changes, which I think are obvious from this Python code:

def rot(x, y): # 
    z = x
    w = 1
    e = 0.000001
    while (z - w > e):
        z = ((y - 1) * z + w) / y
        w = x / (z ** (y - 1)) # a ** b is a to the power of b in Python
                               # you might want to use modular exponentiation in C++
                               # (or not if y is double...)
    return z


print(rot(64, 3)) # prints 4
print(rot(59, 6)) # prints 1.9730678338673044

See here for a reference. I suggest you read it, as it gives more in depth explanations.

Upvotes: 2

user448810
user448810

Reputation: 17866

Newton's method is similar to the Babylonian method and can be used to extract roots of any power. We assume both k, the root, and n, the input, are positive integers; both divisions in the assignment of u are integer division (ignore the remainder):

function iroot(k, n)
    k1, u, s := k-1, n, n+1
    while u < s
        u := (u * k1 + n / (u ** k1)) / k
        s := u
    return s

Warning: untested pseudocode. Function iroot returns the largest integer that does not exceed n when multiplied by itself k times.

Upvotes: 0

Related Questions