Yet Another SML/NJ Problems

●問題91

Word32 (無符号 32 bit 整数) とリストを使ってシンプルな無符号多倍長整数 (bignum) を実装します。基数を 65536 とし、リストの先頭が下位の桁、末尾を上位の桁とします。簡単な例を示します。

0 => [0wx0]
1 => [0wx1]
65535 => [0wxFFFF]
65536 => [0wx0,0wx1]
4294967295 => [0wxFFFF,0wxFFFF]
4294967296 => [0wx0,0wx0,0wx1]

整数 (IntInf.int) を多倍長整数に変換する関数 integer_to_bignum n を定義してください。

val integer_to_bignum = fn : IntInf.int -> Word32.word list

- integer_to_bignum(0);
val it = [0wx0] : Word32.word list
- integer_to_bignum(1);
val it = [0wx1] : Word32.word list
- integer_to_bignum(65535);
val it = [0wxFFFF] : Word32.word list
- integer_to_bignum(65536);
val it = [0wx0,0wx1] : Word32.word list
- integer_to_bignum(0xffffffff);
val it = [0wxFFFF,0wxFFFF] : Word32.word list
- integer_to_bignum(0x100000000);
val it = [0wx0,0wx0,0wx1] : Word32.word list

●問題92

多倍長整数を整数 (IntInf.int) に変換する関数 bignum_to_integer xs を定義してください。

val bignum_to_integer = fn : Word32.word list -> IntInf.int

- bignum_to_integer([0w0]);
val it = 0 : IntInf.int
- bignum_to_integer([0wxffff]);
val it = 65535 : IntInf.int
- bignum_to_integer([0wxffff, 0wxffff]);
val it = 4294967295 : IntInf.int
- bignum_to_integer([0w0, 0w0, 0w0, 0w1]);
val it = 281474976710656 : IntInf.int

●問題93

2 つの多倍長整数 xs, ys の論理積を求める関数 bignum_and(xs, ys) を定義してください。

val bignum_and = fn : Word32.word list * Word32.word list -> Word32.word list

- bignum_and([0wxffff, 0wxffff, 0wxffff], [0wxf0f0, 0wx0f0f, 0wxffff]);
val it = [0wxF0F0,0wxF0F,0wxFFFF] : Word32.word list
- bignum_and([0wxffff, 0wxffff, 0wxffff], [0wxf0f0, 0wx0f0f]);
val it = [0wxF0F0,0wxF0F] : Word32.word list
- bignum_and([0wxffff, 0wxffff, 0wxffff], [0wxf0f0]);
val it = [0wxF0F0] : Word32.word list
- bignum_and([0wxffff, 0wxffff, 0wxffff], [0wx0]);
val it = [0wx0] : Word32.word list

●問題94

2 つの多倍長整数 xs, ys の論理和を求める関数 bignum_or(xs, ys) を定義してください。

val bignum_or = fn : Word32.word list * Word32.word list -> Word32.word list

- bignum_or([0wxff00, 0wxf0f0, 0wx00ff], [0wx00ff, 0wxf0f0f, 0wxff00]);
val it = [0wxFFFF,0wxFFFFF,0wxFFFF] : Word32.word list
- bignum_or([0wxff00, 0wxf0f0, 0wx00ff], [0wx00ff, 0wxf0f0f]);
val it = [0wxFFFF,0wxFFFFF,0wxFF] : Word32.word list
- bignum_or([0wxff00, 0wxf0f0, 0wx00ff], [0wx00ff]);
val it = [0wxFFFF,0wxF0F0,0wxFF] : Word32.word list
- bignum_or([0wxff00, 0wxf0f0, 0wx00ff], [0wx0]);
val it = [0wxFF00,0wxF0F0,0wxFF] : Word32.word list

●問題95

2 つの多倍長整数 xs, ys の排他的論理和を求める関数 bignum_xor(xs, ys) を定義してください。

- bignum_xor([0wxff00, 0wxf0f0, 0wx00ff], [0wxffff, 0wxffff, 0wxffff]);
val it = [0wxFF,0wxF0F,0wxFF00] : Word32.word list
- bignum_xor([0wxff00, 0wxf0f0, 0wx00ff], [0w0]);
val it = [0wxFF00,0wxF0F0,0wxFF] : Word32.word list
- bignum_xor([0wxff00, 0wxf0f0, 0wx00ff], [0wx00ff, 0wx0f0f, 0wxff00]);
val it = [0wxFFFF,0wxFFFF,0wxFFFF] : Word32.word list
- bignum_xor([0wxff00, 0wxf0f0, 0wx00ff], [0wxff00, 0wxf0f0, 0wx00ff]);
val it = [0wx0] : Word32.word list

●問題96

多倍長整数 xs を左へ n bit シフトする関数 bignum_shift_left(xs, n) を定義してください。

val bignum_shift_left = fn : Word32.word list * word -> Word32.word list

- bignum_shift_left([0wxf0f0], 0w0);
val it = [0wxF0F0] : Word32.word list
- bignum_shift_left([0wxf0f0], 0w8);
val it = [0wxF000,0wxF0] : Word32.word list
- bignum_shift_left([0wxf0f0], 0w16);
val it = [0wx0,0wxF0F0] : Word32.word list
- bignum_shift_left([0wxf0f0], 0w24);
val it = [0wx0,0wxF000,0wxF0] : Word32.word list
- bignum_shift_left([0wxf0f0], 0w32);
val it = [0wx0,0wx0,0wxF0F0] : Word32.word list

●問題97

多倍長整数 xs を右へ n bit シフトする関数 bignum_shift_right(xs, n) を定義してください。

