カハンの加算アルゴリズム - Wikipedia
カハンの加算アルゴリズム（英語: Kahan summation algorithm、直訳するとカハンの総和アルゴリズム）とは、有限精度の浮動小数点数列の総和を計算する際の誤差を改善する計算手法・アルゴリズム。計算機において精度に制限のある計算をする場合[1]に、計算の途中の誤差を保持することで補正する。Compensated summation（補正加算）とも呼ぶ[2]。 単純に n 個の数値の総和を計算すると、n に比例して誤差が増えていくという最悪のケースがありうる。また、無作為な入力では二乗平均平方根の誤差すなわち に比例する誤差が生じる（丸め誤差はランダムウォークを形成する）[3]。補正加算では最悪の場合の誤り限界 (error bound) は n とは独立なので、多数の数値を合計しても、誤差は使用する浮動小数点数の精度に依存するだけとなる[3]。 このアルゴリズムの名は考案し
Sorting Algorithms Animations
KEY Black values are sorted. Gray values are unsorted. A red triangle marks the algorithm position. Dark gray values denote the current interval (shell, merge, quick). A pair of red triangles marks the left and right pointers (quick). DISCUSSIONThese pages show 8 different sorting algorithms on 4 different initial conditions. These visualizations are intended to: Show how each algorithm operates.
KDDI研究所、世界で誰にも解読されていない60次元LWE暗号の解読に成功
KDDI研究所は7月19日、世界でいまだ誰にも解読されておらず、スーパーコンピューターでも1万年かかるという暗号の解読に成功したと発表した。 KDDI研究所と九州大学によるもので、ドイツのダルムシュタッド工科大学で開催される暗号解読コンテスト「TU Darmstadt Learning with Errors Challenge 」において、これで誰も解読に成功していなかった60次元LWE（Learning with Errors）問題の解読に成功したというもの。 LWE問題は、故意に誤差を負荷した多元連立1次方程式を解くもので、次元（未知変数の個数）が大きくなると計算時間が膨大となり、誤差が大きいと解読できなくなる可能性があることから、暗号として用いる際には次元と誤差の量をどの程度にするのかがポイントとなる。LWE問題は60次元の計算ともなると、スーパーコンピューターを用いた総当り計算で
JavaScript開発に役立つ重要なランダムの数式まとめ - ICS MEDIA
プログラムで使うことの多い「乱数」。ゲーム開発やビジュアルアート、ウェブサイトのアニメーションにおいて乱数は非常に重要で、さまざまな用途で利用されています。プログラムで一般に乱数と聞くと、すべての数値が同じ頻度（分布）で出現する「一様乱数」と呼ばれる乱数をイメージする方が多いと思います。 多くの場合はこの「一様乱数」で取得した乱数を用いれば十分でしょう。しかし、場合によっては「一様乱数」ではなく、偏りのある乱数を用いることでコンテンツの見た目や現象の「自然さ」を演出することが可能です。 実は「一様乱数」に一手間加えることで、乱数の分布の偏りを制御できます。今回は乱数を使用して好みの分布を得るためのパターンをいくつか紹介します。 乱数分布のシミュレーションデモ （HTML5製） 次のデモはリアルタイムで乱数の出現頻度を計算し、グラフに可視化するコンテンツです。画面下のプルダウンで乱数の種類を
「遺伝的アルゴリズム」がどのような仕組みなのかが2分でわかるムービー
by fdecomite 複数の個体の中から、適応度の高い個体を優先的に選んで組み換え・突然変異などを繰り返し、解を探索していく「遺伝的アルゴリズム」がどういう仕組みなのか、2分で説明したムービーがYouTubeで公開されています。 Two Minute Papers - How Do Genetic Algorithms Work? - YouTube これは、物事を2分間で説明する「Two MinutePapers」というYouTubeのムービーシリーズの1本で、Károly Zsolnai-Fehérさんが作ったもの。 ムービーの中でわかりやすい事例としてあげられているのは、「できるだけ既定のコースを進める車を自動で生み出す」という目的を遺伝的アルゴリズムでやってみるというBoxCar2D。 三角形といくつかのタイヤをつけた「車」をコンピューターが生成、できるだけ先へ進むことを目指し
癌細胞発見に作られた、UCLAのオープンソース画像分析アルゴリズムがいろいろ使えそうです
癌細胞発見に作られた、UCLAのオープンソース画像分析アルゴリズムがいろいろ使えそうです2016.02.17 07:00 塚本 紺 百聞は一見に如かずと言いますが、目に見えないものもたくさんあるわけです。 ...いやいや、愛とかそんな話をするわけではないので安心してください。 例えば上の画像、私たちが目で見るとLED電球は左のように見えますが、右に写っているような色や模様は見えないですよね。この画像はカリフォルニア大学ロサンゼルス校のエンジニアたちが作ったアルゴリズムによって生成されたもの。このアルゴリズムを使えば通常では観察することができない画像の詳細を識別することができるそうです。 こちらのフェーズ・ストレッチ・トランスフォーム（Phase Stretch Transform）アルゴリズム。もともとは血中のガン細胞を捉える高速画像処理のために開発されたもの。輪郭と幾つかの特徴を抽出し、
乱数のたのしい話と遺伝アルゴリズム - きしだのHatena
金曜日の「プログラマのための数学勉強会＠福岡」で乱数の話をしてきました。 プログラマのための数学勉強会@福岡 #3 - connpass で、乱数の生成だとか、クイックソートや素数判定などの乱択アルゴリズムの話とかをしました。 乱数タノシイヨ 乱数のたのしい話 from なおき きしだ その中で、遺伝アルゴリズムで巡回セールスマン問題(TSP)を解くというのをやってみました。遺伝アルゴリズム、すいぶん昔から名前は知ってて、どういうアルゴリズムかも知ってて、実装もそんな難しくないと知りつつ、書く機会がありませんでした。なので、この機会に書いてみようと。 とりあえず最初に完全にランダムでTSPを解いてみます。 TSP with random ぐちゃぐちゃですね。 下部のグラフはその時点での最短距離。最初に距離が短いものをみつけていくけどだんだんみつかりにくくなる、という感じになっています。 1
ITエンジニアなら知っておきたい、今更聞けないアルゴリズムの種類一覧 - paiza times
Photo by Oferico 皆さんはアルゴリズムやデータ構造について勉強したことはありますか？そして、基本的なアルゴリズムについて、どのようなものがあって、どのようなときに使うとよいかといったことを説明することができますか？ 仕事をしていると、プログラミング言語等の勉強や業務に忙しくて、正直アルゴリズムどころではないという場合がほとんどでしょう。しかし、いつか勉強しようと思っていたけど、基本的なアルゴリズムにどんなものがあるのかなんて今更聞けないな……ということもあるかと思います。 今回はそんな方に向けて、基本的なアルゴリズムの一部の概要に加え、アルゴリズムの勉強に役立つサイト、書籍をご紹介したいと思います。 ■アルゴリズムを学ぶ意味 例えば、ソート等については、通常はすでにソート関数があるので、自分で作らなくても済む＝アルゴリズムも勉強しなくていいと思ってしまうかもしれません。しか
第12回 擬似乱数アルゴリズム、YarrowからFortunaへ | gihyo.jp
擬似乱数アルゴリズム、YarrowからFortunaへ 2015年6月末に実施されたコミットで、FreeBSD 11-CURRENTのカーネルデフォルトのエントロピー処理アルゴリズムがYarrowからFortuna（フォーチュナ、フォルトゥナ）に変更されました。RANDOM_YARROWとRANDOM_DUMMYというカーネルオプションが追加されていまして、希望するのであれば従来のYarrowを使い続けることも、ブロックするだけのドライバに置き換えることもできます。しかし、基本的にこの新しい実装をそのまま使えばよいと思います。 FreeBSDは暗号論的擬似乱数生成器の実装系にYarrowアルゴリズムを採用してきました。Yarrowアルゴリズムは特許による規制がかけられておらず、自由に利用できる状態で提供されています。FreeBSDに限らずOpenBSDやMac OS XでもYarrowアル
もうこれで悩まない！ アルゴリズムで投票先を決められる統一地方選（佐藤哲也）｜ポリタス 「統一地方選2015」私たちの選択
ものさしをつくる 今回、寄稿に際し指定されたテーマは、「投票行動に『ものさし』を提供する」でした。今ひとつ盛り上がりが感じられない選挙戦ですが、「決め手に欠ける」と感じる無党派の有権者が多そうです。沖縄や被災地といった差し迫った争点がある地域を別にすれば、選挙への関心は低調かもしれません。何とかしたいですね。 基本的に、投票行動の「ものさし」をつくるというのは容易ではありません。というより無茶に近いお題でしょう。煎じ詰めれば人が人を評価するという人類永遠の課題に対して、一定の明瞭さを備えた基準を作ることができるとは思えません。 しかし、ネット選挙解禁後の初めての統一地方選挙で、「この記事を読む方」に向けてということであれば、何らかの提案はできそうな気がします。ある程度ネットに親しんでいるはずの本サイト、この記事の（想定）読者であれば、政治家のネット親和性の観点から候補者を評価することが許さ
Berkeley algorithms help researchers understand dark energy
Berkeley algorithms help researchers understand dark energy by Linda Vu, Lawrence Berkeley National Laboratory UC Berkeley / Berkeley Lab graduate student Danny Goldstein developed a new code using the machine learning technique Random Forest to vet detections of supernova candidates automatically, in real time, optimizing it for the Dark Energy Survey. The technique employs an ensemble of decisio
ロスレス圧縮アルゴリズムの歴史
江添亮 自由ソフトウェア主義者 C++ Evangelist C++標準化委員会の委員 ドワンゴ社員 C++11本を執筆した。 株式会社ドワンゴで働いている。 Mail:boostcpp@gmail.com Twitter:@EzoeRyou GitHub: https://github.com/EzoeRyou 江添亮のマストドン@EzoeRyou 筆者にブログのネタを提供するために、品物をアマゾンお気に入りリスト経由で送りたい場合： Amazon.co.jp: 江添亮: 江添のほしい物リスト 筆者にブログのネタを提供するために、直接に品物を送りたい場合、住所をメールで質問してください。 View my complete profile ► 2020 (31) ► December (2) ► November (2) ► September (2) ► August (4) ► Jul
平方数かどうかを高速に判定する方法 - hnwの日記
平方数とは、ある整数の平方（＝二乗）であるような整数のことを言います。つまり、0,1,4,9,16,...が平方数ということになります。 ところで、与えられた整数が平方数かどうかを判定するにはどうすれば良いでしょうか。与えられた整数の平方根の小数点以下を切り捨て、それを二乗して元の数になるかどうか、というのがすぐ思いつく実装です。 <?php function is_square($n) { $sqrt = floor(sqrt($n)); return ($sqrt*$sqrt == $n); } しかし、平方根の計算は比較的重い処理です。もっと高速化する方法は無いのでしょうか。 多倍長整数演算ライブラリGNU MPには平方数かどうかを判定するmpz_perfect_square_p関数が存在します（PHPでもgmp_perfect_square関数として利用できます）。本稿ではこの実装
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - jenetics/jenetics: Jenetics - Genetic Algorithm, Genetic Programming, Grammatical Evolution, Evolutionary Algorithm, and Multi-objective Optimization
Apple、新しい圧縮アルゴリズムLZFSEをオープンソース化
Engadget | Technology News & Reviews
さまざまなソートアルゴリズムをアニメーションで学べるサイト「SORTING」 | ライフハッカー・ジャパン
さまざまなアルゴリズムをアニメーションで解説してくれる『Algomation』 | 100SHIKI
PyAlgoViz - Home
IDEA * IDEA
