昨日のexactDivideBy3()の不具合はちゃんと調べたら修正できた． ボローを伝搬させるところのif文に誤りがあった． たとえば mag[0]=2, mag[1]=0,mag[2]=1 みたいな状況で間違えた答えになる． 正しいものに書き換えたので，Divide(3)をやめてExactDivideBy3…

昨日の計算時間があまりにも遅かったので，BigIntegerのMultiplyにKaratsuba法と3-way Toom-Cook法を追加して高速化した． 実装はここにあるものを参考にしたが，これを移植したところ，非常にまれにバグる．．自分のミスだと思うけど・・・ どれくらいまれ…

nCrの計算が高速にできたので，それを使ってn!の値の高速計算にも利用できないかなーと思って実験してみた． 任意のnについて (n:偶数) (n:奇数) が成り立つので，分割統治法で計算できる． public static BigInteger Factorial(int n) { if ((n & 1) == 0) …

折角BigIntegerを用意したのでいろいろ検証．入山徳夫氏によるnCrを高速に求めるアルゴリズムはかなり速い． n!/((n-r)!r!)は必ず整数になるので，先に約分を行って分母を消してから残りを掛け合わせる． public static BigInteger Combination(int n, int r…

BigInteger.csに平方根計算を追加した． 多倍長整数の平方根計算の速度はhttp://mitv2.net/algorithm/intsqrt2.htmlに詳しくある． ただ，ここにあるような初期値をtoString()使ったりpow()使ったりして10進で求める計算は必要なくて，2進で一桁大きい数を用…

正常に動作する次のようなEqualsメソッドを用意した状態で，何も考えずに「==」演算子をオーバーロードするとコケる． public override bool Equals(object obj) { ・・・ } // これだと arg1 が null のときに死ぬ public static bool operator ==(Class ar…

pythonとかrubyとかJavaだと最初から多倍長整数を扱うことができるけど，C#には残念ながらない． 一応J#経由で使うことはできるけど，nextProbablePrimeとかないしなあってことでJava互換な多倍長整数クラスを作ってみた． The Code ProjectのC# BigInteger …