OCaml 언어 소스:

(*
   Filename: testHexView_02.ml
 
   Execute: ocaml testHexView_02.ml [filename]

     Or
 
   Compile: ocamlc -o testHexView_02 testHexView_02.ml
   Execute: ./testHexView_02 [filename]
 
     Or
 
   Compile: ocamlc -o testHexView_02.exe testHexView_02.ml
   Execute: testHexView_02 [filename]
 
   Date: 2013. 8. 20.
*)

open Printf;;

let printUsage() =
    printf("Usgae: testHexView_02 [filename]\n");;

let toHex n =
    let s = ref "" in
    let x1 = (n land 0xF0) lsr 4 in
    let x2 = n land 0xF in
    if x1 < 10 then
        s := !s ^ Char.escaped (Char.chr( Char.code('0') + x1 ))
    else
        s := !s ^ Char.escaped (Char.chr( Char.code('A') + (x1 - 10) ));
    if x2 < 10 then
        s := !s ^ Char.escaped (Char.chr( Char.code('0') + x2 ))
    else
        s := !s ^ Char.escaped (Char.chr( Char.code('A') + (x2 - 10) ));
    !s


let toHex8 n =
    let s = ref "" in
    (* let x1 = (n land 0xF0000000) lsr 28 in *)
    let x1 = (n land 0x70000000) lsr 28 in
    let x2 = (n land 0xF000000) lsr 24 in
    let x3 = (n land 0xF00000) lsr 20 in
    let x4 = (n land 0xF0000) lsr 18 in
    let x5 = (n land 0xF000) lsr 12 in
    let x6 = (n land 0xF00) lsr 8 in
    let x7 = (n land 0xF0) lsr 4 in
    let x8 = n land 0xF in
    if x1 < 10 then
        s := !s ^ Char.escaped (Char.chr( Char.code('0') + x1 ))
    else
        s := !s ^ Char.escaped (Char.chr( Char.code('A') + (x1 - 10) ));
    if x2 < 10 then
        s := !s ^ Char.escaped (Char.chr( Char.code('0') + x2 ))
    else
        s := !s ^ Char.escaped (Char.chr( Char.code('A') + (x2 - 10) ));
    if x3 < 10 then
        s := !s ^ Char.escaped (Char.chr( Char.code('0') + x3 ))
    else
        s := !s ^ Char.escaped (Char.chr( Char.code('A') + (x3 - 10) ));
    if x4 < 10 then
        s := !s ^ Char.escaped (Char.chr( Char.code('0') + x4 ))
    else
        s := !s ^ Char.escaped (Char.chr( Char.code('A') + (x4 - 10) ));
    s := !s ^ " ";
    if x5 < 10 then
        s := !s ^ Char.escaped (Char.chr( Char.code('0') + x5 ))
    else
        s := !s ^ Char.escaped (Char.chr( Char.code('A') + (x5 - 10) ));
    if x6 < 10 then
        s := !s ^ Char.escaped (Char.chr( Char.code('0') + x6 ))
    else
        s := !s ^ Char.escaped (Char.chr( Char.code('A') + (x6 - 10) ));
    if x7 < 10 then
        s := !s ^ Char.escaped (Char.chr( Char.code('0') + x7 ))
    else
        s := !s ^ Char.escaped (Char.chr( Char.code('A') + (x7 - 10) ));
    if x8 < 10 then
        s := !s ^ Char.escaped (Char.chr( Char.code('0') + x8 ))
    else
        s := !s ^ Char.escaped (Char.chr( Char.code('A') + (x8 - 10) ));
    !s

let load_file f =
  let ic = open_in f in
  let n = in_channel_length ic in
  let s = String.create n in
  really_input ic s 0 n;
  close_in ic;
  (s);;

 

if Array.length Sys.argv < 2 then begin
    printUsage() ;
    exit 1
end;

let fname = Sys.argv.(1) in

if not (Sys.file_exists fname) then begin
    printf "The file \"%s\" does not exist.\n" fname;
    exit 1
end;

if (Sys.is_directory fname) then begin
    printf "\"%s\" is a directory.\n" fname;
    exit 1
end;

let dum = ref "" in
let bstr = load_file Sys.argv.(1) in 
let fsize = String.length bstr in 

printf "The size of the file \"%s\" is %d.\n" fname fsize;
print_newline();


let n = ref 0 in
while (!n < fsize) do
    if (!n mod 16) == 0 then begin
        printf  "%s: " (toHex8 !n)
    end;
    let c = bstr.[!n] in
    (* print_char c   *)
    if (!n mod 16) == 8 then
        printf  "-%s" (toHex (Char.code c))
    else
        printf  " %s" (toHex (Char.code c));
    if (Char.code c) < (Char.code ' ') or (Char.code c) > 0x7F then
        dum := !dum ^ "."
    else
        dum := !dum ^ (Char.escaped c);
    if (!n mod 16) == 15 then begin
        printf  "  |%s|\n" !dum;
        dum := ""
    end;
    n := !n + 1;
done;

if (!n mod 16) > 0 then begin
    for i = 0 to (pred (16 - (!n mod 16))) do
        printf  "   "
    done;
    printf  "  |%s" !dum;
    for i = 0 to (pred (16 - (!n mod 16))) do
        printf  " "
    done;
    printf  "|\n";
    dum := ""
end;

print_newline();
printf "Read %d bytes.\n" !n;

 

 

실행 예 1> testHexView_02 temp_1.bin
The size of the file "temp_1.bin" is 12.

0000 0000:  48 65 6C 6C 6F 20 74 68-65 72 65 0A              |Hello there.    |

Read 12 bytes.

실행 예 2> testHexView_02 myFile.ser
The size of the file "myFile.ser" is 130.

0000 0000:  AC ED 00 05 73 72 00 06-50 65 72 73 6F 6E 07 31  |....sr..Person.1|
0000 0010:  46 DB A5 1D 44 AB 02 00-03 49 00 03 61 67 65 4C  |F...D....I..ageL|
0000 0020:  00 09 66 69 72 73 74 4E-61 6D 65 74 00 12 4C 6A  |..firstNamet..Lj|
0000 0030:  61 76 61 2F 6C 61 6E 67-2F 53 74 72 69 6E 67 3B  |ava/lang/String;|
0000 0040:  4C 00 08 6C 61 73 74 4E-61 6D 65 71 00 7E 00 01  |L..lastNameq.~..|
0000 0050:  78 70 00 00 00 13 74 00-05 4A 61 6D 65 73 74 00  |xp....t..Jamest.|
0000 0060:  04 52 79 61 6E 73 71 00-7E 00 00 00 00 00 1E 74  |.Ryansq.~......t|
0000 0070:  00 07 4F 62 69 2D 77 61-6E 74 00 06 4B 65 6E 6F  |..Obi-want..Keno|
0000 0080:  62 69                                            |bi              |

Read 130 bytes.

 

 

Posted by Scripter
,

수학에서 집합을 표현하는 방법에는 열거형 표현법과 진술형 표현법으로 나뉘어진다.

{ 3, 7, 10, 14 } 는  열거형 표현이고,

{ y | y = n + 2n + [n/2] where n = 1, 2, 3, 4 } 는 진술형 표현이다. (단 여기서 [x] 는 가우스 기호)

(참고로 아래의 구문에서 기호 <- 는 집함의 원소 기호 ∈ 와 유사함을 염두에 두자.)

 

Haskell 언어에는 (집합의 진술형 표현과 유사한) Prelude 에서 기본적으로 제공되는 리스트 생성 구문이 있다.

명령 프롬프트> ghci
GHCi, version 7.4.2: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> [ x + 2*x + (div x 2) | x <- [1, 2, 3, 4] ]
[3,7,10,14]

 

OCaml 언어에는 저런 구문이 기본적으로 제공되지 않는다. 하지만 OCaml 언어로도 특별한 라이브러리를 쓰면 저렇게 편리하게 리스트를 생성할 수 있다. dynlink.cma 와 camlp4oof.cma 라이브러리를 쓰면 된다. cygwin 의 경우에는

     export OCAMLLIB=/lib/ocaml

을 미리해두어야 한다. (안 그러면  윈도우에 설치된 OCaml 의 라이브러리와 충돌이 난다.)

 

