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

syghの新フラグメント置き場

プログラミングTipsやコード断片の保管場所です。お絵描きもときどき載せます。

第2留置場の開設

プログラミングTips

OCNブログの無料プランがいいかげん使いづらくなってきたというか今まで目をそらしてきた「そもそもプログラミング記事向けのサービスじゃない」ことをようやく認めたので分割移転を始めることにしました。移転元はこちら

今後は、はてなブログのほうでは主にWindowsのクライアント アプリ(デスクトップがメイン、ストア アプリ少々)関連のTips系記事を書いていくつもりです。プログラム言語はC++C#がメインで、Direct3DOpenGLWPF、MFCあたりを使ったグラフィックス プログラミングが一応得意分野です。仕事でもやってます。

// Visual C# 2012 の他、Ideone でも動作確認済み。
// http://ideone.com/
using System;
using System.Linq;

class Test
{
  static void Main()
  {
    Func<int, bool> isPrime = (x) =>
    {
      return
        (x == 2) ||
        ((x > 2) && ((x & 1) != 0) && ((Math.Pow(2, (x - 1)) % x) == 1));
    };
    var list = Enumerable.Range(0, 100);
    var primes =
      from x in list
      where isPrime(x)
      select x;
    foreach (var p in primes)
    {
      System.Console.WriteLine(p);
    }
  }
}

はてな記法によるシンタックス ハイライトのテストも兼ねて、C#フェルマーの小定理を使った確率論的素数判定コードを書いてみました。元ネタはココ。コード中の、

Math.Pow(2, (x - 1)) % x

フェルマーの小定理における底 a = 2 の場合のべき剰余の計算です。
2のべき乗は、べき指数yが小さいうちはintやlongのシフト演算でもよいのですが、(y >= 32)の場合はintでは対応不能、(y >= 64)の場合はlongでも対応不能になるのでdoubleを使っています。実はMath.Pow()の演算結果は2の50乗以降からdouble精度の限界である10進16~17桁を超えて桁落ちしているんですが、2のべき剰余を使った場合は一応今回の範囲内で正しく計算できてます。3のべき剰余を使った場合は32乗以降から桁落ちしますが、途中から結果がおかしくなります。なお、フェルマーの小定理を使用した素数判定はあくまで確率論的手法のため、大きな数の素数判定において1回の試行では誤判定する可能性があります。判定精度を上げるためには試行回数を増やす(底aのパターンを増やす)必要があるほか、巨大な整数を扱えるBigInt型を作成する(もしくはモンゴメリ乗算を使うなりして、べき剰余の途中計算自体を工夫する)必要があります。

いいですねはてなブログ。気に入りました。C# 3.0以降のキーワードには対応してないっぽいですが……
ただファイルストレージ機能は残念ながらはてな無料プランにはないようなので、自作ソフトウェアの実行プログラム バイナリとかを公開するときは、SkyDriveとかOCNブログにアップしたファイルへのリンクを張るしかないのか……
一長一短ね。
ちなみにWindowsではデフォルトで本文がTrebuchet MS+メイリオになり、codeブロックのフォントがConsolas+メイリオになるみたいですね。Trebuchet MSはあまり好きじゃないんですが……