高速剰余変換で多倍長整数の乗算をGPUで実装して円周率3億桁計算した話 - Qiita
0 はじめに この記事では高速剰余変換と実装について解説していきます。この記事を書く上で参考にしたのはこのページです。 http://ushiro.jp/method/fmt.htm http://www.cs.t-kougei.ac.jp/nsim/method/fmtbase.htm 基本的にはこのページで私が理解したとこ(+α)を解説します。多倍長整数の世界に興味のある方に少しでも面白さが伝わればと思い書きました。とか言ってますが私も全然素人です。ここではこの資料にのっとり高速剰余変換をFMT(Fast Modulo Transformation)と呼ぶこととします。 ←実は私がやってるのはNTT(数論変換)というようなものだったようで、詳しくは(FFTとNTTとFMTの違い)を見るとわかる通り剰余下でFFTやること＝FMTではなかったようで私はずっと勘違いしていました。以下FMTは
円周率を1億桁計算しました！ ― その試行錯誤の詳しい経緯と結果 ー - プログラムモグモグ
春休み暇ですし, 円周率を計算してみることにしました. エントリーが長くなりましたがお付き合いください. はじめにお断り 私は円周率計算に関しては全くの素人です. もっとスケーラブルなコードの書き方があると思いますので, あまりここばかりあてにしないでください. 時間がないせっかちな人へ コード書く試行錯誤をだらだら書いたので, 割とエントリーが長くなっちゃってます. 結論をここに書きます. 当初の目標は円周率1000万桁を計算することでした. 結局のところは, 後に上げる参考文献を実装しただけです. 計算アルゴリズムは, Chudnovskyアルゴリズムです. 最近の円周率計算の記録はこのアルゴリズムに基づいています. Gauss AGMというアルゴリズムを用いている他のソフトウェアと実行時間を比較することで, Chudnovskyアルゴリズムがいかに速いかを示しました. 円周率の小数点
書籍編集局ブログ｜Ohmsha
2月15日(木)に開催された「Developers Summit 2018(デブサミ)」（主催：翔泳社）にて「ITエンジニアに読んでほしい！ 技術書・ビジネス書大賞2018」のプレゼン大会と投票が行われ、大関真之先生の著書『機械学習入門 ボルツマン機械学習から深層学習まで』がみごと技術書部門の大賞の栄冠に輝きました！ プレゼン大会では大関先生自ら本書に関する熱い熱い思いを披露していただました。このプレゼンによって「読んでみたい！」「数式が苦手だけどこの本なら読める！」と惹きつけられるオーディエンスが続出！みごと大賞に選ばれることとなりました。ブラボー！ 本書は、おとぎ話の白雪姫に登場するお妃様と鏡の関係をなぞらえ、その問答により「機械学習とは何か」「何ができるのか」を楽しいストーリーと可愛らしくしかも的確なイラスト、そして数式をまったく用いることなく解説している画期的な内容です。 登場する
Y combinator - Rosetta Code
Y combinator You are encouraged to solve this task according to the task description, using any language you may know. In strict functional programming and the lambda calculus, functions (lambda expressions) don't have state and are only allowed to refer to arguments of enclosing functions. This rules out the usual definition of a recursive function wherein a function is associated with the state
もし先輩女子エンジニアが『アルゴリズム』を図解で教えてくれるとしたら - paiza times
2014年7月30日より8月27日まで開催した、paizaオンラインハッカソン（略してPOH![ポー！]）Lite「天才火消しエンジニア霧島 もしPMおじさんが『丸投げ』を覚えたら」ですが、どのような解法が有ったのでしょうか。 今回もPOH恒例の「解説図解」を、天才火消しエンジニア霧島が解説するとしたら、という体で書いてみたいと思います。(特に文体とか変えませんがｗ 最後に霧島壁紙DLが有るので是非最後までお読みください。) ■どのような高速化ステップがあるのか？ 今回の問題ですが、実行時間に大きく影響する計算量別にみたアプローチでは、すべての組み合わせを出して、人数を満たして一番安い組み合わせを見つける全探索[計算量はO(2^N)]と、動的計画法[計算量はq = max(q_i) としてO(Nq) ]（やり方によってはO(NM)）による2種類があります。 また全探索を改良し、効率的な枝刈
動的計画法が苦手な人が、動的計画法が超苦手な人へアドバイスしてみる - じじいのプログラミング
この記事は、Competitive Programming Advent Calendar Div2013（http://partake.in/events/3a3bb090-1390-4b2a-b38b-4273bea4cc83）の8日目の記事です。 動的計画法(Dynamic Programming, DP)についての記事です。 12/9 前編にサンプルプログラム（http://ideone.com/2B7f4v）を追加しました 12/11 前編の図２つを差し替えました。 はじめに まずは、本やネットの資料で、動的計画法についてのすばらしい解説はいろいろありますので、まずはそれらを参考に。 プログラミングコンテストでの動的計画法 http://www.slideshare.net/iwiwi/ss-3578511 最強最速アルゴリズマー養成講座：アルゴリズマーの登竜門、「動的計画法・メ
History of Lossless Data Compression Algorithms
Introduction There are two major categories of compression algorithms: lossy and lossless. Lossy compression algorithms involve the reduction of a file’s size usually by removing small details that require a large amount of data to store at full fidelity. In lossy compression, it is impossible to restore the original file due to the removal of essential data. Lossy compression is most commonly use
配列のランダマイズ、出来ますか？（後編）
前回のエントリ、配列のランダマイズ、出来ますか？（前編）の続きです。 前回のエントリの最後では、次のようなコードを提示し、どこが問題なのかの疑問を提起しました。 // 配列の初期化 var a = []; for(var i = 0; i < 1000; i++) { a[i] = i; } function swap(s, d) { var t = a[s]; a[s] = a[d]; a[d] = t; } // ランダマイズ、その2 for(var i = 0; i < a.length; i++) { swap(i, (Math.random() * a.length) | 0); } ランダマイズのコードの厄介なところは、1回2回実行したところで問題がわからない点で、このプログラムもぱっと見た感じではきちんとランダマイズされているように見えます。ではどうやって問題があるかを判断す
配列のランダマイズ、出来ますか？（前編）
先日、When Random Isn't Random Enough: Lessons from an Online Poker Exploit（英文注意）という記事がタイムラインに流れてきて、同僚と少し配列ランダマイズの話になったので備忘録として書いておきます。 配列のランダマイズというのは、たとえば上の記事にあるようなトランプのシャッフルであるとか、音楽プレイヤーの再生リストのランダム再生とかで実装しますね。ゲームを作るときなどには実装することが多いでしょうが、記事を読む前に、自分だったらどのように実装するか是非少し考えてみてください。 自分が中学生の頃に書いた記憶のあるコードは、たしか次のようなものでした。 // 配列の初期化 var a = []; for(var i = 0; i < 1000; i++) { a[i] = i; } function swap(s, d) { v
d.y.d. - シミュレーション問題について
20:43 13/12/31 本 今年読んで面白かった本ベスト20。 自分が今年読んだ基準なので遙か昔に出版された本も多数含みます。 しかもジャンル分けもせず適当に混ざっています。 ここ数年読書メーターでまとめてたんですけど今年ないみたいだし、 本棚機能もログインしていないと見られないようになってしまったみたいだし、 こちらで。 カクリヨの短い歌 和歌を詠むとその歌に応じた異能が発動するという能力バトルもの…というと情緒が飛んでしまいますかね。 読み終わったときはそうでもなかったのだけど、後からじわじわ来て、気づいたらこの話のことばかり考えるようになっていました。なんというか、歌を、この歌に込められた思いはこう…等々ロジカルな解題として語ってしまうのは勿体ないと思うんですよ。たとえば一面の桜吹雪、たとえば夜咲く紫陽花の花、その景色をただ再現するだけ、その具象が聴き手に何かを感じさせたならそ
Typical DP Contest - AtCoder
お知らせ モーダルが現れました。(9/01 1:00) 順位表が一部正しく表示されていません。原因を調査中です。(9/01 0:12) 9 月になりました。あけましておめでとうございます。コンテストは残り一時間です。現在とかれていない問題は Q のみです。(9/01 00:00) リジャッジを行いました。(8/31 23:24) P 問題のリジャッジを行います。(8/31 23:17) 半分経過しました。現在とかれていない問題は P, Q, R の三問です。(8/31 22:30) リジャッジを行いました。(8/31 21:04) H 問題に不正な入力がありました。申し訳ございません。リジャッジを行います。(8/31 21:00) 質問に回答しています。質問も定期的にご確認ください。(8/31 20:44) D 言語は使用できないようです。(8/31 20:32) ペナルティタイムは 5
簡潔データ構造 LOUDS の解説（全12回、練習問題付き）
「日本語入力を支える技術」（通称「徳永本」）や「高速文字列解析の世界」（通称「岡野原本」）で紹介されている LOUDS というデータ構造を、12回に分けて解説しました。 友達に教える時に使ったもので、練習問題付きです。 実際に紙に書いてやってみるとわかりやすいと思います。 詳解 LOUDS (1) LOUDS とは 詳解 LOUDS (2) ビット列を作ってみる 詳解 LOUDS (3) 0番ノード 詳解 LOUDS (4) ビットの意味 詳解 LOUDS (5) 木構造の復元 詳解 LOUDS (6) インデックスでノードを表す 詳解 LOUDS (7) ノード番号からインデックスを得る 詳解 LOUDS (8) インデックスからノード番号を得る 詳解 LOUDS (9) 子ノードから親ノード 詳解 LOUDS (10) 親ノードから子ノード 詳解 LOUDS (11) 木の検索 詳解
Efficient and Insightful Generalization
How OCaml type checker works -- or what polymorphism and garbage collection have in common There is more to Hindley-Milner type inference than the Algorithm W. In 1988, Didier Rémy was looking to speed up the type inference in Caml and discovered an elegant method of type generalization. Not only it is fast, avoiding scanning the type environment. It smoothly extends to catching of locally-declare
クイックソート殺し - d.y.d.
19:39 12/09/01 クイックソート殺し こういう系統の話。 Quicksort Killer (kazoo04さん) qsortを撃墜し(最悪ケースを与え)てみた。 (qnighyさん) A Killer Adversary for Quicksort (shinhさんの解説) Webアプリケーションに対する広範なDoS攻撃手法(hashdos)の影響と対策 (徳丸さんの解説) ただのクイックソートは要素数 N の配列をソートするのに最悪 N2 オーダの時間がかかってしまう、 そしてそれは pivot を偏って選びまくってしまった時に発生する、というのはよく知られた話だと思います。 といっても、広く使われている言語／ライブラリのソート関数はその辺り気をつけられていて、最悪時も O(N log N) になるアルゴリズムで実装されている…と思い込んでいたのですが（例えば C++ の
高速な安定ソートアルゴリズム "TimSort" の解説 - Preferred Networks Research & Development
先日、TimSortというソートアルゴリズムが話題になりました。TimSortは、高速な安定ソートで、Python(>=2.3)やJava SE 7、およびAndroidでの標準ソートアルゴリズムとして採用されているそうです。 C++のstd::sort()よりも高速であるというベンチマーク結果1が話題になり(後にベンチマークの誤りと判明)、私もそれで存在を知りました。実際のところ、ランダムなデータに対してはクイックソート(IntroSort)ほど速くないようですが、ソートというシンプルなタスクのアルゴリズムが今もなお改良され続けていて、なおかつ人々の関心を引くというのは興味深いものです。 しかしながら、オリジナルのTimSortのコードは若干複雑で、実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解
超覚えやすいグラフの探査アルゴリズム
グラフの経路探査で有名なダイクストラ法，A*探索を深さ優先探索(DFS)・幅優先探索(BFS)とのアナロジーで理解できることに気づきました。これを覚えておけば，スクラッチから何も参照せずにダイクストラ法，A*探索のコードを書けるようになります。 (以下の説明は，ある程度アルゴリズムを理解していることを前提としています。「超分かりやすい」でない点に注意ください) グラフ探査の抽象化コードグラフ探査を抽象化したコード(C++風擬似コード)は次のようになります。 Search() { Container que; // 抽象コンテナ ･･･(1) // スタート地点をキューに入れる Vertex s(スタート地点); que.push(s); while( !que.empty() ){ Vertex v = que.pop(); if( isGoal(v) ) // ゴールに到達したら終了 r
shinh ミーハー読書 - 昏論会ウィキ
CS とかよくわからんのでミーハー魂をくすぐるものを読んだふりをする * How to break MD5 and other hash functions (Xiaoyun Wang and Hongbo Yu) ** 前置き https://docs.google.com/viewer?url=http%3A%2F%2Fwww.infosec.sdu.edu.cn%2Fuploadfile%2Fpapers%2FHow%2520to%2520Break%2520MD5%2520and%2520Other%2520Hash%2520Functions.pdf MD5 のコリジョン生成方法が発見された時の話。 その発表を聞いた人のコメントがかっこいいんだ http://slashdot.jp/security/comments.pl?sid=203703&cid=607581 >彼女が研究
Benchmarking CRC32 and PopCnt instructions - strchr.com
Abstract: Exploring new instructions in Core i7/i5. Created 14 years ago by Peter Kankowski Last changed 14 years ago Contributors: Dmitry Kostjuchenko, Marat Dukhan, and Subbu N Filed under Low-level code optimization Recent Intel processors (Core i7/i5) can calculate CRC-32C and bit count in hardware. With other domain-specific instructions (string handling, AES encryption) in SSE 4.2, it may se
LOUDS(Level-Order Unary Degree Sequence)を調べたのでメモ - EchizenBlog-Zwei
最近よく目にするLOUDS(Level-Order Unary Degree Sequence)というのが気になっていたので調べた。実は最初に提案されたのは1989年。結構昔からあったと知ってびっくり。 Space-efficient Static Trees and Graphs G. Jacobson, 1989 LOUDSというのは木構造を表現するデータ構造をひとつ。単純に考えると木構造を実装するにはノードを表すオブジェクトに子ノードへのポインタを持たせる、というものが思いつく。この実装はノードへのアクセスは効率的にできるけれどメモリをたくさん使ってしまう(O(NlogN))。 そこでノードへのアクセス効率をあまり悪くせずに、省メモリな木構造が欲しい。これを実現したのがLOUDS。LOUDSはノードの追加や削除が起きないstaticな木構造にしか使えないが、必要なメモリはO(N)で済
Spaghetti Source - Union Find
説明 Union Find は互いに素な集合を扱うための道具である．Union Find を用いると以下の操作を高速に行うことができる． union_set(x,y): x が入っている集合と y が入っている集合を併合する． find_set(x,y): x と y が同じ集合に入っているかを判定する． make_set(x): x のみが入る集合 {x} を作る． アルゴリズムは次の考え方による．集合を多分木で管理し，木の根を集合の代表元とみなす．集合の併合は木の併合，二つの要素が同じ集合に入るかどうかは代表元が等しいかどうかの比較で行う． これらの走査を単純な木で行った場合，検索や併合に最悪 O(n) かかってしまう．そこで平衡操作を取る．具体的には木の要素を手繰ったとき，それらの親ポインタをすべて根に張り替える．このときの計算量を見積もるのは複雑だが，ならし解析によって O(A(n
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