명령 프롬프트> ocaml dynlink.cma camlp4oof.cma
        Objective Caml version 3.12.1

        Camlp4 Parsing version 3.12.1

# [x + 2*x + x/2 | x <- [1; 2; 3; 4]];;
- : int list = [3; 7; 10; 14]

 

Haskell 언어로 3x3 Hilbert 행렬의 제곱을 계산해 보자.

명령 프롬프트> ghci
GHCi, version 7.4.2: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> import Data.Ratio
Prelude Data.Ratio> let a = [1, 2, 3]
Prelude Data.Ratio> let hilb3 = [ [ 1 % (i + j - 1) | i <- a ] | j <- a ]
Prelude Data.Ratio> hilb3
[[1 % 1,1 % 2,1 % 3],[1 % 2,1 % 3,1 % 4],[1 % 3,1 % 4,1 % 5]]
Prelude Data.Ratio> import Data.List
Prelude Data.Ratio Data.List> transpose hilb3
[[1 % 1,1 % 2,1 % 3],[1 % 2,1 % 3,1 % 4],[1 % 3,1 % 4,1 % 5]]
Prelude Data.Ratio Data.List> let mmult a b = [ [ sum $ zipWith (*) ar bc | bc <
- (transpose b) ] | ar <- a ]
Prelude Data.Ratio Data.List> mmult hilb3 hilb3
[[49 % 36,3 % 4,21 % 40],[3 % 4,61 % 144,3 % 10],[21 % 40,3 % 10,769 % 3600]]
Prelude Data.Ratio Data.List>

 

이제는 OCaml 언어로 3x3 Hilbert 행렬의 제곱을 계산해 보자.

명령 프롬프트> ocaml dynlink.cma camlp4oof.cma
        Objective Caml version 3.12.1

        Camlp4 Parsing version 3.12.1

let rec transpose list = match list with
    | []             -> []
    | []   :: xss    -> transpose xss
    | (x::xs) :: xss ->
        (x :: List.map List.hd xss) :: transpose (xs :: List.map List.tl xss) ;;
val transpose : 'a list list -> 'a list list = <fun>
# transpose [ [2; 3]; [1; 5] ] ;;
- : int list list = [[2; 1]; [3; 5]]
# let sum list = List.fold_left (+) 0 list ;;
val sum : int list -> int = <fun>
# sum [1; 2; 3] ;;
- : int = 6
# #load "nums.cma" ;;
# 2/3 ;;
- : int = 0
# open Num ;;
# num_of_string "2/3" ;;
- : Num.num = Ratio <abstr>
# let sum list = List.fold_left ( +/ ) (num_of_int 0) list ;;
val sum : Num.num list -> Num.num = <fun>
let v = List.map num_of_string [ "1/2"; "1/3" ] ;;
val v : Num.num list = [Ratio <abstr>; Ratio <abstr>]
# sum v ;;
- : Num.num = Ratio <abstr>
# string_of_num (sum v) ;;
- : string = "5/6"
let rec zipWith f l1 l2 =
         match (l1, l2) with
           ([], _) -> []
         | (_, []) -> []
         | (x1 :: rl1, x2 :: rl2) -> (f x1 x2) :: (zipWith f rl1 rl2) ;;
val zipWith : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list = <fun>
# let mmult a b = [ [ sum (zipWith ( */ ) ar bc) | bc <- (transpose b) ] | ar <- a ]  ;;
val mmult : Num.num list list -> Num.num list list -> Num.num list list =
  <fun>
# let a = [1; 2; 3] ;;
val a : int list = [1; 2; 3]
# let hilb3 = [ [ (num_of_int 1) // (num_of_int  (i +  j - 1)) | i <- a ] | j <- a ] ;;
val hilb3 : Num.num list list =
  [[Int 1; Ratio <abstr>; Ratio <abstr>];
   [Ratio <abstr>; Ratio <abstr>; Ratio <abstr>];
   [Ratio <abstr>; Ratio <abstr>; Ratio <abstr>]]
# string_of_num (List.nth (List.nth hilb3 2) 2) ;;
- : string = "1/5"
# let matB = mmult hilb3 hilb3 ;;
val matB : Num.num list list =
  [[Ratio <abstr>; Ratio <abstr>; Ratio <abstr>];
   [Ratio <abstr>; Ratio <abstr>; Ratio <abstr>];
   [Ratio <abstr>; Ratio <abstr>; Ratio <abstr>]]
# open Printf ;;
# let print_vector v = List.iter (fun x -> printf "%s, " (string_of_num x)) v ;;
val print_vector : Num.num list -> unit = <fun>
# print_vector (List.nth hilb3 2) ;;
1/3, 1/4, 1/5, - : unit = ()
# let print_matrix m = List.iter (fun x -> print_vector x; print_newline()) m ;;
val print_matrix : Num.num list list -> unit = <fun>
# print_matrix hilb3 ;;
1, 1/2, 1/3,
1/2, 1/3, 1/4,
1/3, 1/4, 1/5,
- : unit = ()
# print_matrix matB ;;
49/36, 3/4, 21/40,
3/4, 61/144, 3/10,
21/40, 3/10, 769/3600,
- : unit = ()
# #quit ;;

 

F# 언어로는 부동소수점수로 3x3 Hilber 행렬의 제곱을 계산해 보았다.

명령프롬프트> fsi

Microsoft (R) F# 2.0 Interactive 빌드 4.0.40219.1
Copyright (c) Microsoft Corporation. 모든 권리 보유.

도움말을 보려면 #help;;를 입력하십시오.

> let array3 = [| for i in 1 .. 10 -> i * i |] ;;

val array3 : int [] = [|1; 4; 9; 16; 25; 36; 49; 64; 81; 100|]

> let a = [ 1..3 ] ;;

val a : int list = [1; 2; 3]

> let hilb3 = [ for i in a -> [ for j in a -> 1.0/(float (i + j - 1)) ] ] ;;

val hilb3 : float list list =
  [[1.0; 0.5; 0.3333333333]; [0.5; 0.3333333333; 0.25];
   [0.3333333333; 0.25; 0.2]]

> let sum list = List.fold ( + ) (0.0) list ;;

val sum : float list -> float

> sum [5.0; 2.1] ;;
val it : float = 7.1
> let rec zipWith f l1 l2 =
      match (l1, l2) with
         ([], _) -> []
       | (_, []) -> []
      | (x1 :: rl1, x2 :: rl2) -> (f x1 x2) :: (zipWith f rl1 rl2) ;;

val zipWith : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list

> let mmult a b = [ for ar in a -> [ for bc in b -> sum (zipWith ( * ) ar bc) ] ] ;;

val mmult : seq<float list> -> seq<float list> -> float list list

> let matB = mmult hilb3 hilb3 ;;

val matB : float list list =
  [[1.361111111; 0.75; 0.525]; [0.75; 0.4236111111; 0.3];
   [0.525; 0.3; 0.2136111111]]

> #quit ;;

 

 

또 다음은 F# 의 PowerPack.dll 라이브리의 BigRational 을 이영하여 3x3 Hilbert 행렬의 제곱을 계산하는 과정이다.

명령 프롬프트> fsi

Microsoft (R) F# 2.0 Interactive 빌드 4.0.40219.1
Copyright (c) Microsoft Corporation. 모든 권리 보유.

도움말을 보려면 #help;;를 입력하십시오.

> #r "FSharp.PowerPack.dll" ;;

--> 'C:\test\f#\FSharp.PowerPack.dll'이(가) 참조되었습니다.

> let r = (1N/2N) * (1N/3N) ;; // 1/6
세션을 'C:\test\f#\FSharp.PowerPack.dll'에 바인딩하는 중...

val r : BigRational = 1/6N

> let sum list = List.fold ( + ) (0N) list ;;

val sum : BigRational list -> BigRational

> sum [5N; 2N/3N] ;;
val it : BigRational = 17/3N
> bigint 2;;
val it : System.Numerics.BigInteger = 2 {IsEven = true;
                                         IsOne = false;
                                         IsPowerOfTwo = true;
                                         IsZero = false;
                                         Sign = 1;}
