n = 2 인 경우에는 Newton-Raphson 의 방법이 Heron 의 방법과 동일하다.
F# 언어에는 System 모듈에 지수 계산 함수 Math.Pow(double, double) 를 불러서 사용하면 된다. 하지만 차후 필요한 데가 있을 것 같아서 이와 유사한 n 제곱 함수와 n 제곱근 함수를 구현해 보았다.
지수가 정수인 거듭제곱을 계산하는 함수도 nPow(), gPow, mPow() 세 개 구현해 놓았는데, 이들 세 함수는 절차적 언어의 성능상 재귀호출이 아니고 단순 반복 기법을 사용하는 함수이다. 이 세 함수 중 mPow() 의 성능이 가장 우수하다. 큰 지수의 경우 for 반복문의 반복회수를 따져 보면 성능 비교를 할 수 있을 것이다. (성능 비교를 위해 세 가지를 모두 소스에 남겨 두었다.) mPow() 함수는 n 제곱근을 구하는 재귀함수 newtonNthRoot(int, double) 의 구현에 사용되기도 한다. if ... else ... 구문이 많아 소스가 복잡하게 보일지 모르겠으나 이는 밑수나 지수가 음수이거나 0인 경우의 처리를 위함이다. 구현된 모든 함수의 구현에는 예외상황(예를 들어, 음수의 짝수 제곱근 같은 예외상황) 처리 과정이 있다.
하지만, 아래의 소스에서는 함수형 언어의 기능은 거의 사용하지 않앗고, 절차적 언어의 기능을 위주로 사용하였다. 하나의 함수를 구현하는데 함수형 기능과 절차적 기능을 섞어서 사용하는 것은 좋지 않은 습관이다.
라고 선언하였으니, MAX_ITER 와 M_EPSILON 는 상수로 선언되었다.
(*
* Filename: testNthRoot.fs
*
* Approximate square roots, cubic roots and n-th roots of a given number.
*
* Compile: fsc --codepage:949 testNthRoot.fs
* Execute: testNthRoot
*
* Date: 2013. 1. 7.
* Copyright (c) 2013 PH Kim (pkim __AT__ scripts.pe.kr)
*)
# light
let MAX_ITER = 20000
let M_EPSILON = 1.0e-15
//
// Compute the n-th root of x to a given scale, x > 0.
//
let rec nPow(a: double, n: int) : double =
if n > 0 then
if n = 1 then
a
else
if a = 0.0 || a = 1.0 then
a
elif a = -1.0 then
if n % 2 = 1 then
-1.0
else
1.0
elif a < 0.0 then
if n % 2 = 1 then
-nPow(-a, n)
else
nPow(-a, n)
else
let mutable y = 1.0
for i = 1 to n do
y <- y * a
y
elif n = 0 then
1.0
else // when n < 0
if a = 0.0 then
raise (new System.InvalidOperationException("Negative powering exception of zero."))
else
if n = -1 then
1.0/a
else
1.0/nPow(a, -n)
//
// Compute the n-th root of x to a given scale, x > 0.
//
let rec gPow(a: double, n: int) : double =
if n > 0 then
if n = 1 then
a
else
if a = 0.0 || a = 1.0 then
a
elif a = -1.0 then
if n % 2 = 1 then
-1.0
else
1.0
elif a < 0.0 then
if n % 2 = 1 then
-gPow(-a, n)
else
gPow(-a, n)
else
let mutable y = 1.0
let mutable r = a
let mutable m = 8*4 - 1 // 8*sizeof(int) - 1;
let mutable one = 1
for i = 0 to m do
if (n &&& one) = 0 then
y <- y * 1.0
else
y <- y * r
r <- r*r
one <- (one <<< 1)
y
elif n = 0 then
1.0
else // when n < 0
if a = 0.0 then
raise (new System.InvalidOperationException("Negative powering exception of zero."))
else
if n = -1 then
1.0/a
else
1.0/gPow(a, -n)
//
// Compute the n-th root of x to a given scale, x > 0.
//
let rec mPow(a: double, n: int) : double =
if n > 0 then
if n = 1 then
a
else
if a = 0.0 || a = 1.0 then
a
elif a = -1.0 then
if n % 2 = 1 then
-1.0
else
1.0
elif a < 0.0 then
if n % 2 = 1 then
-mPow(-a, n)
else
mPow(-a, n)
else
let mutable y = 1.0
let mutable r = a
let mutable m = n
while m > 0 do
if (m &&& 0x1) = 1 then
y <- y * r
r <- r*r
m <- (m >>> 1)
y
elif n = 0 then
1.0
else // when n < 0
if a = 0.0 then
raise (new System.InvalidOperationException("Negative powering exception of zero."))
else
if n = -1 then
1.0/a
else
1.0/mPow(a, -n)
//
// Compute the square root of x to a given scale, x > 0.
//
let rec heronSqrt(a: double) : double =
if a < 0.0 then
raise (new System.InvalidOperationException("Cannot find the sqrt of a negative number."))
elif a = 0.0 || a = 1.0 then
a
else
let mutable x1 = a
let mutable x2 = (x1 + a/x1)/2.0
let mutable er = x1 - x2
let mutable counter = 0
let mutable not_stop = true
while x1 + er <> x1 && not_stop do
x1 <- x2
x2 <- (x1 + a/x1)/2.0
er <- x1 - x2
if abs(er) < abs(M_EPSILON*x1) then
not_stop <- false
counter <- counter + 1
if counter > MAX_ITER then
not_stop <- false
if counter >= MAX_ITER then
raise (new System.InvalidOperationException("Inaccurate sqrt exception by too many iterations."))
x2
//
// Compute the cubic root of x to a given scale, x > 0.
//
let rec newtonCbrt(a: double) : double =
if a = 0.0 || a = 1.0 || a = -1.0 then
a
elif a < 0.0 then
-newtonCbrt(-a)
else
let mutable x1 = a
let mutable x2 = (2.0*x1 + a/(x1*x1))/3.0
let mutable er = x1 - x2
let mutable counter = 0
let mutable not_stop = true
while x1 + er <> x1 && not_stop do
x1 <- x2
x2 <- (2.0*x1 + a/(x1*x1))/3.0
er <- x1 - x2
if abs(er) < abs(M_EPSILON*x1) then
not_stop <- false
counter <- counter + 1
if counter > MAX_ITER then
not_stop <- false
if counter >= MAX_ITER then
raise (new System.InvalidOperationException("Inaccurate cbrt exception by too many iterations."))
x2
//
// Compute the n-th root of x to a given scale, x > 0.
//
let rec newtonNthRoot(n: int, a: double) : double =
if n = 0 then
1.0
elif n = 1 then
a
elif n > 0 then
if a = 0.0 || a = 1.0 then
a
elif a = -1.0 then
if n % 2 = 1 then
a
else
raise (new System.InvalidOperationException("Cannot find the even n-th root of a negative number."))
elif a < 0.0 then
if n % 2 = 1 then
-newtonNthRoot(n, -a)
else
raise (new System.InvalidOperationException("Cannot find the n-th root of a negative number."))
elif a < 1.0 then
1.0/newtonNthRoot(n, 1.0/a)
else
let mutable x1 = a
let mutable xn = mPow(x1, n - 1)
let mutable x2 = ((double n - 1.0)*x1 + a/xn)/(double n)
let mutable er = x1 - x2
let mutable counter = 0
let mutable not_stop = true
while x1 + er <> x1 && not_stop do
x1 <- x2
xn <- mPow(x1, n - 1)
x2 <- ((double n - 1.0)*x1 + a/xn)/(double n)
er <- x1 - x2
if abs(er) < abs(M_EPSILON*x1) then
not_stop <- false
counter <- counter + 1
if counter > MAX_ITER then
not_stop <- false
if counter >= MAX_ITER then
raise (new System.InvalidOperationException("Inaccurate n-th root exception by too many iterations."))
x2
else
if a = 0.0 then
raise (new System.InvalidOperationException("Cannot find the negative n-th root of zero."))
else
1.0/newtonNthRoot(-n, a)
let mutable x = 16.0
let mutable u = System.Math.Sqrt(x)
printfn "[ Testing heronSqrt(double) ]--------------------"
printfn "x = %g" x
printfn "u = sqrt(%g) = %g" x u
let mutable y = heronSqrt(x)
printfn "y = heronSqrt(%g) = %g" x y
printfn "y*y = %g" (y*y)
printfn ""
x <- 729000000000.0
printfn "x = %g" x
printfn "exp(log(x)/3.0) = %g" (System.Math.Exp (System.Math.Log x)/3.0)
let mutable w = (newtonCbrt x)
printfn "w = newtonCbrt(%g) = %g" x w
printfn "w*w*w = %g" (w*w*w)
printfn ""
printfn "[ Testing newtonNthRoot(int, double) ]--------------------"
let mutable z = newtonNthRoot(3, x)
printfn "x = %g" x
printfn "z = newtonNthRoot(3, %g) = %g" x z
printfn "z*z*z = %g" (z*z*z)
printfn ""
x <- 12960000000000000000.0
z <- newtonNthRoot(4, x)
printfn "x = %g" x
printfn "z = newtonNthRoot(4, x) = newtonNthRoot(4, %g) = %g" x z
printfn "z*z*z*z = %g" (z*z*z*z)
printfn ""
x <- 1.0/12960000000000000000.0
z <- newtonNthRoot(4, x)
printfn "x = %g" x
printfn "exp(log(x)/4.0) = %g" (System.Math.Exp (System.Math.Log x)/4.0)
printfn "z = newtonNthRoot(4, x) = newtonNthRoot(4, %g) = %g" x z
printfn "z*z*z*z = %g" (z*z*z*z)
printfn ""
try
x <- -4.0
printfn "[ Test Exception heronSqrt(double) ]--------------------"
printfn "x = %g" x
printfn "Calculating heronSqrt(%g)" x
y <- heronSqrt(x)
printfn "y = heronSqrt(%g) = %g" x y
printfn "y*y = %g" (y*y)
printfn ""
with
| err -> printfn "%s\nCaught some exception in calculating heronSqrt(%g)" err.Message x
printfn ""
try
x <- -4.0
printfn "[ Test Exception newtonCbrt(double) ]--------------------"
printfn "x = %g" x
printfn "Calculating newtonCbrt(%g)" x
y <- newtonCbrt(x)
printfn "y = newtonCbrt(%g) = %g" x y
printfn "y*y*y = %g" (y*y*y)
printfn ""
with
| err -> printfn "%s\nCaught some exception in calculating newtonCbrtrt(%g)" err.Message x
printfn ""
printfn "[ Test calculations by powering ]-----------------------------"
x <- 200.0
z <- newtonNthRoot(10, x)
printfn "x = %g" x
printfn "exp(log(x)/10.0) = %g" ((System.Math.Exp (System.Math.Log x))/10.0)
printfn "z = newtonNthRoot(10, x) = newtonNthRoot(10, %g) = %g" x z
printfn "z**10.0 = pow(z, 10.0) = %g" (z**10.0)
printfn ""
x <- 3001.0
z <- newtonNthRoot(99, x)
printfn "x = %g" x
printfn "exp(log(x)/99.0) = %g" (System.Math.Exp(System.Math.Log(x)/99.0))
printfn "z = newtonNthRoot(99, x) = newtonNthRoot(99, %g) = %g" x z
printfn "z**99.0 = pow(z, 99) = %g" (z**99.0)
printfn ""
x <- 3001.0
z <- newtonNthRoot(-99, x)
printfn "x = %g" x
printfn "exp(log(x)/-99.0) = %g" (System.Math.Exp(System.Math.Log(x)/(-99.0)))
printfn "z = newtonNthRoot(-99, x) = newtonNthRoot(-99, %g) = %g" x z
printfn "1.0/z**99.0 = 1.0/pow(z, 99) = %g" (1.0/z**99.0)
printfn ""
printfn "2.1**2.1 = pow(2.1, 2.1) = %g" (2.1**2.1)
printfn "2.1**(-2.1) = pow(2.1, -2.1) = %g" (2.1**(-2.1))
printfn "2.1**2.1 * 2.1**(-2.1) = pow(2.1, 2.1) * pow(2.1, -2.1) = %g" (2.1**2.1 * 2.1**(-2.1))
printfn "2.1**2.1 = exp(2.1*log(2.1)) = %g" (System.Math.Exp(2.1*System.Math.Log(2.1)))
printfn "2.1**(-2.1) = exp(-2.1*log(2.1)) = %g" (System.Math.Exp(-2.1*System.Math.Log(2.1)))
printfn "2.1**2.1 * 2.1**(-2.1) = exp(2.1*log(2.1)) * exp(-2.1*log(2.1)) = %g" (2.1**2.1 * 2.1**(-2.1))
printfn ""
let mutable k = 301
x <- -1.029
let mutable t1 = nPow(x, k)
let mutable t2 = gPow(x, k)
let mutable t3 = mPow(x, k)
let mutable tt = System.Math.Pow(x, double k)
printfn "System.Math.Pow(%g, %d) = %g" x k tt
printfn "t1 = nPow(%g, %d) = %g" x k t1
printfn "t2 = gPow(%g, %d) = %g" x k t2
printfn "t3 = mPow(%g, %d) = %g" x k t3
printfn "t1 / t2 = %g" (t1 / t2)
printfn "t1 - t2 = %g" (t1 - t2)
printf "t1 == t2 ? "
if t1 = t2 then printfn "yes"
else printfn "no"
printfn "t1 / t3 = %g" (t1 / t3)
printfn "t1 - t3 = %g" (t1 - t3)
printf "t1 == t3 ? "
if t1 = t3 then printfn "yes"
else printfn "no"
printfn "t2 / t3 = %g" (t2 / t3)
printfn "t2 - t3 = %g" (t2 - t3)
printf "t2 == t3 ? "
if t2 = t3 then printfn "yes"
else printfn "no"
printfn ""
printfn "Done."
(*
Output:
[ Testing heronSqrt(double) ]--------------------
x = 16
u = sqrt(16) = 4
y = heronSqrt(16) = 4
y*y = 16
x = 7.29e+11
exp(log(x)/3.0) = 2.43e+11
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.92901e-20
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 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) = 20
z = newtonNthRoot(10, x) = newtonNthRoot(10, 200) = 1.69865
z**10.0 = pow(z, 10.0) = 200
x = 3001
exp(log(x)/99.0) = 1.08424
z = newtonNthRoot(99, x) = newtonNthRoot(99, 3001) = 1.08424
z**99.0 = pow(z, 99) = 3001
x = 3001
exp(log(x)/-99.0) = 0.922308
z = newtonNthRoot(-99, x) = newtonNthRoot(-99, 3001) = 0.922308
1.0/z**99.0 = 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
System.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.
*)