- bignum_shift_right([0w0, 0wxffff], 0w0);
val it = [0wx0,0wxFFFF] : Word32.word list
- bignum_shift_right([0w0, 0wxffff], 0w8);
val it = [0wxFF00,0wxFF] : Word32.word list
- bignum_shift_right([0w0, 0wxffff], 0w16);
val it = [0wxFFFF] : Word32.word list
- bignum_shift_right([0w0, 0wxffff], 0w24);
val it = [0wxFF] : Word32.word list
- bignum_shift_right([0w0, 0wxffff], 0w32);
val it = [0wx0] : Word32.word list

●問題98

下表に示す多倍長整数を比較する演算子を定義してください。

infix 4 =/ <>/ </ >/ <=/ >=/
val =/ = fn : Word32.word list * Word32.word list -> bool
val <>/ = fn : Word32.word list * Word32.word list -> bool
val </ = fn : Word32.word list * Word32.word list -> bool
val >/ = fn : Word32.word list * Word32.word list -> bool
val <=/ = fn : Word32.word list * Word32.word list -> bool
val >=/ = fn : Word32.word list * Word32.word list -> bool

- [0w0, 0w0, 0w1] =/ [0w0, 0w0, 0w1];
val it = true : bool
- [0w0, 0w0, 0w1] =/ [0w1, 0w0, 0w1];
val it = false : bool
- [0w0, 0w0, 0w1] </ [0w1, 0w0, 0w1];
val it = true : bool
- [0w0, 0w0, 0w1] >/ [0w0, 0w1, 0w1];
val it = false : bool

●問題99

多倍長整数 xs と基数未満の整数 n を加算する関数 bignum_add_int(xs, n) を定義してください。

val bignum_add_int = fn : Word32.word list * Word32.word -> Word32.word list

- bignum_add_int([0wxffff, 0wxffff], 0w0);
val it = [0wxFFFF,0wxFFFF] : Word32.word list
- bignum_add_int([0wxffff, 0wxffff], 0w1);
val it = [0wx0,0wx0,0wx1] : Word32.word list
- bignum_add_int([0wxffff, 0wxffff], 0wxffff);
val it = [0wxFFFE,0wx0,0wx1] : Word32.word list

●問題100

多倍長整数 xs. ys を加算する中置演算子 xs +/ ys を定義してください。

infix 6 +/
val +/ = fn : Word32.word list * Word32.word list -> Word32.word list

- [0wxffff, 0wxffff] +/ [0w0, 0w0, 0w1];
val it = [0wxFFFF,0wxFFFF,0wx1] : Word32.word list
- [0wxffff, 0wxffff] +/ [0w1, 0w0, 0w1];
val it = [0wx0,0wx0,0wx2] : Word32.word list
- [0wxffff, 0wxffff] +/ [0w0, 0w1, 0w1];
val it = [0wxFFFF,0wx0,0wx2] : Word32.word list

●問題101

多倍長整数 xs と基数未満の整数 n を減算する関数 bignum_sub_int(xs, n) を定義してください。

val bignum_sub_int = fn : Word32.word list * Word32.word -> Word32.word list

- bignum_sub_int([0w1], 0w1);
val it = [0wx0] : Word32.word list
- bignum_sub_int([0w0, 0w1], 0w1);
val it = [0wxFFFF] : Word32.word list
- bignum_sub_int([0w0, 0w0, 0w1], 0w1);
val it = [0wxFFFF,0wxFFFF] : Word32.word list
- bignum_sub_int([0w0, 0w0, 0w1], 0wxffff);
val it = [0wx1,0wxFFFF] : Word32.word list
- bignum_sub_int([0w0], 0wx1);

uncaught exception Bignum_underflow

●問題102

多倍長整数 xs. ys を減算する中置演算子 xs -/ ys を定義してください。

infix 6 -/
val -/ = fn : Word32.word list * Word32.word list -> Word32.word list

- [0w0, 0w0, 0w0, 0w1] -/ [0w0, 0w0, 0w0, 0w1];
val it = [0wx0] : Word32.word list
- [0w0, 0w0, 0w0, 0w1] -/ [0w0, 0w0, 0w1];
val it = [0wx0,0wx0,0wxFFFF] : Word32.word list
- [0w0, 0w0, 0w0, 0w1] -/ [0wxffff, 0wxffff, 0wxffff];
val it = [0wx1] : Word32.word list
- [0w0, 0w0, 0w1] -/ [0wxffff, 0wxffff, 0wxffff];

uncaught exception Bignum_underflow

●問題103

多倍長整数 xs と基数未満の整数 n を乗算する関数 bignum_mul_int(xs, n) を定義してください。

val bignum_mul_int = fn : Word32.word list * Word32.word -> Word32.word list

- bignum_mul_int([0w1,0w2,0w3,0w4,0w5], 0w2);
val it = [0wx2,0wx4,0wx6,0wx8,0wxA] : Word32.word list
- bignum_mul_int([0w1,0w2,0w3,0w4,0w5], 0w1);
val it = [0wx1,0wx2,0wx3,0wx4,0wx5] : Word32.word list
- bignum_mul_int([0w1,0w2,0w3,0w4,0w5], 0w0);
val it = [0wx0] : Word32.word list
- bignum_mul_int([0wxffff, 0wxffff, 0wxffff], 0w2);
val it = [0wxFFFE,0wxFFFF,0wxFFFF,0wx1] : Word32.word list
- bignum_mul_int([0wxffff, 0wxffff, 0wxffff], 0wxffff);
val it = [0wx1,0wxFFFF,0wxFFFF,0wxFFFE] : Word32.word list

●問題104

多倍長整数 xs. ys を乗算する中置演算子 xs */ ys を定義してください。

infix 7 */
val */ = fn : Word32.word list * Word32.word list -> Word32.word list

