.NET Frameworkの抽象クラスSystem.Security.Cryptography.HashAlgorithmの実装としてCRC32とCRC16を求めるクラスを作った。 基本的にMD5CryptoServiceProviderやSHAxxxCryptoServiceProviderと同じように使うことができる。 CRCの計算にはいろいろな流儀が…

LarssonSadakane法で接尾辞配列を求めるプログラム。 基本的にqsufsort.cそのまんま。実行結果 10 : a 7 : abra 0 : abracadabra 3 : acadabra 5 : adabra 8 : bra 1 : bracadabra 4 : cadabra 6 : dabra 9 : ra 2 : racadabra Program.cs using System; nam…

昨日の計算時間があまりにも遅かったので，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進で一桁大きい数を用…

俺，ナベアツ数のこと，わかったつもりになっていた． でも本当は何もわかっちゃいなかったんだ． ナベアツ数考(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の○乗のときの計…