あるデータの中から特定のデータを探す場合、データ数が少なければ力任せに探索してもなんとかなりますが、データ数が多くなると探索に時間がかかるようになります。このような場合、あらかじめデータを整理整頓しておくことで、特定のデータを高速に見つけることができるようになります。この代表的なアルゴリズムが「ハッシュ法」と「二分探索木」です。
Clojure のマップとセットには、ハッシュ法で実装された hash-map, hash-set と、「木構造」で実装された sorted-map, sorted-set があります。実用的にはそれらを使えばいいのですが、今回は Clojure のお勉強ということで、あえて二分探索木のプログラムを作ってみましょう。二分探索木はその名が示すように木構造の一種です。まずは木構造から説明します。
「木構造 (tree structer)」は「木 (tree)」とも呼ばれるデータ構造で、「節 (ノード)」と呼ばれる要素に対して、階層的な関係を表したものです。身近な例では、ディレクトリの階層構造が木にあたります。ディレクトリに「ルートディレクトリ」があるように、木にも「根 (ルート)」と呼ばれる節が存在します。
(root)
Ａ ──────── レベル０
／｜＼ ↑
／ ｜ ＼
Ｂ Ｃ Ｄ 木 レベル１
／｜＼ ｜＼ の
／ ｜ ＼ ｜ ＼ 高
Ｅ Ｆ Ｇ Ｈ Ｉ さ レベル２
／ ＼
／ ＼ ↓
Ｊ Ｋ ───── レベル３
図 : 一般的な木構造の一例
木を図示する場合、階層関係がはっきりわかるように、根を上にして、同じ階層にある節を並べて書きます。根からレベル 0、レベル 1 と階層を数えていき、最下層の節までの階層数を「木の高さ」といいます。木は、ある節から下の部分を切り出したものも、木としての性質を持っています。これを「部分木」といいます。
木は、ある節からほかの節に至る「経路」を考えることができます。たとえば、A から J には、A - B - G - J という経路がありますね。これは、ディレクトリやファイルを指定するときのパスと同じです。
ある節から根の方向にさかのぼるとき、途中で通っていく節を「先祖」といい、直接繋がっている節を「親」といます。これは、逆から見ると「子孫」と「子」という関係になります。子を持たない節をとくに「葉」と呼ぶことがあります。上図でいうと、G は J と K の親で、J は G の子になります。J は子を持っていないので葉となります。
子は、「左 < 右」の順番で節に格納するのが一般的です。これを「順序木」といいます。また、順番がない木を「無順序木」と呼びます。節が持っている子の数を「次数」といいます。上図の場合、A は 3 つの子 B, C, D を持っているので、A の次数は 3 となります。すべての節の次数を n に揃えた順序木を「 n 分木」と呼びます。
とくに、次数が 2 の二分木は、プログラムでよく使われるデータ構造です。
(root)
18
／ ＼
／ ＼
／ ＼
／ ＼
／ ＼
14 22
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 20 24
／ ＼ ／ ＼ ／ ＼ ／ ＼
11 13 15 17 19 21 23 25
図 : 二分木の一例
上図に二分木の例を示します。二分木では、節にひとつのデータを格納します。そして、その節の左側の子には小さいデータを、右側の子には大きいデータが配置されるように木を構成します。
この二分木をデータの探索に使うアルゴリズムが「二分探索木」です。二分探索木はデータの探索・挿入を高速に行うことができます。たとえば、上図の木から 19 を探してみましょう。まず root の 18 と比較します。18 < 19 ですから、右側の子をたどり 22 と比較します。今度は 19 < 22 なので左側の子をたどります。次は 20 と比較し 19 < 20 なので左側の子をたどり、ここで 19 を見つけることができます。
二分探索木の探索は「二分探索 (binary search)」と同じ原理です。左右どちらかの子をたどるたびに、探索するデータ数は半分になります。上図の場合でも、探索するデータ数が 15, 7, 3, 1 となり、最後に見つけることができました。
データ数を N とすると、単純な線形探索では平均で N / 2 回の比較が必要になりますが、二分探索木を使うと log 2 N 程度の回数で収まります。たとえば、データが 100個ある場合、線形探索では 50 回データを比較しなければいけないのに、二分探索木では 7 回程度の比較で済むわけです。ただし、これは左右の部分木のバランスがとれている理想的な状態での話です。バランスが崩れると二分探索木の性能は劣化し、最悪の場合は線形探索と同じになってしまいます。
そこで、左右のバランスを一定の範囲に収める「平衡木」が考案されています。有名なところでは AVL 木、2-3 木、B 木、B* 木などがあります。また、Ｃ++の標準ライブラリである STL (Standard Template Library) では、「2 色木（赤黒木）」というアルゴリズムが使われているそうです。今回は Clojure のお勉強ということで、単純な二分探索木をプログラムすることにします。なお、本ページでは二分探索木のことを単に「二分木」と書くことにします。
それでは、Clojure で mutable な二分木を作ってみましょう。最初に deftype で二分木を定義します。
リスト : 二分木の定義 ;; 木の定義 (deftype Node [item left right]) ;; 空の木 (def empty-tree (->Node nil nil nil)) ;; 空の木か (defn empty-tree? [node] (= node empty-tree))
二分木の節をデータ型 Node で表します。もちろん、レコードを使ってもかまいません。フィールド変数 item が二分木に格納するデータ、left が左部分木、right が右部分木を表します。変数 empty-tree が空の木を表します。フィールド変数をすべて nil にした節 (ダミーデータ) を生成して empty-tree にセットします。述語 empty-tree? は節 node が空の木であれば真を返します。
簡単な例を示しましょう。
12
／ ＼ ==> (->Node 12 (->Node 11 E E) (->Node 13 E E))
11 13
E : empty-tree
これを図で表すと次のようになります。
┌─┬─┬─┐
│12│・│・│
└─┴┼┴┼┘
│ │
┌──────┘ └─┐
↓ ↓
┌─┬─┬─┐ ┌─┬─┬─┐
│11│／│／│ │13│／│／│
└─┴─┴─┘ └─┴─┴─┘
┌─┬─┬─┐
節：│Ｉ│Ｌ│Ｒ│
└─┴─┴─┘
Ｉ：item, Ｌ：left, Ｒ：right, ／：empty-tree
図 : 二分木の構造
それでは、データを探索する関数から作ってみましょう。この処理はデータを比較して左右の部分木をたどっていくだけです。
リスト : データの探索
(defn search-tree [node x]
(if (empty-tree? node)
false
(let [r (compare x (.item node))]
(cond
(zero? r) true
(neg? r) (search-tree (.left node) x)
:else (search-tree (.right node) x)))))
関数 search-tree の第 1 引数が二分木 (節) で、第 2 引数 x が探索するデータです。二分木が空の木であれば、これ以上探索することはできません。データは見つからなかったので false を返します。そうでなければ、引数 x と節のデータ (.item node) を compare で比較し、結果を変数 r にセットします。r が 0 ならばデータを見つけたので true を返します。r が負ならば x が小さいので、search-tree を再帰呼び出しして左部分木をたどります。そうでなければ、x が大きいので右部分木をたどります。
次は、データを挿入する関数を作りましょう。探索と同様に、データを比較して木をたどっていき、木がなくなった所に新しいデータを挿入します。
リスト : データの挿入
(defn insert-tree [node x]
(if (empty-tree? node)
(->Node x empty-tree empty-tree)
(let [r (compare x (.item node))]
(cond
(zero? r) node
(neg? r) (->Node (.item node) (insert-tree (.left node) x) (.right node))
:else (->Node (.item node) (.left node) (insert-tree (.right node) x))))))
関数 insert-tree の第 1 引数が二分木 (節)、第 2 引数 x が挿入するデータです。二分木が空の木であれば、新しい節を作って返します。この返り値を節の部分木にセットします。そうでなければ、引数 x と節のデータ (.item node) を compare で比較し、結果を変数 r にセットします。
r が 0 ならばデータを見つけたので node をそのまま返します。r が負ならば x が小さいので、insert-tree を再帰呼び出しして左部分木をたどります。もしも、left が空の木であれば、ここに新しい節が挿入され、新しい部分木が返されます。r が正の場合は右部分木をたどり、データを挿入した新しい右部分木を返します。
次はデータを削除する処理を作りましょう。これは今までと違って少々面倒です。削除するデータが「葉」の場合は、それを削除するだけなので簡単ですが、木の途中のデータを削除する場合は、二分木の構成を崩さないように注意しないといけません。最初に、葉を削除する場合を説明します。下図を見てください。
14 14
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 => 12 16
／ ＼ ／ ＼ ／ ＼ ／ ＼
11 13 15 17 11 13 空 17
↑
15 を削除する 削除
図 : データの削除 (葉の場合)
15 を削除する場合を考えてみましょう。15 は「葉」にあたるので、それを削除するだけで大丈夫です。
次に、子が一つある場合を考えてみましょう。
14 14
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 => 12 15
／ ＼ ／ ／ ＼
11 13 15 11 13
16 を削除する
図 : データの削除 (子が一つの場合)
16 を削除する場合、その子である 15 と置き換えれば二分木の構成は保たれます。これも簡単ですね。問題は、子が二つある節を削除する場合です。
14 15 <- 最小値と置き換え
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 => 12 16
／ ＼ ／ ＼ ／ ＼ ／ ＼
11 13 15 17 11 13 空 17
↑
14 を削除する 削除
図 : データの削除 (子が二つの場合)
この場合、削除するデータの右部分木の中から最小値のデータ [*1] を探し、それと削除するデータと置き換えれば「右部分木 < 節 < 左部分木」の構成を崩さなくてすみます。たとえば、上図で 14 を削除することを考えてみましょう。右部分木の中で 15 が最小値なので、それと 14 を置き換えます。そして、15 を格納していた節は削除します。節が最小値を格納している場合、その節の左側の子は存在しないので、その節を削除することは簡単です。
まずは木の中から最小値を探す関数と、最小値の節を削除する関数を作成しましょう。次のリストを見てください。
リスト : 最小値の探索と削除
;; 最小値を求める
(defn search-min [node]
(cond
(empty-tree? node) nil
(empty-tree? (.left node)) (.item node)
:else (search-min (.left node))))
;; 最小値を削除する
(defn delete-min [node]
(cond
(empty-tree? node) nil
(empty-tree? (.left node)) (.right node)
:else (->Node (.item node) (delete-min (.left node)) (.right node))))
二分木の場合、最小値は簡単に求めることができます。左側の子を順番にたどっていき、左側の子がない節に行き着いたとき、その節のデータが最小値になります。関数 search-min は最小値を求めてそれを返します。
最初の節はエラーチェックです。引数が空の木であれば nil を返します。次に、左側の子の値をチェックします。もし、空の木であれば左側の子がないので、その節のデータが最小値です。格納されているデータ (.item node) を返します。そうでなければ、search-min を再帰呼び出しして左側の子をたどります。
関数 delete-min は最小値を格納している節を削除します。左側の子が空の木の節を探すのは search-min と同じです。見つけたら、もう一つの子 (.right node) を返します。そうでなければ、delete-min を再帰呼び出しして、その左部分木の中から最小値を探し出して削除します。そして、その返り値を格納した新しい節を返します。これで、最小値を持つ節が削除されます。葉の場合であれば right は空の木なので、単純に削除されることになります。
同様に、最大値を求める関数 search-max や、最大値を削除する関数 delete-max も簡単にプログラムすることができます。詳細はプログラムリスト１をお読みください。
それでは、データを削除する関数 delete-tree を作ります。まず削除するデータを探索して、見つけたら子の有無に合わせた削除処理を行います。
リスト : データの削除
(defn delete-tree [node x]
(if (empty-tree? node)
node
(let [r (compare x (.item node))]
(cond
(zero? r)
(cond
(empty-tree? (.left node)) (.right node)
(empty-tree? (.right node)) (.left node)
:else (let [min-data (search-min (.right node))]
(->Node min-data (.left node) (delete-min (.right node)))))
(neg? r)
(->Node (.item node) (delete-tree (.left node) x) (.right node))
:else
(->Node (.item node) (.left node) (delete-tree (.right node) x))))))
まず、節 node が空の木ならばデータが見つからなかったので、そのまま node を返します。この場合、データは削除されず、二分木は元のままです。次に、削除するデータ x と節のデータ (.item node) を比較します。等しい場合はその節を削除します。左部分木が空の木の場合は (.right node) を返し、右部分木が空の木の場合は (.left node) を返します。
子が 2 つある場合は、右部分木の最小値を関数 search-min で求め、その値を格納した新しい節を作ります。このとき、関数 delete-min で最小値を格納していた節を削除します。これで、削除するデータを最小値で置き換えることができます。
x と節のデータが等しくない場合は、左右の部分木をたどって削除するデータを探索します。この処理は今までと同じで、delete-tree の返り値を格納した新しい節を返します。
最後に、二分木の全データにアクセスする関数を作りましょう。二分木はデータの大小関係を使って構成されているので、ある順番で節をすべて出力すると、それはソートした結果と同じになります。「木」のすべての節を規則的な順序で回ることを「巡回 (traverse)」といいいます。このなかで、次の 3 つの方法が重要です。
名前の由来は、節のデータを出力するタイミングからきています。節に最初に到達したときに出力する方法が「行きがけ」、子を出力してその節に戻ってきたときに出力する方法が「帰りがけ」、子を出力する途中でその節に戻ってきたときに出力する方法が「通りがけ」です。
二分木は「左の子 < 節のデータ < 右の子」という関係が成り立つので、通りがけ順に出力すれば、ソートされた出力結果を得ることができます。この処理は、再帰定義を使えば簡単に実現できます。
リスト : 二分木の巡回
(defn foreach-tree [node proc]
(when-not (empty-tree? node)
(foreach-tree (.left node) proc)
(proc (.item node))
(foreach-tree (.right node) proc)))
関数 foreach-tree は二分木を通りがけ順に巡回し、格納されているデータに関数 proc を適用します。まず、二分木が空の木ならば何もしないで nil を返します。これが再帰呼び出しの停止条件となります。あとは通りがけ順の定義そのままにプログラムをするだけです。
左部分木をたどるため、(.left node) に対して foreach-tree を再帰呼び出しします。次に、節のデータ (.item node) に関数 proc を適用します。最後に右部分木をたどるため、(.right node) に対して foreach-tree を再帰呼び出しします。
それでは簡単な実行例を示しましょう。
user=> (def a (insert-tree empty-tree 5)) #'user/a user=> (def b (insert-tree a 3)) #'user/b user=> (def c (insert-tree b 7)) #'user/c user=> (search-tree c 0) false user=> (search-tree c 3) true user=> (search-tree c 5) true user=> (search-tree c 7) true user=> (search-tree c 9) false user=> (foreach-tree c println) 3 5 7 nil user=> (foreach-tree (delete-tree c 3) println) 5 7 nil user=> (foreach-tree (delete-tree c 5) println) 3 7 nil user=> (foreach-tree (delete-tree c 7) println) 3 5 nil user=> (foreach-tree (delete-tree c 9) println) 3 5 7 nil user=> (def d (reduce (fn [a x] (insert-tree a x)) empty-tree '(5 3 7 1 4 6 8 2 9))) #'user/d user=> (foreach-tree d println) 1 2 3 4 5 6 7 8 9 nil user=> (dotimes [x 11] (println x (search-tree d x))) 0 false 1 true 2 true 3 true 4 true 5 true 6 true 7 true 8 true 9 true 10 false nil user=> (def e (reduce (fn [a x] (delete-tree a x)) d '(1 3 5 7 9))) #'user/e user=> (dotimes [x 11] (println x (search-tree e x))) 0 false 1 false 2 true 3 false 4 true 5 false 6 true 7 false 8 true 9 false 10 false nil user=> (foreach-tree e println) 2 4 6 8 nil
正常に動作していますね。
ご参考までに、プロトコルを使って書き直したものをプログラムリスト２に示します。興味のある方はお読みくださいませ。
;;;
;;; tree.clj : 二分木
;;;
;;; Copyright (C) 2025 Makoto Hiroi
;;;
;; 二分木の定義
(deftype Node [item left right])
;; 空の木
(def empty-tree (->Node nil nil nil))
;; 空の木か
(defn empty-tree? [node] (= node empty-tree))
;; データの探索
(defn search-tree [node x]
(if (empty-tree? node)
false
(let [r (compare x (.item node))]
(cond
(zero? r) true
(neg? r) (search-tree (.left node) x)
:else (search-tree (.right node) x)))))
;; データの挿入
(defn insert-tree [node x]
(if (empty-tree? node)
(->Node x empty-tree empty-tree)
(let [r (compare x (.item node))]
(cond
(zero? r) node
(neg? r) (->Node (.item node) (insert-tree (.left node) x) (.right node))
:else (->Node (.item node) (.left node) (insert-tree (.right node) x))))))
;; 最小値を求める
(defn search-min [node]
(cond
(empty-tree? node) nil
(empty-tree? (.left node)) (.item node)
:else (search-min (.left node))))
;; 最大値を求める
(defn search-max [node]
(cond
(empty-tree? node) nil
(empty-tree? (.right node)) (.item node)
:else (search-max (.right node))))
;; 最小値を削除する
(defn delete-min [node]
(cond
(empty-tree? node) nil
(empty-tree? (.left node)) (.right node)
:else (->Node (.item node) (delete-min (.left node)) (.right node))))
;; 最大値を削除する
(defn delete-max [node]
(cond
(empty-tree? node) nil
(empty-tree? (.right node)) (.left node)
:else (->Node (.item node) (.left node) (delete-max (.right node)))))
;; データの削除
(defn delete-tree [node x]
(if (empty-tree? node)
node
(let [r (compare x (.item node))]
(cond
(zero? r)
(cond
(empty-tree? (.left node)) (.right node)
(empty-tree? (.right node)) (.left node)
:else (let [min-data (search-min (.right node))]
(->Node min-data (.left node) (delete-min (.right node)))))
(neg? r)
(->Node (.item node) (delete-tree (.left node) x) (.right node))
:else
(->Node (.item node) (.left node) (delete-tree (.right node) x))))))
;; 二分木の巡回
(defn foreach-tree [node proc]
(when-not (empty-tree? node)
(foreach-tree (.left node) proc)
(proc (.item node))
(foreach-tree (.right node) proc)))
;;;
;;; tree1.clj : 二分木 (プロトコル版)
;;;
;;; Copyright (C) 2025 Makoto Hiroi
;;;
;; プロトコル
(defprotocol Tree
(search-tree [this x])
(insert-tree [this x])
(delete-tree [this x])
(search-min [this])
(search-max [this])
(delete-min [this])
(delete-max [this])
(foreach-tree [this proc]))
;; 空の木
(def empty-tree)
;; 空の木か？
(defn empty-tree? [node] (= empty-tree node))
;; 二分木の定義
;; (deftype の中で ->Node は使えない? (要確認), Node. は大丈夫のようだ)
(deftype Node [item left right]
Tree
;; データの探索
(search-tree [node x]
(if (empty-tree? node)
false
(let [r (compare x item)]
(cond
(zero? r) true
(neg? r) (search-tree left x)
:else (search-tree right x)))))
;; データの挿入
(insert-tree [node x]
(if (empty-tree? node)
(Node. x empty-tree empty-tree)
(let [r (compare x item)]
(cond
(zero? r) node
(neg? r) (Node. item (insert-tree left x) right)
:else (Node. item left (insert-tree right x))))))
;; 最小値を求める
(search-min [node]
(cond
(empty-tree? node) nil
(empty-tree? left) item
:else (search-min left)))
;; 最大値を求める
(search-max [node]
(cond
(empty-tree? node) nil
(empty-tree? right) item
:else (search-max right)))
;; 最小値を削除する
(delete-min [node]
(cond
(empty-tree? node) nil
(empty-tree? left) right
:else (Node. item (delete-min left) right)))
;; 最大値を削除する
(delete-max [node]
(cond
(empty-tree? node) nil
(empty-tree? right) left
:else (Node. item left (delete-max right))))
;; データの削除
(delete-tree [node x]
(if (empty-tree? node)
node
(let [r (compare x item)]
(cond
(zero? r)
(cond
(empty-tree? left) right
(empty-tree? right) left
:else (let [min-data (search-min right)]
(Node. min-data left (delete-min right))))
(neg? r)
(Node. item (delete-tree left x) right)
:else
(Node. item left (delete-tree right x))))))
;; 二分木の巡回
(foreach-tree [node proc]
(when-not (empty-tree? node)
(foreach-tree left proc)
(proc item)
(foreach-tree right proc))))
;; 初期化
(def empty-tree (Node. nil nil nil))
次の関数を定義してください。
リスト : カッコ列の生成
(defn kakko
([proc m] (kakko proc m 0 0 '()))
([proc m x y a]
(if (== x y m)
(proc (clojure.string/join (reverse a)))
(do (when (< x m)
(kakko proc m (inc x) y (cons "(" a)))
(when (< y x)
(kakko proc m x (inc y) (cons ")" a)))))))
カッコ列の生成は簡単です。関数 kakko の引数 x が左カッコの個数、引数 y が右カッコの個数を表します。引数 a は累積変数で、文字列 "(", ")" を格納したリストです。
バランスの取れたカッコ列の場合、x, y, m には y <= x <= m の関係が成り立ちます。x = y = m の場合、カッコ列がひとつ完成しました。リスト a を反転して join で文字列を結合し、引数の関数 proc を呼び出します。そうでなければ、kakko を再帰呼び出しします。x < m であれば左カッコを追加し、y < x であれば右カッコを追加します。これでカッコ列を生成することができます。
user=> (kakko println 2) (()) ()() nil user=> (kakko println 3) ((())) (()()) (())() ()(()) ()()() nil user=> (kakko println 4) (((()))) ((()())) ((())()) ((()))() (()(())) (()()()) (()())() (())(()) (())()() ()((())) ()(()()) ()(())() ()()(()) ()()()() nil
カタラン数 - Wikipedia によると、カッコ列の総数は「カタラン数 (Catalan number)」になるとのことです。カタラン数は次に示す公式で求めることができます。
これをそのままプログラムしてもいいのですが、それではちょっと面白くないので別な方法でプログラムを作ってみましょう。カタラン数は次に示す経路図において、A から B までの最短距離の道順を求めるとき、対角線を超えないものの総数に一致します。
Ｂ Ｂ
┌─┬─┬─┬─┐ ┌─┬─┬─０─14
│ │ │ │ │ │ │ │ │ │
├─┼─┼─┼─┤ ├─┼─０─５─14
│ │ │ │ │ │ │ │ │ │
├─┼─┼─┼─┤ ├─０─２─５─９
│ │ │ │ │ │ │ │ │ │
├─┼─┼─┼─┤ ０─１─２─３─４
│ │ │ │ │ │ │ │ │ │
└─┴─┴─┴─┘ １─１─１─１─１
Ａ Ａ
図 : 道順の総数の求め方
A からある地点にいたる最短距離の道順の総数は、左隣と真下の地点の値を足したものになります。一番下の地点は 1 で、対角線を越えた地点は 0 になります。あとは下から順番に足し算していけば、A から B までの道順の総数を求めることができます。上図の場合はカラタン数 Ｃ4 に相当し、その値は 14 となります。
これをそのままプログラムすると、次のようになります。
リスト : カッコ列の総数
(defn kakko-num [m]
(loop [[x & xs :as ys] (repeat (inc m) 1)]
(cond
(not (seq ys)) 0N
(not (seq xs)) x
:else (recur (rest (reverse (reduce (fn [b x] (cons (+ x (first b)) b))
'(0N)
xs)))))))
最初に repeat で一番下の地点の道順の総数 (1) を格納したリスト生成します。これが loop / recur に渡す初期値になります。引数 m のカラタン数を求める場合、リストの大きさは m + 1 になります。あとは、リストの要素がひとつになるまで loop / recur で処理を繰り返します。
一段上の地点の値を求める場合、畳み込み reduce を使うと簡単です。初期値はリスト (0N) とします。これが対角線を越えた地点の値を表します。引数の先頭要素は不要なので、分配束縛 x & xs で分解して reduce に渡します。無名関数の引数 x が真下の地点の値、引数 b の先頭要素が左隣の地点の値になります。
あとは x と (first b) を足し算して、それを cons でリスト b の先頭に追加すればいいわけです。この場合、reduce が返すリストは逆順になるので、reverse で反転してから rest で先頭要素 (対角線を越えた地点の値) を削除します。これでカッコ列の総数 (カラタン数) を求めることができます。
簡単な実行例を示します。
user=> (dotimes [x 10] (println (kakko-num (inc x)))) 1N 2N 5N 14N 42N 132N 429N 1430N 4862N 16796N nil user=> (kakko-num 50) 1978261657756160653623774456N user=> (kakko-num 100) 896519947090131496687170070074100632420837521538745909320N