2007-12-01から1ヶ月間の記事一覧

関数の速度(7)

並列処理を使うと速くなることがある。 具体的にはSSEを使うと速くなることがある。 http://www.intel.co.jp/jp/download/index.htm SSEというのは、floatを4つ並べて一つの命令でまとめて計算する技術である。例えば、 x[0] /= y[0]; x[1] /= y[1]; x[2] /=…

関数の速度(6)

atan2 とにかくこれを速くしたい。 場合分けはあとまわしにして、まずは、0 前回のatanがそのまま使えて、 y /= x; double y2 = y * y; return y * (((256 * y2 + 5943) * y2 + 19250) * y2 + 15015) / (((1225 * y2 + 11025) * y2 + 24255) * y2 + 15015);y…

関数の速度(5)

前回求めた有理関数を展開すると、 h1とh2が近そうだが、実際に[1,2]で最大誤差を見てみると、 0 : error = 0.00520393 1 : error = 0.000249046 2 : error = 0.000186153 3 : error = 0.00129726 4 : error = 0.0901862 と、h2がわずかによい。n = 5だと、 …

関数の速度(4)

log(1+x)/xを有理関数で近似するとき、テーラー展開で4次まであわせると、 となったが、4次まであわせるには、 という形などが考えられる。 その中から最適なものを選ぶべきではないだろうか。 一般に、近似したい関数を、 として、n次までの近似を求めたい…

何回コインを投げれば連続10回表が出るんだろう(4)

分布はだいたい分かったので、これで擬似乱数を調べてみよう。 100万回行って、得られた回数を100ごとに区切って、度数をみる。 VC2005EEで、rand()で得られた値の特定のビットを拾う。 if(rand() & bit) { ...bitが1の結果は、 〜100 56000 〜200 24000 〜3…

何回コインを投げれば連続10回表が出るんだろう(3)

もう一度数学的に考えてみよう。 p(m,n) = 2-n-1(1 - p(n,n) - ... - p(m-n-1,n)) がm > 2nで成り立つ。 確率の総和が1であるから、 p(m,n) = 2-n-1(p(m-n,n) + ...) これをすべて並べて、 p(2n+1,n) = 2-n-1(p(n+1,n) + p(n+2,n) + ...) p(2n+2,n) = 2-n-1(…

何回コインを投げれば連続10回表が出るんだろう(2)

この計算は、浮動小数点数だと誤差がたまってくるが、幸い2進数では有限小数になるので、ある程度の桁までは正確に計算できる。 Arrayで、2048進数で考えるとプログラミングがやさしくなる。 例えば、3 + 11/2048 + 13/2048^2 → [ 3, 11, 13 ]とする。 10万…

何回コインを投げれば連続10回表が出るんだろう(1)

http://blogs.wankuma.com/episteme/archive/2007/12/13/112757.aspx この分布を擬似乱数で出すのは難しい、擬似乱数の質を調べるのによい題材、ということだと思う。 しかし、それにはまず正しい分布を知ることが必要。 というか、私にはそちらを出すほうが…

関数の速度(3)

前々回、expがsin/cosより速いのが気になった。 また、logがatanより速いのも気になった。 exp(x) 35ns sin(x) 45ns cos(x) 45ns log(x) 43ns atan(x) 87ns 数学的には、expとsin/cosは同類である。 logとatanもテーラー展開すれば似たようなものである。 そ…

関数の速度(2)

前回、 double x = 0.5; for(int i = 0; i sum += exp(x); x += dx; // dx = 1e-8 }とした、すなわち、 exp(0.5) + exp(0.50000001) + exp(0.50000002) + ... を計算しているのは、確実にexpをN回計算するため。 これを、 double x = 0.5; for(int i = 0; i …

関数の速度(1)

私はいつも実行速度と戦っている。 遅さの原因がどこにあるかと探ると、 そこにはたいてい atan2 がある。 テーブルを作って速くしたりしているが、劇的には速くならない。 やはり肝心なのはatan2を使わないこと。 atan2の使用を避ける方法をいつも考えてい…

JavaScriptのStringは値?

http://blog.livedoor.jp/dankogai/archives/50963275.htmlえー! http://d.hatena.ne.jp/odz/20071206/1196927108ここにあるようにReadOnlyなだけだと思ってた。 var str = "a"; var str2 = str; // アドレスをコピー var str3 = str.bold(); // 実体をコピ…

フィボナッチ数列の計算法(3)

前に、http://blog.livedoor.jp/dankogai/archives/50958771.htmlを見て、フィボナッチ数の計算がO(1)なのはちょっと気持ち悪いがいいんじゃない?と思ったが、この続きのような記事を見て、ハッとした。http://blog.livedoor.jp/dankogai/archives/50962361…

フィボナッチ数列の計算法(2)

前回の宿題。 べき乗計算に指数の計算を使う(powを使う)場合、80ビット浮動小数点数を使うと、フィボナッチ数列を何項目まで正しく求められるだろうか。 D言語でIntelの場合、realは80ビット浮動小数点数となる。これを用いた計算と、64ビット整数で前回の…