Ruby 언어로 평방근, 입방근, n제곱근 구하는 함수를 구현하고 테스트하기

음이 아닌 실수 A 의 평방근 sqrt(A) 를 구하는 Heron 의 방법:

        반복함수  g(x) = (x + A/x) / 2   를 이용

 

실수 A 의 n제곱근 root(n, A) 를 구하는 Newton-Raphson 의 방법

        반복함수  g(x) = ((n-1)*x + A/(x**(n - 1))) / n    를 이용

n = 2 인 경우에는 Newton-Raphson 의 방법이 Heron 의 방법과 동일하다.

(참조. http://en.wikipedia.org/wiki/Newton's_method )

 

Ruby 언어에는 지수 연산자 ** 를 (밑수)**(지수) 의 형식으로 언어 자체에서 지원하고 있다. 하지만 차후 필요한 데가 있을 것 같아서 이와 유사한 n 제곱 함수와 n 제곱근 함수를 구현해 보았다.

지수가 정수인 거듭제곱을 계산하는  함수도 nPow(), gPow, mPow() 세 개 구현해 놓았는데, 이들 세 함수는 절차적 언어의 성능상 재귀호출이 아니고 단순 반복 기법을 사용하는 함수이다. 이 세 함수 중 mPow() 의 성능이 가장 우수하다. 큰 지수의 경우 for 반복문의 반복회수를 따져 보면 성능 비교를 할 수 있을 것이다. (성능 비교를 위해 세 가지를 모두 소스에 남겨 두었다.) mPow() 함수는 n 제곱근을 구하는 재귀함수 newtonNthRoot(int, double) 의 구현에 사용되기도 한다. if ... else ... 구문이 많아 소스가 복잡하게 보일지 모르겠으나 이는 밑수나 지수가 음수이거나 0인 경우의 처리를 위함이다. 구현된 모든 함수의 구현에는 예외상황(예를 들어, 음수의 짝수 제곱근 같은 예외상황) 처리 과정이 있다.

아래의 소스는 대부분 버전의 Ruby 에서 실행되도록 작성된 소스이다.

참고로, Ruby 언어는 (다른 언어와 달리) 대분자만으로 쓰여진 것은 구문상 변수가 아니라 상수를 의미한다. 잠간 irb(인터랙티브 Ruby)를 실행하여 확인해 보자.

irb(main):001:0> ABC = 5
=> 5
irb(main):002:0> ABC = 3
(irb):2: warning: already initialized constant ABC
=> 3

그러므로 아래의 소스 첫 부분에

MAX_ITER = 20000
M_EPSILON = 1.0e-15

로 선언한 것은 (두 전역변수가 아니라) 두 상수를 선언한 것이며, 이는 소스 전체에서 통용된다.

#!/usr/bin/env ruby
# -*- encoding: utf-8 -*-

# Filename: testNthRoot.rb
#
#            Approximate square roots, cubic roots and n-th roots of a given number.
#
# Execute: ruby testNthRoot.rb
#
# Date: 2013. 1. 6.
# Copyright (c) 2013 PH Kim  (pkim __AT__ scripts.pe.kr)

MAX_ITER = 20000
M_EPSILON = 1.0e-15

#
# Compute the n-th root of x to a given scale, x > 0.
#
def nPow(a, n)
    if n > 0
        if n == 1
            return a
        else
            if a == 0.0 or a == 1.0
                return a
            elsif a == -1.0
                if n % 2 == 1
                    return -1.0
                else
                    return 1.0
                end
            elsif a < 0.0
                if n % 2 == 1
                    return -nPow(-a, n)
                else
                    return nPow(-a, n)
                end
            else
                y = 1.0
                for i in 0...n do
                    y *= a
                end
                return y
            end
         end
    elsif n == 0
        return 1.0
    else      #  when n < 0
        if a == 0.0
            raise RuntimeError,'Negative powering exception of zero.'
        else
            if n == -1
                return 1.0/a
            else
                return 1.0/nPow(a, -n)
            end
        end
    end
end

#
# Compute the n-th root of x to a given scale, x > 0.
#
def gPow(a, n)
    if n > 0
        if n == 1
            return a
        else
            if a == 0.0 or a == 1.0
                return a
            elsif a == -1.0
                if n % 2 == 1
                    return -1.0
                else
                    return 1.0
                end
            elsif a < 0.0
                if n % 2 == 1
                    return -gPow(-a, n)
                else
                    return gPow(-a, n)
                end
            else
                y = 1.0
                r = a
                m = 8*4 - 1            #  8*sizeof(int) - 1;
                one = 1
                for i in 0..m do
                    if (n & one) == 0
                        y *= 1.0
                    else
                        y *= r
                    end
                    r = r*r
                    one <<= 1
                    if one > n
                        break
                    end
                end
                return y
            end
        end
    elsif n == 0
        return 1.0
    else      #  when n < 0
        if a == 0.0
            raise RuntimeError,'Negative powering exception of zero.'
        else
            if n == -1
                return 1.0/a
            else
                return 1.0/gPow(a, -n)
            end
        end
    end
end

 

#
# Compute the n-th root of x to a given scale, x > 0.
#
def mPow(a, n)
    if n > 0
        if n == 1
            return a
        else
            if a == 0.0 or a == 1.0
                return a
            elsif a == -1.0
                if n % 2 == 1
                    return -1.0
                else
                    return 1.0
                end
            elsif a < 0.0
                if n % 2 == 1
                    return -mPow(-a, n)
                else
                    return mPow(-a, n)
                end
            else
                y = 1.0
                r = a
                m = n
                while m > 0 do
                    if (m & 0x1) == 1
                        y *= r
                    end
                    r = r*r
                    m >>= 1
                end
                return y
            end
        end
    elsif n == 0
        return 1.0
    else      #  when n < 0
        if a == 0.0
            raise RuntimeError,'Negative powering exception of zero.'
        else
            if n == -1
                return 1.0/a
            else
                return 1.0/mPow(a, -n)
            end
        end
    end
end

#
# Compute the square root of x to a given scale, x > 0.
#
def heronSqrt(a)
    if a < 0.0
        raise RuntimeError,'Cannot find the sqrt of a negative number.'
    elsif a == 0.0 or a == 1.0
        return a
    else
        x1 = a
        x2 = (x1 + a/x1)/2.0
        er = x1 - x2
        counter = 0
        while x1 + er != x1 do
            x1 = x2
            x2 = (x1 + a/x1)/2.0
            er = x1 - x2
            if (er).abs < (M_EPSILON*x1).abs
                break
            end
            counter += 1
            if counter > MAX_ITER
                break
            end
        end
        if counter >= MAX_ITER
            raise RuntimeError,'Inaccurate sqrt exception by too many iterations.'
        end
        return x2
    end
end

#
# Compute the cubic root of x to a given scale, x > 0.
#
def newtonCbrt(a)
    if a == 0.0 or a == 1.0 or a == -1.0
        return a
    elsif a < 0.0
        return -newtonCbrt(-a)
    else
        x1 = a
        x2 = (2.0*x1 + a/(x1*x1))/3.0
        er = x1 - x2
        counter = 0
        while x1 + er != x1 do
            x1 = x2
            x2 = (2.0*x1 + a/(x1*x1))/3.0
            er = x1 - x2
            if (er).abs < (M_EPSILON*x1).abs
                break
            end
            counter += 1
            if counter > MAX_ITER
                break
            end
        end
        if counter >= MAX_ITER
            raise Error,'Inaccurate sqrt exception by too many iterations.'
        end
        return x2
    end
end

#
# Compute the n-th root of x to a given scale, x > 0.
#
def newtonNthRoot(n, a)
    if n == 0
        return 1.0
    elsif n == 1
        return a
    elsif n > 0
        if a == 0.0 or a == 1.0
            return a
        elsif a == -1.0
            if n % 2 == 1
                return a
            else
                raise RuntimeError,'Cannot find the even n-th root of a negative number.'
            end
        elsif a < 0.0
            if n % 2 == 1
                return -newtonNthRoot(n, -a)
            else
                raise RuntimeError,'Cannot find the even n-th root of a negative number.'
            end
        elsif a < 1.0
            return 1.0/newtonNthRoot(n, 1.0/a)
        else
            x1 = a
            xn = mPow(x1, n - 1)
            x2 = ((n -1)*x1 + a/xn)/n
            er = x1 - x2
            counter = 0
            while x1 + er != x1 do
                x1 = x2
                xn = mPow(x1, n - 1)
                x2 = ((n -1)*x1 + a/xn)/n
                er = x1 - x2
                if (er).abs < (M_EPSILON*x1).abs
                    break
                end
                counter += 1
                if counter > MAX_ITER
                    break
                end
            end
            if counter >= MAX_ITER
                raise RuntimeError, 'Inaccurate sqrt exception by too many iterations.'
            end
            return x2
        end
    else
        if a == 0.0
            raise Error, 'Cannot find the negative n-th root of zero.'
        else
            return 1.0/newtonNthRoot(-n, a)
        end
    end
end 

x = 16.0
u = Math.sqrt(x)

print "[ Testing heronSqrt(double) ]--------------------\n"
print "x = %g\n" % x
print "u = sqrt(%g) = %g\n" % [x, u]
y = heronSqrt(x)
print "y = heronSqrt(%g) = %g\n" % [x, y]
print "y*y = %g\n" % (y*y)
print "\n"

print "[ Testing newtonCbrt(double) ]--------------------\n"
x = -216.0
print "x = %g\n" % x
print "-exp(log(-x)/3.0) = %g\n" % -Math::exp(Math::log(-x)/3.0)
w = newtonCbrt(x)
print "w = newtonCbrt(%g) = %g\n" % [x, w]
print "w*w*w = %g\n" % (w*w*w)
print "\n"

x = 729000000000.0
print "x = %g\n" % x
print "exp(log(x)/3.0) = %g\n" % Math::exp(Math::log(x)/3.0)
w = newtonCbrt(x)
print "w = newtonCbrt(%g) = %g\n" % [x, w]
print "w*w*w = %g\n" % (w*w*w)
print "\n"

print "[ Testing newtonNthRoot(int, double) ]--------------------\n"
z = newtonNthRoot(3, x)
print "x = %g\n" % x
print "z = newtonNthRoot(3, %g) = %g\n" % [x, z]
print "z*z*z = %g\n" % (z*z*z)
print "\n"

x = 12960000000000000000.0
z = newtonNthRoot(4, x)
print "x = %g\n" % x
print "z = newtonNthRoot(4, x) = newtonNthRoot(4, %g) =  %g\n" % [x, z]
print "z*z*z*z = %g\n" % (z*z*z*z)
print "\n"

x = 1.0/12960000000000000000.0
z = newtonNthRoot(4, x)
print "x = %g\n" % x
print "exp(log(x)/4.0) = %g\n" % Math::exp(Math::log(x)/4.0)
print "z = newtonNthRoot(4, x) = newtonNthRoot(4, %g) =  %g\n" % [x, z]
print "z*z*z*z = %g\n" % (z*z*z*z)
print "\n"

begin
    x = -4.0
    print "[ Test Exception heronSqrt(double) ]--------------------\n"
    print "x = %g\n" % x
    print "Calculating heronSqrt(%g)\n" % x
    y = heronSqrt(x)
    print "y = heronSqrt(%g) = %g\n" % [x, y]
    print "y*y = %g\n" % (y*y)
    print "\n"
rescue RuntimeError => ex
    print "%s\nCaught some exception in calculating heronSqrt(%g)\n" % [ex, x]
    print "\n"
end

begin
    x = -4.0
    print "[ Test Exception in newtonCbrt(double) ]--------------------\n"
    print "x = %g\n" % x
    print "Calculating newtonCbrt(%g)\n" % x
    y = newtonCbrt(x)
    print "y = newtonCbrt(%g) = %g\n" % [x, y]
    print "y*y*y = %g\n" % (y*y*y)
    print "\n"
rescue RuntimeError => ex
    print "%s\nCaught some exception in calculating newtonCbrtrt(%g)\n" % [ex, x]
    print "\n"
end

print "[ Test calculations by powering ]-----------------------------\n"
x = 200.0
z = newtonNthRoot(10, x)
print "x = %g\n" % x
print "exp(log(x)/10.0) = %g\n" % Math::exp(Math::log(x)/10.0)
print "z = newtonNthRoot(10, x) = newtonNthRoot(10, %g) = %g\n" % [x, z]
print "pow(z, 10) = %g\n" % z**10
print "\n"

x = 3001.0
z = newtonNthRoot(99, x)
print "x = %g\n" % x
print "exp(log(x)/99.0) = %g\n" % Math::exp(Math::log(x)/99.0)
print "z = newtonNthRoot(99, x) = newtonNthRoot(99, %g) = %g\n" % [x, z]
print "pow(z, 99) = %g\n" % z**99
print "\n"

x = 3001.0
z = newtonNthRoot(-99, x)
print "x = %g\n" % x
print "exp(log(x)/-99.0) = %g\n" % Math::exp(Math::log(x)/-99.0)
print "z = newtonNthRoot(-99, x) = newtonNthRoot(-99, %g) = %g\n" % [x, z]
print "1.0/pow(z, 99) = %g\n" % (1.0/z**99)
print "\n"

print "2.1**2.1 = pow(2.1, 2.1) = %g\n" % 2.1**2.1
print "2.1**(-2.1) = pow(2.1, -2.1) = %g\n" % 2.1**(-2.1)
print "2.1**2.1 * 2.1**(-2.1) = pow(2.1, 2.1) * pow(2.1, -2.1) = %g\n" % ((2.1** 2.1)*2.1**( -2.1))
print "2.1**2.1 = exp(2.1*log(2.1)) = %g\n" % Math::exp(2.1*Math::log(2.1))
print "2.1**(-2.1) = exp(-2.1*log(2.1)) = %g\n" % Math::exp(-2.1*Math::log(2.1))
print "2.1**2.1 * 2.1**(-2.1) = exp(2.1*log(2.1)) * exp(-2.1*log(2.1)) = %g\n" % (Math::exp(2.1*Math::log(2.1)) * Math::exp(-2.1*Math::log(2.1)))
print "\n"

k = 301
x = -1.029
t1 = nPow(x, k)
t2 = gPow(x, k)
t3 = mPow(x, k)
print "math.pow(%g, %d) = %g\n" % [x, k,  x**k ]   # pow(x, k)
print "t1 = nPow(%g, %d) = %g\n" % [x, k,  t1]
print "t2 = gPow(%g, %d) = %g\n" % [x, k,  t2]
print "t3 = mPow(%g, %d) = %g\n" % [x, k,  t3]
print "t1 / t2 = %g\n" % (t1 / t2)
print "t1 - t2 = %g\n" % (t1 - t2)
print "t1 == t2 ? "
if t1 == t2
    print "yes\n"
else
   print "no\n"
end
print "t1 / t3 = %g\n" % (t1 / t3)
print "t1 - t3 = %g\n" % (t1 - t3)
print "t1 == t3 ? "
if t1 == t3
    print "yes\n"
else
   print "no\n"
end
print "t2 / t3 = %g\n" % (t2 / t3)
print "t2 - t3 = %g\n" % (t2 - t3)
print "t2 == t3 ? "
if t2 == t3
    print "yes\n"
else
   print "no\n"
end
print "\n"

print "Done.\n"

=begin
Output:
[ Testing heronSqrt(double) ]--------------------
x = 16
u = sqrt(16) = 4
y = heronSqrt(16) = 4
y*y = 16

[ Testing newtonCbrt(double) ]--------------------
x = -216
-exp(log(-x)/3.0) = -6
w = newtonCbrt(-216) = -6
w*w*w = -216

x = 7.29e+11
exp(log(x)/3.0) = 9000
w = newtonCbrt(7.29e+11) = 9000
w*w*w = 7.29e+11

[ Testing newtonNthRoot(int, double) ]--------------------
x = 7.29e+11
z = newtonNthRoot(3, 7.29e+11) = 9000
z*z*z = 7.29e+11

x = 1.296e+19
z = newtonNthRoot(4, x) = newtonNthRoot(4, 1.296e+19) =  60000
z*z*z*z = 1.296e+19

x = 7.71605e-20
exp(log(x)/4.0) = 1.66667e-05
z = newtonNthRoot(4, x) = newtonNthRoot(4, 7.71605e-20) =  1.66667e-05
z*z*z*z = 7.71605e-20

[ Test Exception heronSqrt(double) ]--------------------
x = -4
Calculating heronSqrt(-4)
Cannot find the sqrt of a negative number.
Caught some exception in calculating heronSqrt(-4)

[ Test Exception in newtonCbrt(double) ]--------------------
x = -4
Calculating newtonCbrt(-4)
y = newtonCbrt(-4) = -1.5874
y*y*y = -4

[ Test calculations by powering ]-----------------------------
x = 200
exp(log(x)/10.0) = 1.69865
z = newtonNthRoot(10, x) = newtonNthRoot(10, 200) = 1.69865
pow(z, 10) = 200

x = 3001
exp(log(x)/99.0) = 1.08424
z = newtonNthRoot(99, x) = newtonNthRoot(99, 3001) = 1.08424
pow(z, 99) = 3001

x = 3001
exp(log(x)/-99.0) = 0.922308
z = newtonNthRoot(-99, x) = newtonNthRoot(-99, 3001) = 0.922308
1.0/pow(z, 99) = 3001

2.1**2.1 = pow(2.1, 2.1) = 4.74964
2.1**(-2.1) = pow(2.1, -2.1) = 0.210542
2.1**2.1 * 2.1**(-2.1) = pow(2.1, 2.1) * pow(2.1, -2.1) = 1
2.1**2.1 = exp(2.1*log(2.1)) = 4.74964
2.1**(-2.1) = exp(-2.1*log(2.1)) = 0.210542
2.1**2.1 * 2.1**(-2.1) = exp(2.1*log(2.1)) * exp(-2.1*log(2.1)) = 1

math.pow(-1.029, 301) = -5457.93
t1 = nPow(-1.029, 301) = -5457.93
t2 = gPow(-1.029, 301) = -5457.93
t3 = mPow(-1.029, 301) = -5457.93
t1 / t2 = 1
t1 - t2 = 6.18456e-11
t1 == t2 ? no
t1 / t3 = 1
t1 - t3 = 6.18456e-11
t1 == t3 ? no
t2 / t3 = 1
t2 - t3 = 0
t2 == t3 ? yes

Done.
=end