4. 多倍長整数

著者:梅谷武

各言語における多倍長整数について調べる。

作成:2024-03-12
更新:2024-09-02

C++

GCC/ClangにおいてはGMP(GNU multiple precision arithmetic library)で多倍長計算を行なう。GMPについてはオンラインマニュアル:GNU MPを参照のこと。

OCaml

OCaml5.2.0版の標準ライブラリに多倍長整数は見当たらない。過去には標準ライブラリに多倍長整数が組み込まれていた時期があり、その情報がネット上に残っているので注意が必要である。現在はGMPを組み込んだZarithが用いられている。ZarithについてはGitHub:ocaml/Zarithを参照のこと。

Racket

Racketの整数型についての概説はThe Racket Guide＞3 Built-in Datatypes＞3.2 Numbers、詳細仕様はThe Racket Reference＞4 Datatypes＞4.3 Numbersにある。

4.2 多倍長整数

C++

forループを使って階乗計算する。

factorial2.cpp:

#include <gmpxx.h>
#include <print>
#include <stdexcept>
 
int main(int argc, char *argv[]) {
  try {
    if (argc != 2) {
      throw std::invalid_argument(
          "Usage: factorial2 <non-negative integer>");
    }
    long n = std::stol(argv[1]);
    if (n < 0l) {
      throw std::invalid_argument(
          "The argument must be a non-negative integer.");
    }
    mpz_class result(1);
    for (long i = 2; i <= n; ++i)
      result *= i;
    std::println("{}! = {}", n, result.get_str());
  } catch (const std::logic_error &e) {
    std::println(stderr, "Logic error: {}", e.what());
  } catch (const std::runtime_error &e) {
    std::println(stderr, "Runtime error: {}", e.what());
  } catch (const std::exception &e) {
    std::println(stderr, "Another std::exception: {}", e.what());
  } catch (...) {
    std::println(stderr, "Unknown exception.");
  }
  return 0;
}

コンパイル時にGMPライブラリをリンクする。

makefile:

CPPG = g++
CPPL = clang++
CPPFLAGS = -std=c++23 -O2
LIBS = -lgmpxx -lgmp
SRC = factorial2.cpp
EXES = factorial2_g factorial2_l
 
all: $(EXES)
 
factorial2_g: $(SRC)
	$(CPPG) $(CPPFLAGS) -o $@ $(SRC) $(LIBS)
 
factorial2_l: $(SRC)
	$(CPPL) $(CPPFLAGS) -o $@ $(SRC) $(LIBS)
 
clean:
	rm -f $(EXES)

n = 40で測定する。

$ measure ./factorial2_g 40
40! = 815915283247897734345611269596115894272000000000
======================================
Process exited with status: 0
total time:  0.000000 [sec]
mem  size:       4088 [KB]
code size:        123 [KB]

$ measure ./factorial2_l 40
40! = 815915283247897734345611269596115894272000000000
======================================
Process exited with status: 0
total time:  0.000796 [sec]
mem  size:       4116 [KB]
code size:         93 [KB]

OCaml

末尾再帰を使って階乗計算する。

factorial2.ml:

open Printf
 
let rec fact_aux n acc =
  if n = Z.zero then
    acc
  else
    fact_aux (Z.pred n) (Z.mul n acc)
 
let () =
  try
    if Array.length Sys.argv <> 2 then
      raise (Invalid_argument
        "Usage: factorial2 <non-negative integer>")
    else
      let n = int_of_string Sys.argv.(1) in
      if n < 0 then
        raise (Invalid_argument
          "The argument must be a non-negative integer.")
      else
        let result = fact_aux (Z.of_int n) Z.one in
        printf "%d! = %s\n" n (Z.to_string result)
  with
    | Invalid_argument msg ->
        eprintf "Logic error: %s\n" msg
    | Failure msg ->
        eprintf "Runtime error: %s\n" msg
    | exn ->
        eprintf "Another exception: %s\n" (Printexc.to_string exn)

zarithは標準ライブラリではないのでインストールパスを実行時に動的に取得する。

