スターリングの近似 - Wikipedia
この記事には参考文献や外部リンクの一覧が含まれていますが、脚注によって参照されておらず、情報源が不明瞭です。 脚注を導入して、記事の信頼性向上にご協力ください。（2015年12月） log n! と n log n − n は n → ∞ のとき漸近する スターリングの近似（英: Stirling's approximation）またはスターリングの公式（英: Stirling's formula）は、階乗、あるいはその拡張の一つであるガンマ関数の漸近近似である。名称は数学者ジェイムズ・スターリング（英語版）にちなむ。 スターリングの近似は精度に応じていくつかの形がある。応用上よく使われる形の公式は、ランダウの記号を用いて、 である。O(log n) における次の項は (1/2)log 2πn である。故に、次によい近似の漸近公式（英語版）は である[1]。（ここで記号 は両辺の比が（n
スターリングの公式
階乗n!というものは、nが大きくなると計算が大変である。 5!=1×2×3×4×5=120 ぐらいなら簡単だが 13!=1×2×3×4×5×6×7×8×9×10×11×12×13=6227020800 あたりになると、かなり大変である。 そこで、階乗の計算を別の式で近似しようというのがスターリングの公式というものである。 これは あるいは とあらわされる。 定積分がうまくできない場合、積分がグラフ上の面積を求めることであることから、積分領域を長方形に分割して近似的に計算してしまう方法がある。（参考：Excelで積分する） この上の赤い部分の面積を計算する代わりに、下のように分割した長方形の面積を求める。 これと逆の発想で、長方形の面積の合計を積分で表すことを考える。 20!を求めてみよう。 いきなり20!を求めるのではなく、ちょっと工夫してloge20!を求めてみる。 l
しかしSVMも最近は速いらしい - 射撃しつつ前転 改
Complement Naive BayesがSVMより速いよーと主張していたので、SVMもなんか最近は速くなってるらしいよ、という事を紹介してみたい。近年はSVMなどの学習を高速に行うという提案が行われており、実装が公開されているものもある。その中の一つにliblinearという機械学習ライブラリがある。ライブラリ名から推測できる通り、liblinearではカーネルを使うことが出来ない。しかし、その分速度が速く、大規模データに適用できるという利点がある。 liblinearを作っているのはlibsvmと同じ研究グループで、Chih-Jen Linがプロジェクトリーダーであるようだ。libsvmはかなり有名なライブラリで、liblinearにはそういった意味で安心感がある。（liblinearの方は公開されてしばらくは割とバグがあったらしいけど。） liblinearにはL1-SVM, L
『【DiGRA公開講座】モンテカルロ木探索とは何か？』
将棋と比べて囲碁の評価関数を難しくしているのは、 ・将棋の駒は種類ごとに機能と優劣に差があるが、囲碁の石にはそれがない。 ・リバーシにおける角のように、明らかな特徴を持った場所が少ない。 ・支配領域の広さを基準としても、領域が確定するのはゲーム終了時になる。 ・局所的な最善手が全体の最善手ではなく、相手に取らせるためにわざと置く「捨石」というテクニックが常套となっている。 などの点で、さらに上級者の間でしか理解できないような評価基準が存在する。 ・石の厚い薄い 石の厚みは物理的厚さではなく、ある石の配置が全局的に与える影響のこと。 ・形の良し悪し 複数の石の配置の評価。良い形になるように、悪い形にならないように注意することにより、「打ち筋が良くなる」効果がある。ただし「愚形の妙手」も多数存在する。 「代表的な悪い形」 ┼┼┼┼┼┼ ┼┼●┼┼┼ ┼┼●●┼┼ アキ三角 ┼┼┼┼┼┼ ┼┼●
The Danger of Naïveté
07 Dec 2007 The Danger of Naïveté In my previous post on shuffling, I glossed over something very important. The very first thing that came to mind for a shuffle algorithm is this: for (int i = 0; i < cards.Length; i++) { int n = rand.Next(cards.Length); Swap(ref cards[i], ref cards[n]); } It's a nice, simple solution to the shuffling problem: Loop through each card in the deck. Swap the current c
ランダムソート(笑)とは - 西尾泰和のはてなダイアリー
誰が「ソートするときに比較関数に『ランダムに1か-1を返す関数』を与えたらシャッフルできる」って言い出したのかしらないけど、真に受ける方も真に受ける方だと思う。 たとえばソート関数が下のような「リストの先頭の値をピボットにしてそれより大きいものと小さいものに振り分けるクイックソート」だったとする。比較関数の所はランダムにしてある。 >>> def quicksort(xs): from random import random if len(xs) < 2: return xs pivot = xs[0] left = [] right = [] for x in xs[1:]: if random() < 0.5: left.append(x) else: right.append(x) return quicksort(left) + [pivot] + quicksort(right
Google の秘密 - PageRank 徹底解説
INDEX はじめに PageRank の基本概念 どうやって PageRank を求めるか 現実に適用する際の問題 Namazu での実装実験 PageRank に対する個人的見解 参考文献 おまけ：「グーグル？／ゴーグル？」 Since: Thu Feb 1 18:22:44 JST 2001 Last Refreshed: Sat Jan 24 18:30:35 JST 2004 ★(2004/1/24) Yuan Huanglin氏によって 本ページの中国語訳 が作成されました。 ★(2003/7/1) 拙著『Namazuシステムの構築と活用』を改訂しました。 詳しくは サポートページをご覧ください。 ★(2003/5/20) Google に関するオンラインニュース記事一覧(日本語記事のみ)を 別ページ(googlenews.html) として分離しました。 ★(2001/2/
ICP(Iterative Closest Point)のアルゴリズム - かみやんの技術者ブログ
つくばチャレンジ２００７の出場者の技術資料にICPを使っているという人が何人かいたので、僕もICPを採用することにしました。という訳でまずはICPについて調べました。 ICPはパターンマッチングの１種なので、ちょっと人工知能的。手書き認識とか、OCRとか、音声認識とか、顔認識とかジェスチャー認識も多くはパターンマッチングが使われる。やっとソフトウェアらしい自分の領分なので楽しい。 『Efficient Variants of the ICP Algorithm』この論文が、ICPの様々なアルゴリズムについて検証していてよい感じでした。3Dのレーザーレンジファインダから得られる２つのメッシュの合成について書かれています。 この論文は、主にいろいろなアルゴリズムを試験して、何が高速であるかを検証しています。 概要 概要としては、ICPは以下の６つのステージからなります。 Selection :
diffのアルゴリズム - Plan9日記
ふと見つけた「あなたが一番好きなアルゴリズムを教えてください。また、その理由やどんな点が好きなのかも教えてください」を読んで、diffのアルゴリズムを調べてみた。2つのファイルの違いを見つけるには、共通する部分が最長になるペアを見つければよい。これはLCS (Longest Common Subsequence)問題と呼ばれる。LCS問題の最適解は動的計画法を用いて求めることができるが、計算時間、メモリ使用量ともにO(MN)になる*1。これより早く、また小メモリで実行できるようにいろいろなアルゴリズムが提案されている。 テキストを比較するdiffというUnix系のコマンドがありますが、これは実は高度に数学的なエディットグラフというアルゴリズムが使われています。 [1] E.W.Myers, "An O(ND) difference algorithm and its variations"
パラメトロン計算機
久野君たちの努力により, Beautiful Codeの翻訳がでた. 以前 三省堂の洋書の棚にあるのを見たことはあったが, その時はパスした. 翻訳をみると, なにしろ多くの人がそれぞれのプログラム言語で書いた自分のプログラムを(それもかなり大きい部分を)自讚しているから, 読むのが大変そうである. 短くて面白かったのは, 33章「『本』のためにプログラムを書く」であった. 要するに平面上の3点A, B, Cの座標が与えられた時, その3点が同一直線上にあるかを判定するプログラムを書くのだ. 私がやっても多分こういうアプローチになるであろうという風に話は展開していく. まずA,Bの2点を通る直線の式を決め, 点Cがそれに乗っているかを問うもの. これは最初の2点がy軸と平行な線上にあるときの始末が面倒. 次はABを通る直線の勾配と, ACを通る直線の勾配を計算し, それらが一致するかを見る
正規分布と正規乱数 - chmod 777 myknowledge
ノイズを付加する場合に確率密度関数として正規分布を用いることがある。 これを実際にやってみたくなったので実現方法を調べてみた。自分への覚え書きとして以下に示す。 正規分布の説明は以下を参照。 http://ja.wikipedia.org/wiki/%E6%AD%A3%E8%A6%8F%E5%88%86%E5%B8%83 正規分布を表す式は以下。 正規分布に従うノイズを発生させるためには、上式における x をノイズ量として x 軸上の各点におけるノイズを f(x) で表される確率で発生させればよい。 一方、多くのプログラミング言語で提供されているのは一様乱数(ある有限の区間を区切って、その区間内で全ての実数が同じ確率（濃度）で現れるような乱数 by Wikipedia)を発生させるメソッドである。C言語でいえば stdlib.h で提供される rand() が相当する。 0より大きく(0は
はてな村の地図『HatenarMaps』を公開しました - kaisehのブログ
『はてな村』のアナロジーを本当に地図にできたら面白いだろうなと思って、週末を潰して作ってみました。TopHatenarが蓄積しているDBを一部活用したサービスになっています。 Blogopolis このサービスを簡単に説明すると、はてなダイアリーのユーザに、獲得ブクマ数に応じた領土面積を割り当て、さらに似た者同士の領土を隣接させるという試みです。 地図の全体を見渡すことで、はてダの大まかなトレンドを掴むこともできるし、スケールを拡大していけば個別記事に到達することもできます。さらに、Google Mapsで検索するような感覚ではてなidやキーワードを入力して地図を探索したり、「去年と今年で勢力図がどう変わったか」を調べることもできます。 HatenarMapsはTopHatenarと同様、Javaで開発しました。フレームワーク構成もTopHatenarと一緒で、Cubby+Mayaa+S2
綱引きに蛇口当てゲーム？！ 楽しく学ぶベイズフィルターの仕組み
付き合いたくないスパムと付き合うために 受信者の意向を無視して、一方的に送りつけられる迷惑メール（スパム）は、いまやメールボックスを雑音でいっぱいにしてしまい、大事なメールを見過ごしかねないほどの量に膨れ上がり、大きな問題となっています。 残念ながら、このようなスパムを発生源から断つような根本的な対策はいまだになく、私たちは、せめてメールサーバで受け取った大量のメール群からスパムと大事なメールを仕分けしてくれる仕組みに頼らざるを得ません。 スパムを判定する方法は、次の2つに大別することができます。 本稿では前者の方法に着目します。メールを受け取った人にとっては、メールの中身を読めば、そのメールがスパムかそうでないかを判定するのは容易なことです。スパムの定義は、メールを読む人によって変わる可能性があります。例えば、まったくゴルフをしない人にゴルフの勧誘メールが来た場合はスパムといえるでしょう
Bresenham's line algorithm - Wikipedia
Bresenham's line algorithm is a line drawing algorithm that determines the points of an n-dimensional raster that should be selected in order to form a close approximation to a straight line between two points. It is commonly used to draw line primitives in a bitmap image (e.g. on a computer screen), as it uses only integer addition, subtraction, and bit shifting, all of which are very cheap opera
アルゴリズム百選 - ユークリッドの互除法 : 404 Blog Not Found
2007年12月11日16:30 カテゴリアルゴリズム百選Math アルゴリズム百選 - ユークリッドの互除法 今回は、ユークリッドの互除法を取り上げます。 ユークリッドの互除法とは何か。小学校の時に実は習っているはずですが、忘れている方は思い出してみてください。最大公約数(Greatest Common Divisor)を確実に計算する方法です。古代から有名なこのアルゴリズムは、かつては"The Algorithm"といえばこれをさすほど有名なアルゴリズムです。 それは、コードではなく普通の言葉でも簡単に書くことが出来ます。gcd(m, n)を出すには、 mをnで割り、余りがrだとする 余りrが0なら、nがGCD。 そうでなければ、nとrのGCDを求める 互い違いに割っていくので、互除法というわけです。 function gcd(m, n){ if (m < n) return gcd(
ゲームプログラミングのための数学とか物理とか - 梶本裕介の日記
http://d.hatena.ne.jp/Isoparametric/20071203/1196686962名前につられてその本買ったのですが，ちょっと簡単すぎるよなーと言う印象でした．ゲームプログラミングとか素人のぼくが書くのもなんですが，今まで読んだ中から最初の一冊として薦める本を選ぶとすると，次のものくらいでも良いんじゃないかなーと思います．ゲームプログラミングのための数学と物理作者: DANNY KODICEK, 加藤諒, 秋山謙一, 杉山明, 中村達也出版社/メーカー: ボーンデジタル発売日: 2006/03/25メディア: 大型本ここからはゲームプログラマ目指そうとか言う方へのアドバイスになります（ぼくなんかが適当なこと言って良いのか？）が，個人的にはゲーム開発のための〜だとかプログラミングのための〜だとかだけじゃなくて，ちゃんとした数学や物理の専門書を読んでおいた方が良いと
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://www.codeblog.org/blog/akr/20060413.html
ベンチマークに迷う | 配電盤
http://www.algo.ics.tut.ac.jp/~yusuke_abe/html/2007-07-04.html
阿部めも / 2007-12-05 - 最近話題のブログ