> open System ;;
> open System.Numerics ;;
> BigRational.FromInt 5 ;;
val it : BigRational = 5N
> let a = [ 1..3 ] ;;

val a : int list = [1; 2; 3]

> let hilb3 = [ for i in a -> [ for j in a -> 1N/(BigRational.FromInt (i + j - 1
- )) ] ] ;;

val hilb3 : BigRational list list =
  [[1N; 1/2N; 1/3N]; [1/2N; 1/3N; 1/4N]; [1/3N; 1/4N; 1/5N]]

> let rec zipWith f l1 l2 =
       match (l1, l2) with
         ([], _) -> []
       | (_, []) -> []
       | (x1 :: rl1, x2 :: rl2) -> (f x1 x2) :: (zipWith f rl1 rl2) ;;

val zipWith : ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list

let mmult a b = [ for ar in a -> [ for bc in b -> sum (zipWith ( * ) ar bc) ]
- ] ;;

val mmult :
  seq<BigRational list> -> seq<BigRational list> -> BigRational list list

let matB = mmult hilb3 hilb3 ;;

val matB : BigRational list list =
  [[49/36N; 3/4N; 21/40N]; [3/4N; 61/144N; 3/10N]; [21/40N; 3/10N; 769/3600N]]

> #quit ;;


 

Posted by Scripter
,

음이 아닌 실수 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 )

 

OCaml 언어에는 부동소수점수의 지수연산자 ** 가 있다. 하지만 차후 필요한 데가 있을 것 같아서 이와 유사한 n 제곱 함수와 n 제곱근 함수를 구현해 보았다.

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

 

1. OCaml 언어는 (절차적 프로그래밍도 지원하는) 함수형 언어이다.

   하지만, 아래의 소스에서는 함수형 언어의 기능은 거의 사용하지 않앗고, 절차적 언어의 기능을 위주로 사용하였다. 하나의 함수를 구현하는데 함수형 기능과 절차적 기능을 섞어서 사용하는 것은 좋지 않은 습관이다.