makefile:

OCAMLOPT = ocamlopt
OCAMLFLAGS = -O2
LIBPATH = -I $(shell opam var zarith:lib)
LIBS = zarith.cmxa
SRC = factorial2.ml
EXES = factorial2
 
all: $(EXES)
 
factorial2: $(SRC)
	$(OCAMLOPT) $(OCAMLFLAGS) $(LIBPATH) -o $@ $(LIBS) $(SRC)
 
clean:
	rm -f $(EXES) *.o *.cmx *.cmi

n = 40で測定する。

$ measure ./factorial2 40
40! = 815915283247897734345611269596115894272000000000
======================================
Process exited with status: 0
total time:  0.001698 [sec]
mem  size:       3684 [KB]
code size:       3106 [KB]

Racket

Racketの場合はfactorial.rktがすでに多倍長整数に対応している。これを末尾再帰に書き直す。

factorial2.rkt:

#lang racket
(require iso-printf)
 
(define (fact_aux n acc)
  (if (= n 0)
      acc
      (fact_aux (- n 1) (* n acc))))
 
(define (main args)
  (with-handlers
    ([exn:fail? (λ (e) (eprintf "%s\n" (exn-message e)))]
     [exn? (λ (e) (eprintf "Unexpected: %s\n" (exn-message e)))])
  (cond
    [(not (= (vector-length args) 1))
      (error "Usage: factorial2 <non-negative integer>")]
    [else
      (let ([n (string->number (vector-ref args 0))])
        (cond
          [(not (integer? n))
            (error "The argument must be an integer.")]
          [(< n 0)
            (error "The argument must be a non-negative integer.")]
          [else
            (printf "%d! = %d\n" n (fact_aux n 1))]))])))
 
(main (current-command-line-arguments))

n = 40で測定する。

$ measure ./factorial2 40
40! = 815915283247897734345611269596115894272000000000
======================================
Process exited with status: 0
total time:  0.462708 [sec]
mem  size:     134192 [KB]
code size:      12442 [KB]

4.3 フィボナッチ数

フィボナッチ数の計算でC++、OCaml、Racketを比較してみよう。フィボナッチ数(Fibonacci number)とは、

F₀

F₁

F_n

F_n-1 + F_n-2 (n ＞ 1)

という漸化式で定義される自然数列である。この帰納的定義はそのままプログラムになりそうであるが関数型言語では末尾再帰にしなければならない。

C++

C++でフィボナッチ数を計算するプログラムはfor文を使って次のように書ける。計算結果は標準エラー出力に書くようにしてコマンドラインでファイルにリダイレクトする。後でdiffコマンドによりC++、OCaml、Racketの計算結果を比較する。

fibonacci.cpp:

#include <gmpxx.h>
#include <print>
#include <stdexcept>
 
mpz_class fibonacci(long n) {
  mpz_class a(0), b(1), tmp(0);
  if (n == 0l)
    b = 0;
  else if (n == 1l)
    b = 1;
  else {
    for (long i = 0; i < n - 1; ++i) {
      tmp = a + b;
      a = b;
      b = tmp;
    }
  }
  return b;
}
 
int main(int argc, char *argv[]) {
  try {
    if (argc != 2) {
      throw std::invalid_argument(
          "Usage: fibonacci <non-negative integer>");
    }
    long n = std::stol(argv[1]);
    if (n < 0l) {
      throw std::invalid_argument(
          "The argument must be a non-negative integer.");
    }
    mpz_class result = fibonacci(n);
    std::println(stderr, "fib {}\n{}", n, result.get_str());
  } catch (const std::logic_error &e) {
    std::println(stderr, "Logic error: {}", e.what());
  } catch (const std::runtime_error &e) {
    std::println(stderr, "Runtime error: {}", e.what());
  } catch (const std::exception &e) {
    std::println(stderr, "Another std::exception: {}", e.what());
  } catch (...) {
    std::println(stderr, "Unknown exception.");
  }
  return 0;
}

