昨日の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 …

JavaにあってC#にない演算子に「>>>」がある． ないのにはもちろん理由があって，そもそも必要ないからなんだけど．． どういうことかというと，Javaには符号なし変数が用意されていないので基本的にシフト演算子を使っても算術シフト(右シフト時に空いた部…

またしょーもないこと考えてみた．定義： k番目のナベアツ数N_inv(k)を第k項とする数列をナベアツ数列(nn)とする． 定理： ナベアツ数列 (nn) = 3,6,9,12,13,15,... には無限に素数が存在する． こんなもんいつ使うんだって話はとりあえず保留． ナベアツ数…

俺，ナベアツ数のこと，わかったつもりになっていた． でも本当は何もわかっちゃいなかったんだ． ナベアツ数考(2)の実験結果からも分かるとおり，N_inv(n)はy=xに漸近する関数である． これに対して二分探索でアプローチするのはあまりにも性急だった． 逆…

どうせなら逆ナベアツ数も考えてみたい． 要するにn個目のナベアツ数は何かという話． 定義： 自然数に現れる昇順でn番目のナベアツ数をN_inv(n)とする． N(N_inv(n)) = n． だけど， N_inv(N(n))は常にnになるとは限らないので，N-1(n)とは書きたくない． …

何書こうかなーと．巻頭言にとりあえず最近考えてた話でも・・ 定義： 1からnまでの自然数に現れる3の倍数或いは3のつく数（以下ナベアツ数）の総数をN(n)とする． 系： 1からnまで数えるときに世界のナベアツがアホになる回数はN(n)． nが10の○乗のときの計…