2. OCaml 언어는 (C 언어 처럼 소스에 들여쓰기 규칙을 지키지 않는다.

3. OCaml 언어에서는 상수든 변수든 함수든 처음 선언할 때는 구문 선두에 let 예약어를 반드시 붙인다.

     let a = 2.7 in               // a (통용범위가 한정된) 변수
     let b = ref 5.3 in          // b 는 (통용범위가 한정된) 참조 변수 
     let g x = x*x  in           // g 는 (통용범위가 한정된) 함수

아래의 소스 첫 부분에

        let nMAX_ITER = 20000 ;;
        let nM_EPSILON = 1.0e-15 ll

라고 선언하였으니, nMAX_ITER 와 nM_EPSILON 는 (재정의 되지 않는 한) 상수로 사용된다. 상수나 변수명은 대문자로 시작되지 않아야 한다.

4. OCaml 언어에는 return 이라는 예약어가 없다. 그냥 리턴될 값만 수식으로 표현해 놓으면, OCaml 컴파일러 ocamlc(또는 OCaml 대화형 인터프리터 ocaml)가 리턴될 값을 알아서 인식하고 처리해 준다.

5. 예외상황 처리를 위해 예외 던지기 구문 raise ... 과 예외 받기 구문 try ... with ...을 이용하였다. (해당 부분 주석을 제거하면 확인 가능)

6. OCaml 언어에서 부동소수점수의 부호를 반대로 바꾸는 단항 연산자 기호는 - 가 아니고 -. 이다.

 

(*
 * Filename: testNthRoot.ml
 *
 *            Approximate square roots, cubic roots and n-th roots of a given number.
 *
 * Execute: ocaml testNthRoot.ml
 *  Or
 * Compile: ocamlc -o testNthRoot.exe testNthRoot.ml
 * Execute: testNthRoot
 *
 * Date: 2013. 2. 6.
 * Copyright (c) 2013  pkim __AT__ scripts.pe.kr
 *)

open Printf ;;

exception InvalidPower ;;
exception SqrtOfNegative ;;
exception EventhRootOfNegative ;;
exception TooManyInterations ;;

let nMAX_ITER = 20000 ;;
let nM_EPSILON = 1.0e-15 ;;


(*
   Compute the n-th root of x to a given scale, x > 0.
*)
let rec nPow a n =
    if n > 0 then begin
        if n = 1 then
            a
        else begin
            if a = 0.0 or a = 1.0 then
                a
            else if a = -1.0 then begin
                if n mod 2 = 1 then
                    -1.0
                else
                    1.0
            end
            else if a < 0.0 then
                if n mod 2 = 1 then
                    -. (nPow (-. a) n)
                else
                    nPow (-. a) n
            (*
            *)
            else begin
                let y = ref 1.0 in
                for i = 1 to n do
                    y := !y *. a
                done ;
                !y
            end
        end
    end
    else if n = 0 then begin
        1.0
    end
    else begin     (*  when n < 0  *)
        if a = 0.0 then
            raise InvalidPower
        else begin
            if n = -1 then
                1.0 /. a
            else
               1.0 /. (nPow a (-n))
        end
    end ;;
(*
    end
    5.0 ;;
*)

(*
  Compute the n-th root of x to a given scale, x > 0.
*)
let rec gPow a n =
    if n > 0 then
        if n = 1 then
            a
        else
            if a = 0.0 || a = 1.0 then
                a
            else if a = -1.0 then
                if n mod 2 = 1 then
                    -1.0
                else
                    1.0
            else if a < 0.0 then
                if n mod 2 = 1 then
                    -. (gPow (-. a) n)
                else
                    gPow (-.a) n
            else
                let y = ref 1.0 in
                let r = ref (0.0 +. a) in
                let m = 8*4 - 1 in           (*  8*sizeof(int) - 1; *)
                let one = ref 1 in
                for i = 0 to m do
                    if (n land !one) = 0 then
                        y := !y *. 1.0
                    else
                        y := !y *. !r ;
                    r := !r *. !r ;
                    one := (!one lsl 1) ;    (*  one = one << 1  *)
                done ;
                !y
    else if n = 0 then
        1.0
    else      (*  when n < 0  *)
        if a = 0.0 then
            raise InvalidPower
        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 n =
    if n > 0 then
        if n = 1 then
            a
        else
            if a = 0.0 || a = 1.0 then
                a
            else if a = -1.0 then
                if n mod 2 = 1 then
                    -1.0
                else
                    1.0
            else if a < 0.0 then
                if n mod 2 = 1 then
                    -. (mPow (-. a) n)
                else
                    mPow (-. a) n
            else
                let y = ref 1.0 in
                let r = ref (0.0 +. a) in
                let m = ref (0 + n)  in
                while !m > 0 do
                    if (!m land 0x1) = 1 then
                        y := !y *. !r ;
                    r := !r *. !r ;
                    m := (!m lsr 1) ;   (* m <- (m >>> 1) *)
                done ;
                !y
    else if n = 0 then
        1.0
    else      (*  when n < 0  *)
        if a = 0.0 then
            raise InvalidPower
        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 =
    if a < 0.0 then
        raise SqrtOfNegative
    else if a = 0.0 || a = 1.0 then
        a
    else
        let x1 = ref (0.0 +. a) in
        let x2 = ref ((!x1 +. a /. !x1) /. 2.0) in
        let er = ref (!x1 -. !x2) in
        let counter = ref 0 in
        let not_stop = ref true in
        while (((!x1 +. !er) != !x1) && !not_stop) do
            x1 := !x2 ;
            x2 := (!x1 +. a /. !x1) /. 2.0 ;
            er := !x1 -. !x2 ;
            if (abs_float !er) < (abs_float (nM_EPSILON *. !x1)) then
                not_stop := false ;
            counter := !counter + 1 ;
            if !counter > nMAX_ITER then
                not_stop := false ;
        done ;
        if !counter >= nMAX_ITER then
            raise TooManyInterations ;
        !x2 ;;


(*
  Compute the cubic root of x to a given scale, x > 0.
*)
let rec newtonCbrt a =
    if a = 0.0 || a = 1.0 || a = -1.0 then
        a
    else if a < 0.0 then
        -. newtonCbrt (-. a)
    else
        let x1 = ref (0.0 +. a) in
        let x2 = ref ((2.0 *. !x1 +. a /. (!x1 *. !x1)) /. 3.0) in
        let er = ref (!x1 -. !x2) in
        let counter = ref 0 in
        let not_stop = ref true in
        while (!x1 +. !er <> !x1) && !not_stop do
            x1 := !x2 ;
            x2 := (2.0 *. !x1 +. a /. (!x1 *. !x1)) /. 3.0 ;
            er := !x1 -. !x2 ;
            if (abs_float !er) < (abs_float (nM_EPSILON *. !x1)) then
                not_stop := false ;
            counter := !counter + 1 ;
            if !counter > nMAX_ITER then
                not_stop := false
        done ;
        if !counter >= nMAX_ITER then
            raise TooManyInterations ;
        !x2 ;;


(*
  Compute the n-th root of x to a given scale, x > 0.
*)
let rec newtonNthRoot n a =
    if n = 0 then
        1.0
    else if n = 1 then
        a
    else if n > 0 then
        if a = 0.0 || a = 1.0 then
            a
        else if a = -1.0 then
            if n mod 2 = 1 then
                a
            else
                raise EventhRootOfNegative
        else if a < 0.0 then
            if n mod 2 = 1 then
                -. (newtonNthRoot n (-. a))
            else
                raise EventhRootOfNegative
        else if a < 1.0 then
            1.0 /. (newtonNthRoot n (1.0 /. a))
        else
            let x1 = ref (0.0 +. a) in
            let xn = ref (mPow !x1 (n - 1)) in
            let x2 = ref ((((float_of_int n) -. 1.0) *. !x1 +. a /. !xn)  /. (float_of_int n)) in
            let er = ref (!x1 -. !x2) in
            let counter = ref 0 in
            let not_stop = ref true in
            while !x1 +. !er <> !x1 && !not_stop do
                x1 := !x2 ;
                xn := mPow !x1 (n - 1) ;
                x2 := (((float_of_int n) -. 1.0) *. !x1 +. a /. !xn) /. (float_of_int n) ;
                er := !x1 -. !x2 ;
                if (abs_float !er) < (abs_float nM_EPSILON *. !x1) then
                    not_stop := false ;
                counter := !counter + 1 ;
                if !counter > nMAX_ITER then
                    not_stop := false ;
            done ;
            if !counter >= nMAX_ITER then
                raise TooManyInterations ;
            !x2
    else
        if a = 0.0 then
            raise EventhRootOfNegative
        else
            1.0 /. (newtonNthRoot (-n) a) ;;


 

(* ---- Begin here ---- *)
let x = ref 16.0 in
let u = ref (sqrt !x) in

printf "[ Testing (heronSqrt double) ]--------------------\n" ;
printf "x = %g\n" !x ;
printf "u = sqrt(%g) = %g\n" !x !u ;
let y = ref (heronSqrt !x) in
printf "y = (heronSqrt %g) = %g\n" !x !y ;
printf "y*y = %g\n" (!y *. !y) ;
printf "\n" ;

printf "[ Testing (newtonCbrt double) ]--------------------\n" ;
x := 729000000000.0 ;
printf "x = %g\n" !x ;
printf "exp(log(x)/3.0) = %g\n" (exp ((log !x) /. 3.0)) ;
let w = ref (newtonCbrt !x) in
printf "w = (newtonCbrt %g) = %g\n" !x !w ;
printf "w*w*w = %g\n"  (!w *. !w *. !w)  ;
printf "\n" ;

printf "[ Testing (newtonNthRoot int double) ]--------------------\n" ;
let z = ref (newtonNthRoot 3 !x) in
printf "x = %g\n" !x ;
printf "z = (newtonNthRoot 3 %g) = %g\n" !x !z ;
printf "z*z*z = %g\n" (!z *. !z *. !z) ;
printf "\n" ;

x := 12960000000000000000.0 ;
z := newtonNthRoot 4 !x ;
printf "x = %g\n" !x ;
printf "z = (newtonNthRoot 4 x) = (newtonNthRoot 4 %g) = %g\n" !x !z ;
printf "z*z*z*z = %g\n" (!z *. !z *. !z *. !z) ;
printf "\n" ;

x := 1.0 /. 12960000000000000000.0 ;
z := newtonNthRoot 4 !x ;
printf "x = %g\n" !x ;
printf "exp(log(x)/4.0) = %g\n" (exp ((log !x) /. 4.0)) ;
printf "z = (newtonNthRoot 4 x) = (newtonNthRoot 4 %g) = %g\n" !x !z ;
printf "z*z*z*z = %g\n" (!z *. !z *. !z *. !z) ;
printf "\n" ;


(*
try
    x := -4.0 ;
    printf "[ Test Exception (heronSqrt double) ]--------------------\n" ;
    printf "x = %g\n" !x ;
    printf "Calculating (heronSqrt %g)\n" !x ;
    y := heronSqrt !x ;
    printf "y = (heronSqrt %g) = %g\n" !x !y ;
    printf "y*y = %g\n" (!y *. !y) ;
    printf "\n" ;
with
    | SqrtOfNegative -> printf "Tried to get a square root of a negative number in calculating (heronSqrt %g)\n" !x ;
             printf "\n" ;
    | TooManyInterations -> printf "Too many iterations in calculating (heronSqrt %g)\n" !x ;
             printf "\n" ;

try
    x := -4.0 ;
    printf "[ Test Exception (newtonCbrt double) ]--------------------\n" ;
    printf "x = %g\n" !x ;
    printf "Calculating (newtonCbrt %g)\n" !x ;
    y := newtonCbrt !x ;
    printf "y = newtonCbrt(%g) = %g\n" !x !y ;
    printf "y*y*y = %g\n" (!y *. !y *. !y) ;
    printf "\n" ;
with
    | TooManyInterations -> printf "Too many iterations in calculating (heronSqrt %g)\n" !x ;
             printf "\n" ;
*)

printf "[ Test calculations by powering ]-----------------------------\n" ;
x := 200.0 ;
z := newtonNthRoot 10  !x ;
printf "x = %g\n" !x ;
printf "exp(log(x)/10.0) = %g\n" (exp ((log !x) /. 10.0)) ;
printf "z = (newtonNthRoot 10 x) = (newtonNthRoot 10 %g) = %g\n" !x !z ;
printf "z**10.0 = (mPow z 10) = %g\n" (mPow !z 10) ;
printf "z**10.0 = z ** 10.0 = %g\n" (!z ** (float_of_int 10)) ;
printf "\n" ;

x := 3001.0 ;
z := newtonNthRoot 99 !x ;
printf "x = %g\n" !x ;
printf "exp(log(x)/99.0) = %g\n" (exp ((log !x) /. 99.0)) ;
printf "z = (newtonNthRoot 99 x) = (newtonNthRoot 99 %g) = %g\n" !x !z ;
printf "z**99.0 = (mPow z 99) = %g\n" (mPow !z 99) ;
printf "z**99.0 = z ** 99.0 = %g\n" (!z ** (float_of_int 99)) ;
printf "\n" ;

x := 3001.0 ;
z := newtonNthRoot (-99) !x ;
printf "x = %g\n" !x ;
printf "exp(log(x)/-99.0) = %g\n" (exp ((log !x) /. (-99.0))) ;
printf "z = (newtonNthRoot (-99) x) = (newtonNthRoot (-99) %g) = %g\n" !x !z ;
printf "mPow z (-99) = %g\n" (mPow !z (-99)) ;
printf "1.0/(z**99.0) = %g\n" (1.0 /. (!z ** 99.0)) ;
printf "z**(-99.0) = %g\n" (!z ** (-99.0)) ;
printf "\n" ;


printf "2.1**2.1 = pow(2.1, 2.1) = %g\n" (2.1**2.1) ;
printf "2.1**(-2.1) = pow(2.1, -2.1) = %g\n" (2.1**(-2.1)) ;
printf "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)) ;
printf "2.1**2.1 = exp(2.1*log(2.1)) = %g\n" (exp (2.1 *. (log 2.1))) ;
printf "2.1**(-2.1) = exp(-2.1*log(2.1)) = %g\n" (exp (-2.1 *. (log 2.1))) ;
printf "2.1**2.1 * 2.1**(-2.1) = exp(2.1*log(2.1)) * exp(-2.1*log(2.1)) = %g\n"  (2.1**2.1 *. 2.1**(-2.1)) ;
printf "\n" ;


let k = ref 301 in
x := -1.029 ;
let t1 = ref (nPow !x !k) in
let t2 = ref (gPow !x !k) in
let t3 = ref (mPow !x !k) in
let tt = ref (!x ** (float_of_int !k)) in
printf "%g ** %d = %g\n" !x !k !tt ;
printf "t1 = (nPow %g %d) = %g\n" !x !k !t1 ;
printf "t2 = (gPow %g %d) = %g\n" !x !k !t2 ;
printf "t3 = (mPow %g %d) = %g\n" !x !k !t3 ;
printf "t1 / t2 = %g\n" (!t1 /. !t2) ;
printf "t1 - t2 = %g\n" (!t1 -. !t2) ;
printf "t1 == t2 ? " ;
if t1 = t2 then printf "yes\n"
           else printf "no\n" ;
printf "t1 / t3 = %g\n" (!t1 /. !t3) ;
printf "t1 - t3 = %g\n" (!t1 -. !t3) ;
printf "t1 == t3 ? "  ;
if t1 = t3 then printf "yes\n"
           else printf "no\n" ;
printf "t2 / t3 = %g\n" (!t2 /. !t3) ;
printf "t2 - t3 = %g\n" (!t2 -. !t3) ;
printf "t2 == t3 ? "  ;
if t2 = t3 then printf "yes\n"
           else printf "no\n" ;
printf "\n" ;


printf "Done.\n" ;

 

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

[ Testing (newtonCbrt double) ]--------------------
x = 7.29e+011
exp(log(x)/3.0) = 9000
w = (newtonCbrt 7.29e+011) = 9000
w*w*w = 7.29e+011

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

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

x = 7.71605e-020
exp(log(x)/4.0) = 1.66667e-005
z = (newtonNthRoot 4 x) = (newtonNthRoot 4 7.71605e-020) = 1.66667e-005
z*z*z*z = 7.71605e-020

[ Test calculations by powering ]-----------------------------
x = 200
exp(log(x)/10.0) = 1.69865
z = (newtonNthRoot 10 x) = (newtonNthRoot 10 200) = 1.69865
z**10.0 = (mPow z 10) = 200
z**10.0 = 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 = (mPow z 99) = 3001
z**99.0 = z ** 99.0 = 3001

x = 3001
exp(log(x)/-99.0) = 0.922308
z = (newtonNthRoot (-99) x) = (newtonNthRoot (-99) 3001) = 0.922308
mPow z (-99) = 3001
1.0/(z**99.0) = 3001
z**(-99.0) = 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

-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-011
t1 == t2 ? no
t1 / t3 = 1
t1 - t3 = 6.18456e-011
t1 == t3 ? no
t2 / t3 = 1
t2 - t3 = 0
t2 == t3 ? yes

Done.
*)

 

 