- [0w1, 0w1, 0w1] */ [0w1, 0w1, 0w1];
val it = [0wx1,0wx2,0wx3,0wx2,0wx1] : Word32.word list
- [0wxffff, 0wxffff, 0wxffff] */ [0w1, 0w1, 0w1];
val it = [0wxFFFF,0wxFFFE,0wxFFFE,0wx0,0wx1,0wx1] : Word32.word list
- [0wxffff, 0wxffff, 0wxffff] */ [0w1, 0w0, 0w1];
val it = [0wxFFFF,0wxFFFF,0wxFFFE,0wx0,0wx0,0wx1] : Word32.word list
- [0wxffff, 0wxffff, 0wxffff] */ [0w1];
val it = [0wxFFFF,0wxFFFF,0wxFFFF] : Word32.word list
- [0wxffff, 0wxffff, 0wxffff] */ [0w0];
val it = [0wx0] : Word32.word list

●問題105

多倍長整数 xs と基数未満の整数 n を除算する関数 bignum_div_int(xs, n) を定義してください。返り値は商と剰余をタプルで返すものとします。

- bignum_div_int([0w2,0w4,0w6,0w8],0w2);
val it = ([0wx1,0wx2,0wx3,0wx4],[0wx0]) : Word32.word list * Word32.word list
- bignum_div_int([0w2,0w4,0w6,0w8],0w4);
val it = ([0wx0,0wx8001,0wx1,0wx2],[0wx2]) : Word32.word list * Word32.word list
- bignum_div_int([0w2,0w4,0w6,0w8],0w0);

uncaught exception Bignum_div_by_zero

●問題106

多倍長整数 xs. ys を除算する関数 bignum_div(xs, ys) を定義してください。返り値は商と剰余を多値で返すものとします。また、bignum_div を使って多倍長整数を商を求める演算子 // と剰余を求める演算子 %/ を定義してください。

val bignum_div = fn : Word32.word list * Word32.word list -> Word32.word list * Word32.word list
infix 7 //
val // = fn : Word32.word list * Word32.word list -> Word32.word list
val %/ = fn : Word32.word list * Word32.word list -> Word32.word list

- bignum_div([0w0,0w0,0w0,0w1],[0w0,0w0,0w0,0w1]);
val it = ([0wx1],[0wx0]) : Word32.word list * Word32.word list
- bignum_div([0w0,0w0,0w0,0w1],[0w0,0w0,0w1]);
val it = ([0wx0,0wx1],[0wx0]) : Word32.word list * Word32.word list
- bignum_div([0w0,0w0,0w0,0w1],[0w0,0w1]);
val it = ([0wx0,0wx0,0wx1],[0wx0]) : Word32.word list * Word32.word list
- bignum_div([0w0,0w0,0w0,0w1],[0wxffff,0wxffff]);
val it = ([0wx0,0wx1],[0wx0,0wx1]) : Word32.word list * Word32.word list

- bignum_div([0w65535, 0w65535, 0w32767], [0w65535, 0w32768]);
val it = ([0wxFFFE],[0wxFFFD,0wx2]) : Word32.word list * Word32.word list
- bignum_div([0w65535, 0w0, 0w32767], [0w65535, 0w32768]);
val it = ([0wxFFFC],[0wxFFFB,0wx5]) : Word32.word list * Word32.word list

- bignum_div([0w0,0w0,0w0,0w1],[0w0]);

uncaught exception Bignum_div_by_zero


- [0w0, 0w0, 0w0, 0w1] // [0wxffff, 0wxffff];
val it = [0wx0,0wx1] : Word32.word list
- [0w0, 0w0, 0w0, 0w1] %/ [0wxffff, 0wxffff];
val it = [0wx0,0wx1] : Word32.word list
- [0w0, 0w0, 0w0, 0w4] // [0w0, 0w2];
val it = [0wx0,0wx0,0wx2] : Word32.word list
- [0w0, 0w0, 0w0, 0w4] %/ [0w0, 0w2];
val it = [0wx0] : Word32.word list

●問題107

多倍長整数 xs を文字列に変換する関数 bignum_to_string(xs, r) を定義してください。r は基数を表す整数値 (r <= 16) です。

val bignum_to_string = fn : Word32.word list * int -> string

- bignum_to_string([0w722,0w18838], 10);
val it = "1234567890" : string
- bignum_to_string([0w65535,0w65535], 16);
val it = "FFFFFFFF" : string
- bignum_to_string([0w0, 0w0, 0w0, 0w0, 0w1], 10);
val it = "18446744073709551616" : string
- bignum_to_string([0w0, 0w0, 0w0, 0w0, 0w1], 16);
val it = "10000000000000000" : string

●問題108

文字列 str を多倍長整数に変換する関数 string_to_bignum(str, r) を定義してください。r は基数を表す整数値 (r <= 16) です。

val string_to_bignum = fn : string * int -> Word32.word list

- string_to_bignum("1234567890", 10);
val it = [0wx2D2,0wx4996] : Word32.word list
- bignum_to_string(it, 10);
val it = "1234567890" : string
- string_to_bignum("ffffffff", 16);
val it = [0wxFFFF,0wxFFFF] : Word32.word list
- bignum_to_string(it, 16);
val it = "FFFFFFFF" : string
- string_to_bignum("ffffffffg", 16);

uncaught exception Bignum_illegal_char

●問題109

今まで作成した多倍長整数を使って階乗を求める関数 bignum-fact n を定義してください。ただし、引数 n は基数 (65536) 未満の整数とします。

- bignum_to_string(bignum_fact(0w10), 10);
val it = "3628800" : string
- bignum_to_string(bignum_fact(0w20), 10);
val it = "2432902008176640000" : string
- bignum_to_string(bignum_fact(0w30), 10);
val it = "265252859812191058636308480000000" : string
- bignum_to_string(bignum_fact(0w40), 10);
val it = "815915283247897734345611269596115894272000000000" : string
- bignum_to_string(bignum_fact(0w50), 10);
val it = "30414093201713378043612608166064768844377641568960512000000000000" : string

