bignumber.nim

Nimで多倍長整数と多倍長浮動小数点数を実装しました。この実装は私がSPOJ Constantsコンテストのために書いているコードをもとにパフォーマンスの核となるFFT乗算を除き、代わりにToom-Cook乗算を追加したものです (English README)。

特徴

• 多倍長整数型のBigIntと多倍長浮動小数点数型のBigFloatを実装しています（基数は1E16です）
• Nimの標準ライブラリのみに依存しています (algorithm, math, sequtils and strutils)
• Chudnovskyの公式を使用した円周率100万桁の計算が30秒以内（マシンの性能依存）に可能な程度には高速です（高速乗算アルゴリズムとしてKaratsuba, Toom-Cook 3, Toom-Cook 4.5, Toom-Cook 6.5を使用）
• 主要な演算子はオーバーロードしてあります

注意点

• FFT乗算を実装していないため巨大な桁数の計算には向きません（円周率1億桁の計算にはマシンの性能依存ですが数十分から数時間ほどかかります）
• メモリを大量に使用します（円周率100万桁の計算に40MB、1億桁の計算に3.5GB程度）
• 基数変換やビット演算は実装していません
• 並列化には対応していません
• BigFloatを文字列に変換すると、指定した精度より最大31桁多く変換されます
• 除算は除数の桁数に関わらずニュートン除算で実装しているため、n桁 / 1桁のような除算にもO(n)ではなくO(n^1.338)の時間がかかります（要改善）

TODO

• 基数変換、ビット演算、並列化
• 数論変換による乗算（浮動小数点数を使用したFFTによる乗算は高速ですが、メモリ使用量・丸め誤差・SPOJ用のコードの公開を避けたい等の理由により実装の予定はありません）
• 数学関数

API Documents

API Documents (generated by "nim doc" command)

License

MIT License