Posted by Scripter
,

* 꼬리 재귀호출과 패턴 매칭을 이용하여 구현한 팩토리얼과 피보나치 수열 계산

(*
    Filename: fact.ml

         Rapid factorial and fibonacci seq implementations
         by pattern matching and tail recursive call

    Execute: ocaml nums.cma fact.ml
      or
    Compile: ocamlc -o fact.exe nums.cma fact.ml
    Execute: fact

    Date: 2013. 2. 6.
    Author: pkim __AT__ scripts.pe.kr
*)

open Printf
open Num

let bignum x = num_of_int x ;;
let to_string x = string_of_num x ;;

let rec fact n =
    match n with
    | 0 | 1    -> bignum 1
    | k        -> (bignum k) */ (fact (k-1)) ;;

let factorial n =
    let rec loop acc k =
          match k with
          | 0 -> acc
          | _ -> loop (acc */ (bignum k)) (k - 1)
    in
    loop (bignum 1) n  ;;

let fibonacci n =
    let rec loop a b k =
          match k with
          | 0 -> a
          | _ -> loop (a +/ b) a (k - 1)
    in
    loop (bignum 1) (bignum 0) n ;;

let a = 30000 in
let b = 200000 in
printf "Factorial(%d) has %d digits\n" a (String.length (sprintf "%s" (to_string (factorial a)))) ;
printf "Fibonacci(%d) has %d digits\n" b (String.length (sprintf "%s" (to_string (fibonacci b))))

(*
Expected result:
Factorial(30000) has 121288 digits
Fibonacci(200000) has 41798 digits
*)

 

Posted by Scripter
,

OCaml 언어에서 쓸 수 있는 bigint 타입은 Big_Int 모듈의 것과 Num 모듈의 것 두 가지 종류가 있다. Num 모듈의 것은 유리수 계산에도 쓸 수 있는 타입이지만 그 대신 속도가  느리고, Big_int 모듈의 것은 사칙연산자 마저도 정의 되어 있지 않아 사용하는데는 불편하지만 다소 더 빠르다. 그래도 Java 언어의 java.math.BigInteger 보다는 많이 느리다.

OCaml 언어의 타입 체크는 C 언어나 Java 언어 보다도 훨씬 엄격하며, int, int32, int64 간의 오토박싱, 언박싱은 아예 지원되지 않으며 항상 명시적인 타입 변환을 해주어야 한다.

사칙 연산 기호 마저도

     int 타입이면        +    -    *    /

     float 타입이면        +.    -.    *.    /.

     Num.Int 또는 Num.Ratio 타입이면        +/    -/    */    //

처럼 서로 다르게 사용하며, 크기 비교 연산자도

     int 타입이면        =    <    >    <=    >=

     float 타입이면        =.    <.    >.    <= .   >=.

     Num.Int 또는 Num.Rat 타입이면        =/    </    >/    <=/    >=/

처럼 서로 다르게 사용한다.


 

1) 대화형 도구 ocaml 명령으로 Big_int 모듈을 사용하는 예


명령 프롬프트> ocaml nums.cma

        Objective Caml version 3.12.1

# 100L ;;
- : int64 = 100L
# 100l ;;
- : int32 = 100l
# 100 ;;
- : int = 100
# let a = 100L ;;
val a : int64 = 100L
# let b = Int64.to_int a ;;
val b : int = 100
# let c = Big_int.big_int_of_int b ;;
val c : Big_int.big_int = <abstr>
# string_of_big_int c ;;
Characters 0-17:
  string_of_big_int c ;;
  ^^^^^^^^^^^^^^^^^
Error: Unbound value string_of_big_int
# Big_int.string_of_big_int c ;;
- : string = "100"
# Big_int.int_of_big_int c ;;
- : int = 100
# Big_int.power_big_int_positive_int c 5 ;;
- : Big_int.big_int = <abstr>
# Big_int.string_of_big_int (Big_int.power_big_int_positive_int c 5) ;;
- : string = "10000000000"
# Big_int.int64_of_big_int (Big_int.power_big_int_positive_int c 5) ;;
- : int64 = 10000000000L
# Big_int.int32_of_big_int (Big_int.power_big_int_positive_int c 5) ;;
Exception: Failure "nativeint_of_big_int".
# Big_int.int_of_big_int (Big_int.power_big_int_positive_int c 5) ;;
Exception: Failure "int_of_big_int".
# open Big_int ;;
# a ;;
- : int64 = 100L
# b ;;
- : int = 100
# let c = big_int_of_int b ;;
val c : Big_int.big_int = <abstr>
# string_of_big_int c ;;
- : string = "100"
# int64_of_big_int c ;;
- : int64 = 100L
# int32_of_big_int c ;;
- : int32 = 100l
# int_of_big_int c ;;
- : int = 100
# power_big_int_positive_int c 5 ;;
- : Big_int.big_int = <abstr>
# string_of_big_int (power_big_int_positive_int c 5) ;;
- : string = "10000000000"
# int64_of_big_int (power_big_int_positive_int c 5) ;;
- : int64 = 10000000000L
# int32_of_big_int (power_big_int_positive_int c 5) ;;
Exception: Failure "nativeint_of_big_int".
# int_of_big_int (power_big_int_positive_int c 5) ;;
Exception: Failure "int_of_big_int".
# #quit;;



 2) 대화형 도구 ocaml 명령으로 Num 모듈을 사용하는 예