●問題110

今まで作成した多倍長整数を使って累乗を求める関数 bignum-power xs n を定義してください。引数 xs は多倍長整数、n は整数とします。

val bignum_fact = fn : Word32.word -> Word32.word list
val bignum_power = fn : Word32.word list * word -> Word32.word list

- bignum_to_string(bignum_power([0w2], 0w2), 10);
val it = "4" : string
- bignum_to_string(bignum_power([0w2], 0w8), 10);
val it = "256" : string
- bignum_to_string(bignum_power([0w2], 0w32), 10);
val it = "4294967296" : string
- bignum_to_string(bignum_power([0w2], 0w64), 10);
val it = "18446744073709551616" : string
- bignum_to_string(bignum_power([0w2], 0w128), 10);
val it = "340282366920938463463374607431768211456" : string

●解答91

リスト : 整数を多倍長整数に変換する

val base  : Word32.word = 0wx10000
val baseL : IntInf.int = 0x10000
val zero  : Word32.word list = [0w0]

fun integer_to_bignum(n) =
    let
      fun iter(0, []) = zero
      |   iter(0, a) = rev a
      |   iter(n, a) = iter(n div baseL, Word32.fromLargeInt(n mod baseL)::a)
    in
      iter(n, [])
    end

integer_to_bignum は簡単です。整数 n を基数 baseL で割り算していき、剰余を累積変数 a に格納します。あとは n が 0 になったら、a を rev で反転するだけです。このとき、a が空リストであれば、多倍長整数の 0 を表す zero を返します。

●解答92

リスト : 多倍長整数を整数に変換する

fun bignum_to_integer(xs) =
    let
      fun iter([], _, a) = a
      |   iter(x::xs, y, a) =
          iter(xs, y * baseL, Word32.toLargeInt(x) * y + a)
    in
      iter(xs, 1, 0)
    end

bignum_to_integer も簡単です。局所関数 iter でリストから要素 x を順番に取り出し、位を表す引数 y と掛け算して累積変数 a に加算します。

●解答93

リスト : 多倍長整数の論理積

(* 
 * 先頭から連続している 0 を取り除く
 * 最後尾の 0 は取り除かない
 *)
exception Empty_list

fun remove_zero([]) = raise Empty_list
|   remove_zero(xs as [_]) = xs : Word32.word list
|   remove_zero(xs as y::ys) = 
    if y <> 0w0 then xs else remove_zero(ys)

(* 論理積 *)
fun bignum_and(xs, ys) =
    let
      fun iter([], _, a) = rev (remove_zero a)
      |   iter(_, [], a) = rev (remove_zero a)
      |   iter(x::xs, y::ys, a) = iter(xs, ys, Word32.andb(x, y)::a)
    in
      iter(xs, ys, [])
    end

bignum_and は xs と ys の要素を順番に取り出して論理積を計算し、その結果を累積変数 a のリストに追加します。xs または ys が空リストになった場合、残りの要素は 0 との論理積になり結果は 0 になるので、ここで計算を打ち切ります。このとき、a をそのまま反転すると、末尾に余分な 0 が連続する場合があります。関数 remove_zero で先頭から連続している余分な 0 を取り除いてから、a を rev で反転します。

●解答94

リスト : 多倍長整数の論理和

fun bignum_or(xs, ys) =
    let
      fun iter([], ys, a) = List.revAppend(a, ys)
      |   iter(xs, [], a) = List.revAppend(a, xs)
      |   iter(x::xs, y::ys, a) =
          iter(xs, ys, Word32.orb(x, y)::a)
    in
      iter(xs, ys, [])
    end

bignum_or は xs と ys の要素を順番に取り出して論理和を計算し、その結果を累積変数 a のリストに追加します。xs が空リストになった場合、ys の残りの要素は 0 との論理和になり結果は ys と同じになります。関数 List.revAppend で a を反転して ys と連結します。revAppend(a, ys) は (rev a) @ ys と同じです。ys が空リストになった場合は、a を反転して xs と連結します。

●解答95

リスト : 多倍長整数の排他的論理和

fun bignum_xor(xs, ys) =
    let
      fun iter([], [], a) = rev (remove_zero(a))
      |   iter([], ys, a) = List.revAppend(a, ys)
      |   iter(xs, [], a) = List.revAppend(a, xs)
      |   iter(x::xs, y::ys, a) = iter(xs, ys, Word32.xorb(x, y)::a)
    in
      iter(xs, ys, [])
    end

bignum_xor は xs と ys の要素を順番に取り出して排他的論理和を計算し、その結果を累積変数 a のリストに追加します。xs と ys が空リストになった場合、remove_zero で連続する 0 を取り除いてから、rev で a を反転します。xs だけが空リストになった場合、ys の残りの要素は 0 との排他的論理和になり、結果は ys と同じになります。関数 revAppend で a を反転して ys と連結します。ys だけが空リストになった場合は、a を反転して xs と連結します。

●解答96

リスト : 多倍長整数の左シフト

val base_bit = 0w16
val mask : Word32.word = 0wxffff

(* b (< 16) ビット左シフトする *)
fun bignum_shift_left_bit(xs, b) =
    let
      fun iter([], c, a) =
          rev (if c = 0w0 then a else c::a)
      |   iter(x::xs, c, a) =
          iter(xs,
               Word32.>>(x, base_bit - b), 
               Word32.andb(Word32.orb(Word32.<<(x, b), c), mask)::a)
    in
      iter(xs, 0w0, [])
    end

(* リストの生成 *)
fun make_list(x, n) =
  let
    fun iter(0, a) = a
    |   iter(n, a) = iter(n - 1, x::a)
  in
    iter(n, [])
  end

