高速逆平方根(fast inverse square root)のアルゴリズム解説 - 滴了庵日録
高速逆平方根とは？ C言語のコード 検証 アルゴリズムの要点 [1] 逆平方根の計算を対数・指数の計算に置き換える [2] 浮動小数点型の内部表現を利用した対数・指数の近似計算 [2.1] 対数の近似 [2.2] σの最適値 [2.3] 整数型での解釈 [2.4] 逆平方根の計算とマジックナンバー0x5F3759DF [3] ニュートン法による収束で精度アップ 感想 高速逆平方根とは？ 高速逆平方根(fast inverse square root)とは、平方根の逆数 を高速に計算するアルゴリズムです。平方根の逆数は逆平方根とも呼ばれます。逆平方根はベクトルの正規化などに用いられるので、これを高速に計算できるアルゴリズムには大きなご利益があります。 参照： Fast inverse square root - Wikipedia C言語のコード 高速逆平方根の関数を示します。0x5F375
PHP の壊れた mt_rand の品質を統計的に検証した - iwiwiの日記
メルセンヌ・ツイスターと似て非なるアルゴリズムが実装されていたことが発覚して話題の PHP の mt_rand 関数の品質を統計的に検証しました．果たして，PHP の「壊れた」mt_rand は安心して使うことができるのでしょうか……？ ちなみに，結論から言うと，PHP の壊れた mt_rand は，（少なくともこのテストの範囲では）本家メルセンヌ・ツイスターと遜色ない品質を持っているようです．ただし，最後に PHP の乱数の別の懸念点についても紹介します． 壊れた mt_rand とは PHP の mt_rand は，ドキュメントによると，有名な乱数生成アルゴリズム「メルセンヌ・ツイスター」を利用して高品質の乱数を生成する関数です．ところが，どうやら一部では知られていたこととして，PHP の mt_rand の実装にはバグがあり，本家メルセンヌ・ツイスターと挙動が一致していませんでした．
Google Chromeが採用した、擬似乱数生成アルゴリズム「xorshift」の数理
2015年12月17日、Google Chrome の JavaScript エンジン（処理系）である V8 の公式ブログにて、 JavaScript の標準的な乱数生成APIである Math.random() の背後で使われているアルゴリズムの変更がアナウンスされました。 Math.random() 関数は JavaScript を利用する際には比較的よく使われる関数ですので、親しみのある方も多いのではないかと思います。 新たなバグの発見や、従来より優秀なアルゴリズムの発見によってアルゴリズムが変更されること自体はそれほど珍しくはないものの、 技術的には枯れていると思われる Math.random() のような基本的な処理の背後のアルゴリズムが変更されたことに驚きを感じる方も少なくないかと思いますが、 それ以上に注目すべきはその変更後のアルゴリズムです。 実際に採用されたアルゴリズムの原
Gauche Devlog - Fun with primes
About On development of Gauche, and other topics related to Lisp/Scheme in general. More details. Author Shiro Kawai, shiro at acm dot org. Recent Entries Exact and repeating decimalsRunning prebuilt Gauche on GitHub workflowCaching formatter procedurePipeworksReal numerical functionsPretty print indentationSegmented completionHints for unbound variable error:immutable slot optionSource info propa
続・エラトステネスの無限の篩 - 水底で思うこと
本題の前に、前回のコードを少し書き換えた*1ので、まずはそちらから。 ♯エラトステネスの無限の篩 Ver.1 アルゴリズム上の変更点は倍数リスト*2を「n を除く n の倍数」ではなく、「n^2 を初期値とする n の倍数」にしただけです。 (defn- diff-seq [s1 s2] (let [x1 (first s1), x2 (first s2)] (cond (= x1 x2) (recur (rest s1) (rest s2)) (> x1 x2) (recur s1 (drop-while (partial > x1) s2)) (< x1 x2) (let [[s1a s1b] (split-with (partial > x2) s1)] (lazy-cat s1a (diff-seq s1b s2)))))) (defn- arithmetic-seq [start
はてなブログ | 無料ブログを作成しよう
プロデューサー目線、裏読みコンテンツの氾濫：一億総「裏方」化時代を診断する ●「え？さっきのオタク、君の知り合いじゃないの？」 今から20 年近く前。あるレコード会社の新人スタッフだった私は、某人気声優さんのコンサート会場に手伝い要員として参加しました。沢山のお客さんで賑わう物販ブースの傍らで、先輩社員やマネージメントのスタッフ…
アトキンのふるい - 2011-02-09 - 兼雑記
http://cr.yp.to/papers/primesieves.pdf を斜め読みしました。ドメインからわかる通り、 djb が共著なんですよね…アトキンさんが考えたふるいを djb が実装した、って感じですかね、たぶん。 N までの素数を高速に求める方法、って言うと誰でも思いつくのはアリストテレスエラトステネスさんのふるいで、誰でも意味がわかるし速いしでいいものなのですが、それより速くしましたよーという。具体的にはアリストテレスエラトステネス O(N log(N) log(log(N))) に対して O(N / log(log(N))) だそうです。 アイデアとしては、奇数を 4N+1 と 12N+7 と 12N+11 に分類して(4N+1 が 12N+1 と 12N+5 をカバーしてることと、 12N+3 と 12N+9 はどうせ 3 の倍数なんで自明に素数じゃないことを考えると
2008-04-11 - Marriage Theorem 新居 真面目な話ばかりでも何なので、少し中和
元ネタはこちらの記事にある、「論説 数学のすすめ 科学と技術の基盤守ろう」という上毛新聞の2008年3月30日付の論説の紹介。日本における数学研究の「危機的な状況」についての現状と、主に産業界との連携という観点からの改善策についての提言、といった内容なのですが、その論説の結びが以下。 和算は、刺激となり活用の場ともなる自然科学が日本になかったため、十分に発達しなかった。数学研究が同じ道をたどらないよう、しっかり支えたい。 「しっかり支えたい」。なんとも目頭が熱くなる言葉じゃないですか。 数学者の一人として、この論説の筆者ならびに掲載紙である上毛新聞の方々にお礼申し上げます。 元ネタの紹介記事には、こんなことも書かれてありました。 その点からすると、どうしても数学科の人間は「純粋数学の方が高尚だ」と感じてしまいがちだが、その考え自体を改めていくべきなのだと思う。 自分も以前は多少そういうこと
エラトステネスのふるい on JavaScript-1.7/1.8 - ラシウラ
「エラトステネスのふるい」は、平行プログラミングの基礎的な例としても用いられる。この場合は、各ふるい(sieve)は最初に受け取ったものを素数とし、その担当の素数の倍数を受け取ったらふるい落とし、そうでないものを受け取ったら次のふるいへ渡すコードになる。そして各ふるいがactorとして自律する。このふるいをJS1.7以降のgeneratorで記述している。 <?xml version="1.0"?> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <script type="text/javascript;version=1.8">//<
フィボナッチ数とひまわり - まめめも
最近何かと話題のフィボナッチ数計算の高速化ですが、 F(n) = (fib(n+1), fib(n)) （2次元の縦ベクトルだが表記の都合で横に書く） A = ((1, 1), (1, 0)) （第1行が(1, 1)で第2行が(1, 0)の行列） すると，F(n) = A F(n-1) = A A F(n-2) = A A A F(n-3) = ...となるから，F(n)を計算するためには，Aのn乗を計算して，それに右からF(0)をかければ良いことになる。 計算量の工夫でプログラムは劇的に速くなる 以前この記事を読んだときも、ははー、と思ったのですが、そのときは実装してみなかったのでちょっと実装してみました。 require "matrix" def fib(n) aux = proc do |m, a| case m when 0 then Matrix.I(2) when 1 then
The Aggregate Magic Algorithms
There are lots of people and places that create and collect algorithms of all types (here are a few WWW sites). Unfortunately, in building systems hardware and software, we in The Aggregate often have found it necessary to do relatively obscure low-level things very efficiently. Many of the tricks we've devised or collected either require assembly language coding or are not entirely portable when
てっく煮ブログ - 四則演算を JavaScript で実装する
aki note ≫ Google 電話面接を受けました orz （いまは消えてるけど）にて割り算が壊れました。自分で実装してみてくださいという質問が紹介されていた。せっかく(?)の機会なので、割り算だけでなく、四則演算を全部壊してみて、JavaScript で実装して見ることにした。JavaScript を選んだのは、コンパイル不要、ビット演算がある、Firebug で手軽に確認できる、という理由から。それ以上の深い意味はない。ということで、次のような問題に一般化してみた。問い四則演算を JavaScript で実装しなさい。演算子は ==、!= およびビット演算子のみ使ってよいものとします。補足例えば、for 文で for(var i = 0; i { // ... } と書くためには、++ 演算子は次のように定義できる。 function increment(i){ var c =
ブルームフィルタ - Wikipedia
この項目では、確率的データ構造について説明しています。画像にぼかし効果を付加する画像フィルタについては「川瀬のブルームフィルター」をご覧ください。 ブルームフィルタ（英語: Bloom filter）は、1970年に Burton H. Bloom が考案した空間効率の良い確率的データ構造であり、あるデータが集合の要素である（集合に含まれている）かどうかの判定に使われる。ただし判定は正確ではなくて、含まれていないのに含まれていると誤って判定すること偽陽性（false positive）の可能性がある。しかし含まれているものを含まれていないと誤判定すること偽陰性（false negative）はない。なお集合に要素を追加することはできるが、集合から要素を削除することはできない（ただし、拡張をした counting filter であれば削除もできる）。集合に要素を追加していくにつれて偽陽性の
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
はてなブログ | 無料ブログを作成しよう
基礎から学ぶコンピュータ