명령 프롬프트> ocaml nums.cma

        Objective Caml version 3.12.1

# let a = 100L ;;
val a : int64 = 100L
# let b = Int64.to_int a ;;
val b : int = 100
# let c = Num.num_of_int b ;;
val c : Num.num = Num.Int 100
# string_of_num c ;;
Characters 0-13:
  string_of_num c ;;
  ^^^^^^^^^^^^^
Error: Unbound value string_of_num
# Num.string_of_num c ;;
- : string = "100"
# int_of_num c ;;
Characters 0-10:
  int_of_num c ;;
  ^^^^^^^^^^
Error: Unbound value int_of_num
# Num.int_of_num c ;;
- : int = 100
# Int32.of_int (Num.int_of_num c) ;;
- : int32 = 100l
# Int64.of_int (Num.int_of_num c) ;;
- : int64 = 100L
# c **/ (Num.num_of_int 5) ;;
Characters 2-5:
  c **/ (Num.num_of_int 5) ;;
    ^^^
Error: Unbound value **/
# Num.string_of_num (Num.power_num c (Num.num_of_int 5)) ;;
- : string = "10000000000"
# Int64.of_string (Num.string_of_num (Num.power_num c (Num.num_of_int 5)) ) ;;
- : int64 = 10000000000L
# Int32.of_string (Num.string_of_num (Num.power_num c (Num.num_of_int 5)) ) ;;
Exception: Failure "int_of_string".
# Int.of_string (Num.string_of_num (Num.power_num c (Num.num_of_int 5)) ) ;;
Characters 0-13:
  Int.of_string (Num.string_of_num (Num.power_num c (Num.num_of_int 5)) ) ;;
  ^^^^^^^^^^^^^
Error: Unbound module Int
# open Num ;;
# a ;;
- : int64 = 100L
# b ;;
- : int = 100
# let c = num_of_int b ;;
val c : Num.num = Int 100
# string_of_num c ;;
- : string = "100"
# int_of_num c ;;
- : int = 100
# Int64.of_int (int_of_num c) ;;
- : int64 = 100L
# Int32.of_int (int_of_num c) ;;
- : int32 = 100l
# c **/ (num_of_int 5) ;;
- : Num.num = Big_int <abstr>
# string_of_num (c **/ (num_of_int 5)) ;;
- : string = "10000000000"
# Int64.of_string (string_of_num (c **/ (num_of_int 5))) ;;
- : int64 = 10000000000L
# power_num c (num_of_int 5) ;;
- : Num.num = Big_int <abstr>
# string_of_num( power_num c (num_of_int 5)) ;;
- : string = "10000000000"
# Int64.of_string (string_of_num( power_num c (num_of_int 5))) ;;
- : int64 = 10000000000L
# #quit ;;

 

3) 대화형 도구 ocaml 명령으로 Num 모듈의 Int 타입과 Ratio 타입을 구별하는 예

명령 프롬프트> ocaml nums.cma

        Objective Caml version 3.12.1

# open Num ;;
# let a = num_of_int 5 ;;
val a : Num.num = Int 5
# let b = num_of_string "1/5" ;;
val b : Num.num = Ratio <abstr>
# let is_ratio = function
      | Num.Ratio _ -> true
      | _ -> false ;;
val is_ratio : Num.num -> bool = <fun>
# is_ratio b ;;
- : bool = true
# is_ratio a ;;
- : bool = false
# let is_num_int = function
      | Num.Int _ -> true
      | _ -> false ;;
val is_num_int : Num.num -> bool = <fun>
# is_num_int b ;;
- : bool = false
# is_num_int a ;;
- : bool = true
# a +/ b ;;
- : Num.num = Ratio <abstr>
# string_of_num (a +/ b ) ;;
- : string = "26/5"
# string_of_num (a */ b ) ;;
- : string = "1"
# string_of_num (a -/ b ) ;;
- : string = "24/5"
# string_of_num (a // b ) ;;
- : string = "25"
# a ==/ b  ;;     (* 비교 연산자 오류 *)
Characters 2-5:
  a ==/ b  ;;
    ^^^
Error: Unbound value ==/
# b >= a ;;    (* 비교 연산자 오류 *)
- : bool = true
# string_of_num (b -/ a ) ;;
- : string = "-24/5"
# a =/ b  ;;      (* 비교 연산자 정상 *)
- : bool = false
# a </ b  ;;      (* 비교 연산자 정상 *)
- : bool = false
# a <=/ b  ;;      (* 비교 연산자 정상 *)
- : bool = false
# a >=/ b  ;;      (* 비교 연산자 정상 *)
- : bool = true
# a >/ b  ;;      (* 비교 연산자 정상 *)
- : bool = true
# #quit ;;

 

 

Posted by Scripter
,


정의 (소수와 합성수)
    1보다 큰 양의 정수 n에 대하여
    (i) n = a * b 를 만족하고 1보다 큰 두 양의 정수 a와 b가 존재하면,
        n을 합성수(合成數, composite number)라고 한다. 참고로 이 경우,
        a, b 중에 적어도 하나는 sqrt(n) 보다 작거나 같다.
        합성수의 예로는 4, 6, 9, 24, 143 등이 있다.
    (ii) n = a * b 를 만족하고 1보다 큰 두 양의 정수 a와 b가 존재하지 않으면,
         즉 n을 두 양의 정수의 곱으로 표현하는 방법이 1*n과 n*1 두 가지 뿐이면,
         n을 소수(素數, prime number)라고 한다.  소수의 예로는 2, 3, 5, 7, 11 등이 있다.
         n이 소수인지 아닌지 확인하려면, 
         n을 2 보다 크거나 같고 sqrt(n) 보다 작거나 같은 모든 정수로 나누어 본다.
         이 경우 언제나 나누어 떨어지지  않으면 n은 소수이고, 그렇지 않으면 n은 합성수이다.
    

우선 다음의 OCaml 소스 코드는 명령행 인자로 전달 받은 양의 정수 n을
2 및 3, 5, 7, ... , sqrt(n) 이하의 홀수들로 나누어 보아 n이 합성수인지 아닌지
확인하는 애플리케이션 소스이다. 확인하는데 걸린 경과 시간도 알려준다.

(*
 *  Filename: divideEach.ml
 *
 *  Purpose:  Determine whether the given integer is a prime or not.
 *
 *  Execute: ocaml nums.cma unix.cma divideEach.ml 1234567
 *
 *   Or
 *
 *  Compile: ocamlc -o divideEach.exe nums.cma unix.cma divideEach.ml 
 *  Execute: divideEach [integer]
 *
 *     Date:  2013. 2. 3.
 *   Author:  pkim __AT__ scripts.pe.kr
 *)

(*
  Execution Examples with OCaml:
      Prompt> divideEach 10006099720301
      10006099720301 = 2673067 * 3743303
      10006099720301 is a not prime.
      Elapsed time: 13.000000 sec.

      Prompt> divideEach 1234567812343
      1234567812343 = 1 * 1234567812343
      1234567812343 is a prime.
      Elapsed time: 6.000000 sec.

      Prompt> divideEach 9999994200000841
      9999994200000841 = 99999971 * 99999971
      9999994200000841 is a not prime.
      Elapsed time: 504.000000 sec.

      Prompt> divideEach 18446744073709551617
      18446744073709551617 = 274177 * 67280421310721
      18446744073709551617 is a not prime.
      Elapsed time: 1.000000 sec.

      Prompt> divideEach 10023859281455311421
      10023859281455311421 = 1308520867 * 7660450463
      10023859281455311421 is a not prime.
      Elapsed time: 5328.000000 sec.
*)

open Num ;;
open Unix ;;
open Printf ;;

let bignum n = num_of_int n ;;

let bignum_s n = num_of_string n ;;

let n = ref (bignum_s "10006099720301") in

(* Begin here *)
let cmdArgs = Sys.argv in
if ((Array.length cmdArgs) > 1) then begin
    n := bignum_s cmdArgs.(1) ;
end ;

let z = ref (quo_num !n (bignum 2)) in
if !n =/ (bignum 2) */ !z then
    printf "%s = %s * %s\n" (string_of_num !n) (string_of_num (bignum 2)) (string_of_num !z) ;