(* n ビット左シフトする *)
fun bignum_shift_left(xs, n) =
    if n = 0w0 then xs
    else if n < base_bit then bignum_shift_left_bit(xs, n)
    else
      let
        val a = n div base_bit
        val b = n mod base_bit
      in
        make_list(0w0, Word.toInt(a)) @ bignum_shift_left_bit(xs, b)
      end

bignum_shift_left は引数 n が 0 の場合は xs をそのまま返します。base_bit 未満の場合は関数 bignum_shift_left_bit を呼び出します。そうでなければ、n を base_bit で除算し、商を a に、剰余を b にセットします。そして、xs を b ビットシフトした結果に a 個の 0 を先頭に追加します。

実際のビットシフトは関数 bignum_shift_left_bit で行います。局所関数 iter でリストの要素を順番に取り出します。変数 c には左ビットシフトしたときに溢れるビットをセットします。実際には、base_bit - b ビット右シフトして、下位 b ビットにセットしておきます。あとは要素 x と c の論理和を求め、それと mask の論理積を累積変数 a のリストに格納します。xs が空リストになったら、a を rev で反転します。このとき、c が 0 でなければ、a に c を追加します。

●解答97

リスト : 多倍長整数の右シフト

fun bignum_shift_right_bit(xs, b) =
    let
      fun iter([], a) = rev (remove_zero a)
      |   iter([x], a) = rev (remove_zero(Word32.>>(x, b)::a))
      |   iter(x1::x2::xs, a) =
          iter(x2::xs,
               Word32.orb(
                 Word32.>>(x1, b), 
                 Word32.andb(Word32.<<(x2, base_bit - b), mask)
               ) :: a)
    in
      iter(xs, [])
    end

fun bignum_shift_right(xs, n) =
    if n = 0w0 then xs
    else if n < base_bit then bignum_shift_right_bit(xs, n)
    else
      let
        val a = List.drop(xs, Word.toInt(n div base_bit))
        val b = n mod base_bit
      in
        if null(a) then zero else bignum_shift_right_bit(a, b)
      end

bignum_shift_right は引数 n が 0 のときは xs をそのまま返します。base_bit 未満の場合は関数 bignum_shift_right_bit を呼び出します。そうでなければ、n を base_bit で除算し、xs の先頭から商の数だけ要素を取り除き、それを a にセットします。剰余は b にセットします。もし a が空リストならば zero を返します。そうでなければ、bignum_shift_rigth_bit を呼び出して、a を b ビット右へシフトします。

実際のビットシフトは関数 bignum_shift_right_bit で行います。局所関数 iter でリストの要素を順番に取り出し、ビットシフトした結果を累積変数 a のリストに格納します。xs が空リストになったら、remove_zero で a の先頭にある 0 を削除してから rev で反転します。ビットシフトは簡単です。要素 x1 を b ビット右シフトし、次の要素 x2 を base_bit - b ビット左シフトして mask との論理積を求め、その 2 つの値の論理和を求めるだけです。

●解答98

リスト : 多倍長整数の比較

fun bignum_compare(xs, ys) =
    let
      fun iter([], [], r) = r
      |   iter([], _, _) = ~1
      |   iter(_, [], _) = 1
      |   iter(x::xs, y::ys, r) =
          let
            val n = Word32.toInt(x) - Word32.toInt(y)
          in
            iter(xs, ys, if n <> 0 then n else r)
          end
    in
      iter(xs, ys, 0)
    end

infix 4 =/ <>/ </ >/ <=/ >=/

fun op =/ (xs, ys) = bignum_compare(xs, ys) = 0
fun op <>/ (xs, ys) = bignum_compare(xs, ys) <> 0
fun op </ (xs, ys) = bignum_compare(xs, ys) < 0
fun op >/ (xs, ys) = bignum_compare(xs, ys) > 0
fun op <=/ (xs, ys) = bignum_compare(xs, ys) <= 0
fun op >=/ (xs, ys) = bignum_compare(xs, ys) >= 0

関数 bignum_compare は xs と ys が等しい場合は 0 を、xs のほうが大きい場合は正の値を、xs のほうが小さい場合は負の値を返します。

bignum_compare は 2 つのリストを順番にたどっていき、xs が先に空リストになったら -1 を、ys が先に空リストになったら 1 を返します。両方とも空リストになった場合、リストの長さが等しいので要素の値を比較します。リストをたどるとき、要素 x, y を整数に変換して x - y を計算し、その値が 0 でなければ変数 r の値を更新します。もし、r の値が 0 ならば xs と ys は同じ値であることがわかります。負の場合、ys には xs よりも大きい要素が上位の桁にあるので、ys のほうが大きいことがわかります。逆に正の場合は xs が大きいことになります。

●解答99

リスト : 多倍長整数と整数の加算

fun integer_add(x, y, c) =
    let
      val n = x + y + c
    in
      if n < base then (n, 0w0 : Word32.word) else (n - base, 0w1)
    end

fun bignum_add_int(xs, c) = 
    let
      fun iter([], c, a) = rev (remove_zero(c::a))
      |   iter(xs, 0w0, a) = List.revAppend(a, xs)
      |   iter(x::xs, c, a) =
          let
            val (n, m) = integer_add(x, 0w0, c)
          in
            iter(xs, m, n::a)
          end
    in
      iter(xs, c, [])
    end

bignum_add_int は最下位の桁と引数 c を加算し、桁上がりがあればそれを上位の桁に加算します。あとは、桁上げの処理を繰り返すだけです。整数同士の加算は関数 integer_add で行います。引数 x, y, c を加算し、その値 n が base 未満であれば n と 0 をタプルで返します。そうでなければ、n - base と 1 をタプルで返します。

●解答100

リスト : 多倍長整数の加算

infix 6 +/

