読者です 読者をやめる 読者になる 読者になる

チューリング不完全

What are you afraid of? All you have to do is try.

Vimで任意精度整数演算ができるライブラリを作った

github.com

vital.vimに「Data.BigNum」という名称でmergeされました。
vital.vimを入れればお使いいただけます。

なぜVim

Vim scriptでProject Eulerを解こうと思ったのがきっかけでした。
Project Eulerを順に解いていくと、3問目に1つの壁にぶち当たります。

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?


13195 の素因数は 5、7、13、29 である。

600851475143 の素因数のうち最大のものを求めよ。

https://projecteuler.net/problem=3

問題に出てくる数字が32bit integerの範囲(-2147483648 ~ +2147483647)を超えています。
最近登場した言語であれば標準で多倍長整数が扱えますし、そうでない言語でもそれを実現するライブラリが既にあります。
しかしVimには存在していないらしく、これではProject Eulerを解き進められない!

私は新しい言語の理解をしようとするときはProject Eulerを解きます。言語で最初に書くプログラムはHello, WorldとかFizzBuzzとか言われますが、その次にProject Eulerを解くことで基本的な数値演算、リスト/辞書の扱い方、map/filterの使い方、外部ファイルの読み込み、ライブラリの読み込み方法・・・などを段階的に学習できます。よい題材だと思います。

私はVim Scriptの理解を深めるためにVim ScriptでProject Eulerを解き進めたかったのですが、3問目で止まってしまうのは悔しい。

とにかく遅くてもいいから四則演算ができるものを作りたい、ということでググりつつ自分で野良実装をしました。
作成進捗を逐次Lingrで書いていたところ、「汎用的なのでvital化しましょう」ということでPR, 無事mergeされました。

使い方

Project Euler 3のコード例が以下です。

Project Euler 3

現状は四則演算のためのadd, sub, mul, div, 比較のためのcompare, あとは文字列とBigNumデータ間の変換をする関数などがあるだけの、ごくごくシンプルなものです。
計算時間は悲しいぐらい遅いですが、フィボナッチ数列の10000番目などもちゃんと計算することができます。

今後

基数変換、ビットシフト、高速化、BigRationalなどいろいろやりたいことがあるので、Project Eulerやりつつ機能追加できればいいなあと思っています。