let time1 = fst ( mktime (localtime (time())) ) in

let d = ref (bignum 1) in
let k = ref (bignum 3) in
let cont_flag = ref true in
while (!k */ !k <=/ !n && !cont_flag) do
    (* z := !n // !k ; *)
    z := quo_num !n !k ;
    if !n =/ !k */ !z then (
        d := !k ;
        cont_flag := false
    )
    else
        k := !k +/ (bignum 2)
done;

let time2 = fst ( mktime (localtime (time())) ) in
let elapsed = (time2 -. time1)  in

printf "%s = %s * %s\n" (string_of_num !n) (string_of_num !d) (string_of_num (!n // !d)) ;

if !d =/ (bignum 1) then
    printf "%s is a prime.\n" (string_of_num !n)
else
    printf "%s is a not prime.\n" (string_of_num !n) ;

printf "Elapsed time: %f sec.\n" elapsed

 


 

이제 다음은 정수의 인수분해 능력이 뛰어난  Pollard의 rho 방법(일명 거북이와 토끼 알고리즘, tortoise-hair algorithm)을 구현한  OCaml 소스 코드이다. 이 알고리즘은 소수에 대해서는 시간이 많이 걸리지만, 합성수에 대해서는 시간이 매우 적게 걸린다는 것이 특징이다.

(*
 *  Filename: pollardRho.ml
 *
 *  Purpose:  By using the pollard rho method,
 *            determine whether the given integer is a prime or not.
 *
 *      See:  http://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
 *            http://en.wikipedia.org/wiki/Floyd%27s_cycle-finding_algorithm#Tortoise_and_hare#
 *
 *  Execute: ocaml nums.cma unix.cma pollardRho.ml [integer]
 *
 *  Compile: ocamlc -o pollardRho.exe nums.cma unix.cma pollardRho.ml
 *  Execute: pollardRho [integer]
 *
 *     Date:  20013. 2. 3.
 *   Author:  PH Kim   [ pkim ((AT)) scripts.pe.kr ]
 *)

(*
  Execution Examples with OCaml:
      Prompt> pollardRho 1234567812343
      Try first the Pollard rho algorithm with c = 2
      d = 1234567812343, count = 466951
      Try second the Pollard rho algorithm with c = 3
      d = 1, count = 1111112
      Try third the Pollard rho algorithm with c = 1
      d = 1234567812343, count = 799441
      1234567812343 = 1234567812343 * 1
      Elapsed time: 124.000000 sec

      Prompt> pollardRho 9999994200000841
      Try first the Pollard rho algorithm with c = 2
      d = 99999971, count = 3593
      9999994200000841 = 99999971 * 99999971
      Elapsed time: 0.000000 sec

      Prompt> pollardRho 18446744073709551617
      Try first the Pollard rho algorithm with c = 2
      d = 274177, count = 1028
      18446744073709551617 = 274177 * 67280421310721
      Elapsed time: 0.000000 sec

      Prompt> pollardRho 10023859281455311421
      Try first the Pollard rho algorithm with c = 2
      d = 1308520867, count = 20350
      10023859281455311421 = 1308520867 * 7660450463
      Elapsed time: 2.000000 sec
*)

open Unix ;;
open Printf ;;
open Num ;;

let bignum n = num_of_int n

let bignum_s n = num_of_string n

let f x c n =
    mod_num (x */ x +/ c)  n

let g x c n =
    f (f x c n) c n

let gcd x y =
    let a = ref (abs_num x) in
    let b = ref (abs_num y) in
    if !b =/ (bignum 0) then
        !a
    else begin
        while !b <>/ (bignum 0) do
            let t = mod_num !a !b in
            a := !b ;
            b := t
        done ;
        !a
    end ;;

let pollardRho n =
    let c = ref (bignum 2) in
    let x = ref (bignum 1) in
    let y = ref (bignum 1) in
    let d = ref (bignum 1) in
    let savedX = ref (!x +/ (bignum 0)) in
    let count = ref (bignum 0) in
    printf "Try first the Pollard rho algorithm with c = %s\n" (string_of_num !c) ;
    let cont_flag = ref true in
    while !d =/ (bignum 1) && !count */ !count <=/ n && !cont_flag do
        x := f !x !c n ;
        if !x =/ !savedX then begin
            printf "It is cyclic.  x = %s\n" (string_of_num !x) ;
            cont_flag := false
        end
        else begin
            y := g !y !c n ;
            d := gcd (abs_num (!x -/ !y)) n ;
        end ;
        count := !count +/ (bignum 1) ;
    done;


    printf "d = %s, count = %s\n" (string_of_num !d) (string_of_num !count) ;
    if !d >/ (bignum 1) && !d </ n then begin
        !d
    end
    else begin
        c := (bignum 3) ;
        x := (bignum 1) ;
        y := (bignum 1) ;
        d := (bignum 1) ;
        savedX := !x ;
        (* printf " (0.2) x = %s\n" (string_of_num !x) ; *)
        count := (bignum 0) ;
        printf "Try second the Pollard rho algorithm with c = %s\n" (string_of_num !c) ;
        cont_flag := true ;
        while !d =/ (bignum 1) && !count */ !count <=/ n do
            x := f !x !c n ;
            if !x =/ !savedX then begin
                 printf "It is cyclic.  x = %s\n" (string_of_num !x) ;
                 cont_flag := false ;
            end
            else begin
                 y := g !y !c n ;
                 d := gcd (abs_num (!x -/ !y)) n ;
                 count := !count +/ (bignum 1) ;
            end
        done ;


        printf "d = %s, count = %s\n" (string_of_num !d) (string_of_num !count) ;
        if !d >/ (bignum 1) && !d </ n then
            !d
        else begin
            c := (bignum 1) ;
            x := (bignum 1) ;
            y := (bignum 1) ;
            d := (bignum 1) ;
            savedX := !x ;
            count := (bignum 0) ;
            printf "Try third the Pollard rho algorithm with c = %s\n" (string_of_num !c) ;
            let cont_flag2 = ref true in
            while !d =/ (bignum 1) && !count */ !count <=/ n do
                x := f !x !c n ;
                if !x =/ !savedX then begin
                    printf "It is cyclic.  x = %s\n" (string_of_num !x) ;
                    cont_flag2 := false ;
                end
                else begin
                    y := g !y !c n ;
                    d := gcd (abs_num (!x -/ !y)) n ;
                    count := !count +/ (bignum 1) ;
                end
            done ;

            printf "d = %s, count = %s\n" (string_of_num !d) (string_of_num !count) ;
            !d
        end
    end ;;


(* Begin here *)
let n = ref (bignum 9991) in

let cmdArgs = Sys.argv in
if (Array.length cmdArgs > 1) then
    n := bignum_s cmdArgs.(1) ;

let time1 = fst ( mktime (localtime (time())) ) in
let k = pollardRho !n in
let time2 = fst ( mktime (localtime (time())) ) in
let elapsed = time2 -. time1 in

let z = !n // k in
if !n =/ k */ z then
    printf "%s = %s * %s\n" (string_of_num !n) (string_of_num k) (string_of_num z) ;

printf "Elapsed time: %f sec\n" elapsed ;

 

 

Posted by Scripter
,


[파일명:  testStringFindInList.ml]------------------------------------------------
open Printf;;

let is_member arr s = List.exists (fun x -> x = s) arr ;;

let findIndex s data =
    let rec loop s1 l acc =
        match l with
        | x::xs -> if x = s1 then acc else loop s1 xs (acc + 1)
        | [] -> -1
    in
        let k = loop s data 0 in
        k ;;

let printList data =
    let rec loop l =
        match l with
        | x::[] -> printf "%s" x
        | x::xs -> begin printf "%s, " x; loop xs end
        | [] -> printf ""
    in
        printf "[" ;
        loop data ;
        printf "]" ;;

(* Begin here *)
(* let cmdArgs = Sys.argv in *)

let words = ["하나"; "둘"; "셋"; "넷"; "다섯"; "여섯"] in

printf "list: " ;
printList words ;
printf "\n"  ;
let three = "셋" in
let check = is_member words three in
printf "Is %s a membert of list? %s\n" three (string_of_bool check) ;
if check then begin
    let where1 = findIndex three words in
    printf "%s has been found at index %d.\n" three where1 ;
    if where1 < ((List.length words) - 1) then
        printf "The next word of %s is %s.\n" three (List.nth words (where1 + 1)) ;
end ;

print_newline() ;

printf "Sorting...\n" ;
let otherwords = List.sort String.compare words in
printf "sorted list: " ;
printList otherwords ;
printf "\n"  ;
let check = is_member otherwords three in
printf "Is %s a membert of sorted list? %s\n" three (string_of_bool check) ;
if check then begin
    let where1 = findIndex three otherwords in
    printf "%s has been found at index %d.\n" three where1 ;
    if where1 < ((List.length otherwords) - 1) then
        printf "The next word of %s is %s.\n" three (List.nth words (where1 + 1)) ;
end ;

------------------------------------------------


실행> ocaml testStringFindInList.ml
list: [하나, 둘, 셋, 넷, 다섯, 여섯]
Is 셋 a membert of list? true
셋 has been found at index 2.
The next word of 셋 is 넷.

Sorting...
sorted list: [넷, 다섯, 둘, 셋, 여섯, 하나]
Is 셋 a membert of sorted list? true
셋 has been found at index 3.
The next word of 셋 is 다섯.


Posted by Scripter
,

printList 함수를 OCaml 의 함수형 언어의 특징을 살려 (꼬리 재귀호출과 match 표현을 이용하여) 구현하였다.

[파일명:  testSort.ml]------------------------------------------------
open Printf ;;

let printList data =
    let rec loop l =
        match l with
        | x::[] -> printf "%s" x
        | x::xs -> begin printf "%s, " x; loop xs end
        | [] -> printf ""
    in
        printf "[" ;
        loop data ;
        printf "]" ;;

(* Begin here *)
let cmdArgs = Sys.argv in
let args2 = Array.sub cmdArgs 1 ((Array.length cmdArgs) - 1) in
printf "Original data: " ;
printList (Array.to_list args2) ;
print_newline() ;

Array.sort String.compare args2 ;
printf "  Sorted data: " ;
let b = Array.to_list args2 in
printList b ;
print_newline() ;
------------------------------------------------


실행> ocaml testSort.ml a123 help me 한글 각자 halo kk c 564
Original data: [a123, help, me, 한글, 각자, halo, kk, c, 564]
  Sorted data: [564, a123, c, halo, help, kk, me, 각자, 한글]

Posted by Scripter
,

초등학교 때 배우던 두 정수의 곱셈표를 만들어 주는 F# 소스이다. 이 소스는 Python 소스를 F# 소스로 변환한 후 다시 OCaml 언어로 재작성한 것이라서 OCaml 의 명령형 언어 특징을 위주로 짜여져 있다.

(*
 * Filename: makeMultTable.ml
 *
 *     Print a multiplication table.
 *
 *  Execute: ocaml makeMultTable.ml 123 450
 *
 *   Or
 *
 *  Compile: ocamlc -o makeMultTable.exe makeMultTable.ml
 *  Execute: makeMultTable 230 5100
 *
 *     Date: 2013. 2. 2).
 *   Author:  pkim __AT__ scripts.pe.kr
 *)
open Printf;;
exception RuntimeError of string
exception ValueError of string
let println s = printf "%s\n" s ;;
let print s = printf "%s" s ;;
let printUsage() =
    println "Using: ocaml makeMultTable.ml [number1] [number2]" ;
    println "Print a multiplication table for the given two integers." ;;
let printMultTable x y =
    let nx = ref x in
    if !nx < 0 then
        nx := - !nx ;
    let ny = ref y in
    if !ny < 0 then
        ny := - !ny ;
    let ntail1 = ref 0 in
    let ntail2 = ref 0 in
    while (!nx mod 10) = 0 do
        nx := !nx / 10 ;
        ntail1 := !ntail1 + 1
    done ;
    while !ny mod 10 = 0 do
        ny := !ny / 10 ;
        ntail2 := !ntail2 + 1
    done ;
    let z = !nx * !ny in
    let strZ = sprintf "%d" z in
    let strX = sprintf "%d" !nx in
    let strY = sprintf "%d" !ny in
    (* let n = String.length strY in *)
    let zeros  = "0000000000000000000000000000000000000000" in
    let whites = "                                        " in
    let bars   = "----------------------------------------" in
    let loffset = "       " in
    let line4 = loffset ^ strZ in
    let line1 = loffset ^ (String.sub whites 0 ((String.length strZ) - (String.length strX))) ^ strX in
    let line2 = "   x ) " ^  (String.sub whites 0 ((String.length strZ) - (String.length strY))) ^ strY in
    let line3 = "     --" ^  (String.sub bars 0 (String.length strZ)) in
    println (line1 ^ (String.sub zeros 0 !ntail1)) ;
    println (line2 ^ (String.sub zeros 0 !ntail2)) ;
    println line3 ;
    if (String.length strY) > 1 then begin
        for i = 0 to ((String.length strY) - 1) do
            let y1 = int_of_string (String.sub strY ((String.length strY) - i - 1)  1) in
            if not (y1 = 0) then begin
                let strT = sprintf "%d" (!nx * y1) in
                println (loffset ^ (String.sub whites 0 ((String.length strZ) - (String.length strT) - i)) ^ strT)
            end
        done ;
        println line3 ;
    end ;
    println (line4 ^ (String.sub zeros 0 !ntail1) ^ (String.sub zeros 0 !ntail2)) ;;
(* Begin here *)
let cmdArgs = Sys.argv in
if (Array.length cmdArgs >= 3) then begin
    let x = int_of_string (cmdArgs.(1)) in
    let y = int_of_string (cmdArgs.(2)) in
    println "" ;
    printMultTable x y
end
else begin
    printUsage() ;
    exit(1)
end




컴파일> ocamlc -o makeMultTable.exe makeMultTable.ml

실행> makeMultTable 230 5100
결과>

          1030
   x )   10020
     --------
          206
       103
     --------
       10320600

 

Posted by Scripter
,
▒ OCaml 소스:  testStringReverse.ml

open Printf;;

let reverse s =
    let s2 = "" ^ s in
    let n = String.length s in
    for i = 0 to (n/2 - 1) do
        let t = s2.[i] in
        s2.[i] <- s2.[n - 1 - i];
        s2.[n - 1 - i] <- t
    done ;
    s2;;

let reverse2 s =
    let s2 = "" ^ s in
    let n = String.length s in
    let isTwo = ref false in
    for i = 0 to (n - 1) do
        if !isTwo = false then begin
            let t = s.[i] in
            (* printf "  %d\n" (int_of_char t) ; *)
            if (int_of_char t) > 127 then begin
                isTwo := true;
                s2.[n - 1 - i - 1] <- t ;
                s2.[n - 1 - i] <- s.[i + 1]
            end
            else begin
                isTwo := false;
                s2.[n - 1 - i] <- t
            end
        end
        else
            isTwo := false;
    done ;
    s2;;

let a = "Hello, world!" in
let b = "안녕하세요?" in
let a2 = reverse a in
let a3 = reverse a in
let b2 = reverse b in
let b3 = reverse2 b in

printf " reverse: %s\n" a2;
printf "original: %s\n" a;
printf "reverse2: %s\n" a3;
printf "original: %s\n" a;
print_newline();
printf " reverse: %s\n" b2;
printf "original: %s\n" b;
printf "reverse2: %s\n" b3;
printf "original: %s\n" b;

(*
let mutable arr = a.ToCharArray()
arr <- Array.rev arr
System.Console.WriteLine(new System.String(arr))
arr <- b.ToCharArray()
arr <- Array.rev arr
System.Console.WriteLine(new System.String(arr))
*)

(*
Expected result:
 reverse: !dlrow ,olleH
original: Hello, world!
reverse2: !dlrow ,olleH
original: Hello, world!

 reverse: ?岳세逑楹횡
original: 안녕하세요?
reverse2: ?요세하녕안
original: 안녕하세요?
*)

 

주: 소스 파일은 ms949 인코딩으로 저장되어야 한다.

 

Posted by Scripter
,