fun op +/ (xs, ys) =
    let
      fun iter([], ys, c, a) =
          if null(ys) then rev (remove_zero (c::a))
          else List.revAppend(a, bignum_add_int(ys, c))
      |   iter(xs, [], c, a) =
          List.revAppend(a, bignum_add_int(xs, c))
      |   iter(x::xs, y::ys, c, a) =
          let
            val (n, m) = integer_add(x, y, c)
          in
            iter(xs, ys, m, n::a)
          end
    in
      iter(xs, ys, 0w0, [])
    end

+/ は xs と ys の要素と桁上げを表す変数 c を integer_add で加算し、その結果を累積変数 a のリストに格納していきます。xs が空リストで、かつ ys も空リストの場合、a に c を追加して、remove_zero で 0 を取り除いてから rev で反転します。ys が空リストでない場合、bignum_add_int で ys に c を加算し、その結果に a を反転したリストを連結します。ys が空リストの場合、xs は空リストではないので、xs に c を加算して、その結果に a を反転したリストを連結します。

●解答101

リスト : 多倍長整数と整数の減算

fun integer_sub(x, y, c) =
    let
      val n = base + x - y - c
    in
      if n < base then (n, 0w1 : Word32.word)
      else (n - base, 0w0)
    end

exception Bignum_underflow

fun bignum_sub_int(xs, c) =
    let
      fun iter([], c, a) =
          if c <> 0w0 then raise Bignum_underflow
          else rev (remove_zero a)
      |   iter(xs, 0w0, a) = List.revAppend(a, xs)
      |   iter(x::xs, c, a) =
          let
            val (n, m) = integer_sub(x, 0w0, c)
          in
            iter(xs, m, n::a)
          end
    in
      iter(xs, c, [])
    end

bignum_sub_int は最下位の桁と引数 c を減算し、桁借りがあればそれを上位の桁から減算します。あとは、桁借りの処理を繰り返すだけです。xs が空リストで、桁借りの値 c が正であれば、計算結果は負になるのでエラーを送出します。そうでなければ、remove_zero で 0 を取り除いてから a を反転します。

integer_sub は base + x から y と c を減算して変数 n にセットします。もし、n が base よりも小さい場合、n と桁借りを表す 1 をタプルで返します。そうでなければ、n - base と 0 をタプルで返します。

●解答102

リスト : 多倍長整数の減算

infix 6 -/

fun op -/ (xs, ys) =
    let
      fun iter([], [], c, a) =
          if c <> 0w0 then raise Bignum_underflow
          else rev (remove_zero a)
      |   iter(xs, [], c, a) =
          let
            val zs = bignum_sub_int(xs, c)
          in
            if zs = zero then rev (remove_zero a)
            else List.revAppend(a, zs)
          end
      |   iter([], _, _, _) = raise Bignum_underflow
      |   iter(x::xs, y::ys, c, a) =
          let
            val (n, m) = integer_sub(x, y, c)
          in
            iter(xs, ys, m, n::a)
          end
    in
      iter(xs, ys, 0w0, [])
    end

-/ は xs と ys の要素と桁借りを表す変数 c を integer_sub で減算し、その結果を累積変数 a のリストに格納していきます。ys が空リストで xs が空リストでない場合、bignum_sub_int で xs から c を減算し、その結果を変数 zs にセットします。zs が 0 の場合、remove_zero で 0 を取り除いてから rev で反転します。zs が 0 でなければ、revAppend で zs に a を反転したリストを連結します。xs が空リストの場合、結果は負になるのでエラーを送出します。

●解答103

リスト : 多倍長整数と整数の乗算

fun integer_mul(x, y, c) =
    let
      val n = x * y + c
    in
      if n < base then (n, 0w0 : Word32.word)
      else (n mod base, n div base)
    end

fun bignum_mul_int(xs, x) =
    if x = 0w0 then zero
    else if x = 0w1 then xs
    else
      let
        fun iter([], c, a) = rev (remove_zero(c::a))
        |   iter(x1::xs, c, a) =
            let
              val (n, m) = integer_mul(x1, x, c)
            in
              iter(xs, m, n::a)
            end
      in
        iter(xs, 0w0, [])
      end

bignum_mul_int は引数 x が 0 ならば zero を、1 ならば xs をそのまま返します。それ以外の場合、リストの最下位の桁から順番に x と掛け算して、値を累積変数 a のリストに格納します。桁上がりは変数 c に格納して、上位の桁に足し算します。整数の乗算は関数 integer_mul で行います。引数 x, y が乗算する整数、c が桁上がりで加算する値です。x * y + c を n にセットし、値が base 未満であれば n と 0 をタプルで返します。そうでなければ、n と base の剰余と商をタプルで返します。

●解答104

リスト : 多倍長整数の乗算

infix 7 */

fun op */ ([x], ys) = bignum_mul_int(ys, x)
|   op */ (xs, [y]) = bignum_mul_int(xs, y)
|   op */ (xs, ys) =
       let
         fun iter(_, [], a) = a
         |   iter(xs, y::ys, a) =
             iter(0w0::xs, ys, bignum_mul_int(xs, y) +/ a)
       in
         iter(xs, ys, zero)
       end

多倍長整数同士の乗算は筆算と同じ方法で行います。下図のように、xs を 16 bit 左シフトしながら ys の要素を掛け算し、その値を加算していけばいいわけです。

*/ は引数 xs, ys が base 未満の整数であれば、bignum_mul_int を呼び出して計算します。そうでなければ、xs と ys の要素の乗算を bignum_mul_int で求め、累積変数 a にその値を +/ で加算します。ys の次の要素を乗算するとき、xs の先頭に 0 を挿入して 16 bit 左シフトします。