makefile:

CPPG = g++
CPPL = clang++
CPPFLAGS = -std=c++23 -O2
LIBS = -lgmpxx -lgmp
SRC = fibonacci.cpp
EXES = fibonacci_g fibonacci_l
 
all: $(EXES)
 
fibonacci_g: $(SRC)
	$(CPPG) $(CPPFLAGS) -o $@ $(SRC) $(LIBS)
 
fibonacci_l: $(SRC)
	$(CPPL) $(CPPFLAGS) -o $@ $(SRC) $(LIBS)
 
clean:
	rm -f $(EXES)

n = 1000000で測定する。

$ measure ./fibonacci_g 1000000 2>fib1000000_g.txt
======================================
Process exited with status: 0
total time: 10.045444 [sec]
mem  size:       4924 [KB]
code size:        123 [KB]

$ measure ./fibonacci_l 1000000 2>fib1000000_l.txt
======================================
Process exited with status: 0
total time: 10.199326 [sec]
mem  size:       4924 [KB]
code size:         97 [KB]

OCaml

プログラム:fibonacci.ml

open Printf
 
let rec fib_aux n a b = 
  if n = Z.zero then a
  else fib_aux (Z.sub n Z.one) b (Z.add a b)
 
let () =
  try
    if Array.length Sys.argv <> 2 then
      raise (Invalid_argument
        "Usage: fibonacci <non-negative integer>")
    else
      let n = int_of_string Sys.argv.(1) in
      if n < 0 then
        raise (Invalid_argument
          "The argument must be a non-negative integer.")
      else
        let result = fib_aux (Z.of_int n) Z.zero Z.one in
        eprintf "fib %d\n%s\n" n (Z.to_string result)
  with
    | Invalid_argument msg ->
        eprintf "Logic error: %s\n" msg
    | Failure msg ->
        eprintf "Runtime error: %s\n" msg
    | exn ->
        eprintf "Another exception: %s\n" (Printexc.to_string exn)

makefile:

OCAMLOPT = ocamlopt
OCAMLFLAGS = -O2
LIBPATH = -I $(shell opam var zarith:lib)
LIBS = zarith.cmxa
SRC = fibonacci.ml
EXES = fibonacci
 
all: $(EXES)
 
fibonacci: $(SRC)
	$(OCAMLOPT) $(OCAMLFLAGS) $(LIBPATH) -o $@ $(LIBS) $(SRC)
 
clean:
	rm -f $(EXES) *.o *.cmx *.cmi

n = 1000000で測定する。

$ measure ./fibonacci 1000000 2>fib1000000.txt
======================================
Process exited with status: 0
total time:  9.867783 [sec]
mem  size:       7920 [KB]
code size:       3106 [KB]

C++より速い。

Racket

プログラム:fibonacci.rkt

#lang racket
(require iso-printf)
 
(define (fib_aux n a b)
  (if (= n 0)
      a
      (fib_aux (- n 1) b (+ a b))))
 
(define (main args)
  (with-handlers
    ([exn:fail? (λ (e) (eprintf "%s\n" (exn-message e)))]
     [exn? (λ (e) (eprintf "Unexpected: %s\n" (exn-message e)))])
  (cond
    [(not (= (vector-length args) 1))
      (error "Usage: fibonacci <non-negative integer>")]
    [else
      (let ([n (string->number (vector-ref args 0))])
        (cond
          [(not (integer? n))
            (error "The argument must be an integer.")]
          [(< n 0)
            (error "The argument must be a non-negative integer.")]
          [else
            (eprintf "fib %d\n%d\n" n (fib_aux n 0 1))]))])))
 
(main (current-command-line-arguments))

n = 1000000で測定する。

$ raco exe fibonacci.rkt
$ measure ./fibonacci 1000000 2>fib1000000.txt
======================================
Process exited with status: 0
total time: 21.632141 [sec]
mem  size:     133844 [KB]
code size:      12442 [KB]

This document is licensed under the MIT License.
Copyright (C) 2024 Takeshi Umetani