なお、今回の方法は桁数が多くなると遅くなります。これよりも高速な方法として「Karatsuba 法」や「高速フーリエ変換」を使った方法があります。これらのアルゴリズムについては、Fussy さんの「乗算処理の高速化」, 「高速フーリエ変換」、M.Kamada さんの「離散フーリエ変換を用いた多倍長乗算の話」が参考になると思います。

xs : (4 3 2 1)
ys : (7 6 5)

        1   2   3   4
*           5   6   7
----------------------
        7  14  21  28
    6  12  18  24   0
5  10  15  20   0   0
----------------------
5  16  34  52  45  28

図 : 多倍長整数の乗算

●解答105

リスト : 多倍長整数と整数の除算

fun integer_div(x, y, c) =
    let 
      val n = c * base + x
    in
      (n div y, n mod y)
    end

exception Bignum_div_by_zero

fun bignum_div_int(xs, x) =
    if x = 0w0 then raise Bignum_div_by_zero
    else if x = 0w1 then (xs, zero)
    else
      let
        fun iter([], c, []) = (zero, [c])
        |   iter([], c, a) = (a, [c])
        |   iter(x1::xs, c, a) =
            let
              val (n, m) = integer_div(x1, x, c)
            in
              iter(xs, m, if n <> 0w0 orelse not(null(a)) then n::a else a)
            end
      in
        iter(rev xs, 0w0, [])
      end

bignum_div_int は引数 x が 0 の場合はエラーを送出し、1 の場合は xs と 0 をタプルで返します。それ以外の場合は、xs の上位の桁から順番に整数 x で除算していきます。このため、xs を rev で反転しています。局所関数 iter の変数 c には上位の桁の余りをセットします。あとは、関数 integer_div で xs の要素と x の除算を行います。このとき、c * base を加えてから x で割ることに注意してください。あとは商と剰余をタプルで返します。

bignum_div_int は上位の桁から処理を行うため、リストの末尾に 0 が付加されないように工夫する必要があります。値が 0 でない場合、または累積変数 a が空リストでない場合、値を a に追加します。それ以外の場合、つまり、a が空リストで値が 0 の場合は追加しません。最後に、a が空リストであれば zero と [c] を、そうでなければ a と [c] をタプルで返します。

●解答106

多倍長整数の除算は筆算と同じ方法で行いますが、かなり複雑な処理になります。ここではアルゴリズムの概略を説明するだけにとどめます。詳細は参考文献をお読みください。

リスト : 多倍長整数の除算 (擬似コード)

xs = (x1 x2 ... xn), ys = (y1 y2 ... ym) とし、xs / ys の商と剰余を求める

*base* / 2 <= ym * d < *base* を満たす d を求め、(xs * d) / (ys * d) を計算する

xs1 = xs * d とする
xs1 と同じ桁数になるよう (ys * d) の下位に 0 を追加たものを ys1 とする
このとき、追加した 0 の個数を s とする

qs = ()
while( s >= 0 ){
  xs1 / ys1 の仮の商 q' を求める。
    (1) xs1 が ys1 よりも少ない桁数の場合、q' は 0 である
    (2) xs1 と ys1 の桁数 (n) が同じ場合、q' = xn / yn とする
    (3) xs1 が n 桁, ys1 が n - 1 桁の場合、
        q' = min( (xn * base + xn-1) / yn-1, base - 1 ) とする

  if( q' > 0 ){
    ys2 = ys1 * q'
    while( xs1 < ys2 ){
      q' = q' - 1
      ys2 = ys2 - ys1
    }
    xs1 = xs1 - ys2
  }

  q' を qs に追加する
  ys1 の最下位から 0 を取り除く
  s = s - 1
}

商は qs, 剰余は xs1 / d となる。

ポイントは仮の商 q' を求める処理です。ys1 の最上位の桁 ym が条件 (A) base / 2 <= ym < base を満たしている場合、(2) であれば q' は 0 か 1 になります。(3) であれば xs1 の上位 2 桁と ys1 の上位 1 桁 (ym) から仮の商を求めます。このとき、真の商を q とすると、条件 (A) を満たしているならば次の式が成り立ちます。

q <= q' <= q + 2

したがって、q の値は q', q' - 1, q' - 2 のどれかになります。ys2 = ys1 * q' を計算し、xs1 < ys2 であれば q' から 1 を、ys2 から ys1 を引き算します。これを xs1 >= ys2 になるまで繰り返しますが、最悪でも 2 回の繰り返しで済むわけです。

商 q が q' - 1 と q' - 2 になる例を示します。

xs1 = [0w65535, 0w65535, 0w32767]
ys1 = [0w65535, 0w32768]

q' = (32767 * base + 65535) / 32768 = 65535
ys2 = [0w65535, 0w32768] * 65535 = [0w1, 0w32766, 0w32768] > xs1

q' = q' - 1 = 65534
ys2 = ys2 - ys1 = [0w2, 0w65533, 0w32767] < xs1

q' = 65534, xs1 = xs1 - ys2 = [0w65533, 0w2]

-----------------------------------------------------
xs1 = [0w65535, 0w0, 0w32767]
ys1 = [0w65535, 0w32768]

q' = (32767 * base + 0) / 32768 = 65534
ys2 = [0w65535, 0w32768] * 65534 = [0w2, 0w65533, 0w32767] > xs1

q' = q' - 1
ys2 = ys2 - ys1 = [0w3, 0w32764, 0w32767] > xs1
q' = q' - 1
ys2 = ys2 - ys1 = [0w4, 0w65531, 0w32766] < xs1

q' = 65532, xs1 = xs1 - ys2 = [0w65531, 0w5]

なお、(3) を満たしているとき、より高い精度で仮の商 q' を求める方法があります。有名なクヌース先生のアルゴリズムＤはこの方法を使っています。除算のアルゴリズムについては、参考文献 [2] がわかりやすくまとまっていると思います。また、乗算の処理が高速な場合、ニュートン法で ys の逆数 1 / ys を求め、xs * (1 / ys) を計算することで除算を高速に実行することができます。

擬似コードをそのままプログラムすると次のようになります。

リスト : 多倍長整数の除算

val half_base : Word32.word = 0wx8000

(* シフトするビット数を決める *)
fun get_shift_bit(n) =
    let
      fun iter(n, c) =
          if n >= half_base then c
          else iter(Word32.<<(n, 0w1), c + 0w1)
    in
      iter(n, 0w0)
    end

(* 仮の商を求める *)
fun get_quot([], _) = 0w0
|   get_quot([x], [y]) = x div y
|   get_quot(x1::x2::xs, [y]) = (x2 * base + x1) div y
|   get_quot(_::xs, _::ys) = get_quot(xs, ys)

fun last([]) = raise Empty_list
|   last([x]) = x
|   last(_::xs) = last(xs)


(* 商と剰余を返す *)
fun bignum_div(xs, [y]) = bignum_div_int(xs, y)
|   bignum_div(xs, ys) =
    if xs </ ys then (zero, xs)
    else
      let
        val d = get_shift_bit(last(ys))
        val xs1 = ref (bignum_shift_left(xs, d))
        val s = ref (length(!xs1) - length(ys))
        val ys1 = ref (bignum_shift_left(ys, base_bit * Word.fromInt(!s) + d))
        val q = ref []
      in
        while !s >= 0 do
          let
            val quot = ref (Word32.min(get_quot(!xs1, !ys1), base - 0w1))
            val ys2 = ref (bignum_mul_int(!ys1, !quot))
          in
            if !quot <> 0w0 then (
              while !xs1 </ !ys2 do (
                quot := !quot - 0w1;
                ys2 := !ys2 -/ !ys1
              );
              xs1 := !xs1 -/ !ys2
            ) else ();
            if !quot <> 0w0 orelse not (null(!q)) then q := !quot :: (!q) else ();
            ys1 := tl (!ys1);
            s := !s - 1
          end;
        (!q, bignum_shift_right(!xs1, d))
      end

infix 7 // %/
fun op // (xs, ys) = #1(bignum_div(xs, ys))
fun op %/ (xs, ys) = #2(bignum_div(xs, ys))

関数 get_shift_bit は ys の最上位の値が base / 2 以上になるよう、左シフトするビット数を求めます。関数 get_quot は仮の商を求めます。xs が空リストならば、xs の桁は ys よりも少ないので 0 を返します。ys が末尾の要素で、かつ xs も末尾の要素であれば、同じ桁数なので x / y を返します。そうでなければ、xs の上位 2 桁を求め、それを y で割り算します。関数 bignum_div は説明をそのままプログラムしただけなので、とくに難しいところはないと思います。

●解答107

リスト : 多倍長整数を文字列に変換する

val char_table = [#"0", #"1", #"2", #"3", #"4", #"5", #"6", #"7",
                  #"8", #"9", #"A", #"B", #"C", #"D", #"E", #"F"]

fun bignum_to_string(xs, r) =
    let
      fun iter(xs, a) =
          if xs =/ zero then implode(a)
          else
            let
              val (n, m) = bignum_div_int(xs, Word32.fromInt(r))
            in
              iter(n, List.nth(char_table, Word32.toInt(hd m)) :: a)
            end
    in
      iter(xs, [])
    end

bignum_to_string は簡単です。bignum_div_int で xs を基数 r で割り算し、char_table から m 番目の要素を求め、それを累積変数 a のリストに追加します。この処理を xs が 0 になるまで繰り返し、最後に関数 implode で a を文字列に変換します。

●解答108

リスト : 文字列を多倍長整数に変換する

fun position_if pred xs =
  let
    fun iter [] _ = NONE
    |   iter (x::xs) i = if pred x then SOME i else iter xs (i + 1)
  in
    iter xs 0
  end

(* 文字列を多倍長整数に変換 *)
exception Bignum_illegal_char

fun string_to_bignum(str, r) =
    let
      fun iter([], a) = a
      |   iter(x::xs, a) =
          let
            val n = position_if (fn(y) => y = Char.toUpper(x)) char_table
          in
            if isSome(n) andalso valOf(n) < r then
              iter(xs, bignum_add_int(bignum_mul_int(a, Word32.fromInt(r)), 
                                      Word32.fromInt(valOf(n))))
            else raise Bignum_illegal_char
          end
    in
      iter(explode(str), [0w0])
    end

string_to_bignum も簡単です。文字列 str を関数 explode でリストに変換し、局所関数 iter で 1 文字ずつ順番に取り出します。そして、関数 position_if で文字を数値 n に変換します。このとき、英小文字を Char.toUpcase で英大文字に変換しています。文字が見つからない場合、または n が基数 r 以上の場合はエラーを送出します。あとは、bignum_mul_int で累積変数 a と基数 r を掛け算し、それに bignum_add_int で n を加算していくだけです。最後に a を返します。

●解答109

リスト : 階乗

fun bignum_fact(0w0) = [0w1]
|   bignum_fact(n) = bignum_mul_int(bignum_fact(n - 0w1), n)

bignum_fact は引数 n が base 未満の整数なので、bignum_fact の返り値と n を bignum_mul_int で掛け算していくだけです。

●解答110

リスト : 累乗

fun bignum_power(xs, n) =
    if n = 0w0 then [0w1]
    else
      let
        val ys = bignum_power(xs, n div 0w2)
        val zs = ys */ ys
      in
        if n mod 0w2 = 0w0 then zs
        else zs */ xs
      end

bignum_power を再起呼び出しして xs^n/2 を求め ys にセットし、ys */ ys を計算して zs にセットします。n が偶数の場合は zs を返し、そうでなければ、xs */ zs を計算して返します。