巨大整数の除算 Barrett 法 - Tociyuki::Diary
GNU MP では整数の桁数が大きいとき、再帰除算ではなく、除数の逆数を求めて乗算する方式へ切り替えます。GNU MP のニュートン−ラフソン法による逆数算出ロジックは Knuth 先生によるアルゴリズムの応用で、除算ロジックは Barrett 法に基づいているものの、乗算の桁数を減らす工夫をしてあります。ここでは、そうした工夫をせずにシンプルなやりかたに留め、Ruby で試してみます。 2014年10月15日修正: 被除数の桁数が除数の桁数の 2 倍を越える場合に桁ずらし除算をおこなうようにしました。 Knuth 先生の逆数を求めるアルゴリズムがおもしろいのは、整数である除数 b を 1 より小さな固定小数点数とみなして、 1 より大きな逆数を求めるところにあります。整数から逆数を求めようとすると、 1 より小さな小数点数を求めようと考えてしまうものですが、逆転の発想になっています。小数
配列のランダマイズ、出来ますか？（前編）
先日、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
Algorithm - Ruby 2.0 や Haskell の遅延リストを JavaScript で : 404 Blog Not Found
2013年03月10日23:45 カテゴリアルゴリズム百選Math Algorithm - Ruby 2.0 や Haskell の遅延リストを JavaScript で プロになるためのJavaScript入門 河村嘉之 / 川尻剛 これを書いたら欲が出て来たので。 dankogai/js-list-lazy ・ GitHub ちなみに「プロになるためのJavaScript入門」は参考書にした一冊。この場を借りて献本御礼。 無限リスト 自然数を受け取って対応する値を返す関数を一つ食わせるだけです。 var ll = List.Lazy(function(i){return i}); // also predefined as List.Integers p( ll.length ) // Inifity p( ll.get(42) ) // 42 p( ll.take(42) ) //
Algorithm - 配列の冪集合、順列、組み合わせを再帰なしで作る : 404 Blog Not Found
2013年03月08日11:00 カテゴリアルゴリズム百選Math Algorithm - 配列の冪集合、順列、組み合わせを再帰なしで作る C言語による最新アルゴリズム事典 奥村晴彦 ちょっと必要に迫られたので、JavaScript用のやつを作りました。 dankogai/js-combinatorics ・ GitHub こんな感じで使います。 var a = ['js', 'pl', 'py', 'rb'], c, e; p( '/* power set */' ); c = Combinatorics.power(a); p( 0 + c ); while (e = c.next()) p(JSON.stringify(e)); p( '/* combination */' ); c = Combinatorics.combination(a, 3); p( 0 + c ); p(J
javascript - で bilateral filter (選択的ガウスぼかし)を実装してみた : 404 Blog Not Found
2012年09月06日18:03 カテゴリアルゴリズム百選Math javascript - で bilateral filter (選択的ガウスぼかし)を実装してみた HTML5 Canvas Steve Fulton / Steve Fulton / 安藤 慶一訳 [原著:HTML5 Canvas] 「選択的ガウスぼかし」がえらい気に入ったので、アルゴリズムの学習も兼ねてJavaScriptでやってみたら思いの他使い物になりそうということで。 Demo: File APIを実装しているブラウザーで動きます。IEの方ごめんなさい。IEだと10以降になります。小さめのファイルを読み込ませて下さい。1024*1024ピクセルを一応の上限に設定してあります。(追記2021.11.29:上限を16Mピクセルまで上げました。その他CSS周り修正) Info: Source: Radius: Thr
algorithm - Patricia Trie (Radix Trie) を JavaScript で : 404 Blog Not Found
2012年01月21日21:45 カテゴリTipsLightweight Languages algorithm - Patricia Trie (Radix Trie) を JavaScript で スマホ手袋 5本指全てタッチできる smarttouch 5105 ミドリ安全 寒いのでこれをしたまま書きました。 dankogai/js-trie-patricia - GitHub 404 Blog Not Found:Algorithm - 連想配列の実装としてのハッシュはオワコン? Trieが連想配列の代わりになるというのを体でも納得しておきたかったので。 はじめてのTrie というわけで早速作ってみましょう。あっけにとられるほど簡単です。ここではObject、つまり連想配列で分岐点を実現するというある意味本末転倒なことをしていますが、JSならばしかたがない。 var Trie =
algorithm - mapBetween - 配列の隣接する2項にそれぞれ演算を施した配列 : 404 Blog Not Found
2012年01月04日21:00 カテゴリLightweight Languages algorithm - mapBetween - 配列の隣接する2項にそれぞれ演算を施した配列 言語を増やしたかったのと、そういう関数に名前を付けたかったのとで1 entry割くことにしました。 等差数列 - タイトル 配列の隣接する2項にそれぞれ演算を施した配列を得たい。つまり、 f (+) [1,2,3,4,5] = [3,5,7,9] のような f が欲しい。 名前 もちろん等差数列を作るのにもこの関数は使えるのですが、この一般的に使える関数に使う名前としてはあまりに局所的。というわけで mapBetween としてみました。使いどころはかなり多そうです。各言語に標準装備されていないのがちょっと不思議なほど。 JavaScriptによる実装 Array.prototype.mapで滅多に使われない第
algorithm - ソート済み配列をソートしなおすべからず : 404 Blog Not Found
2012年01月08日20:30 カテゴリアルゴリズム百選Math algorithm - ソート済み配列をソートしなおすべからず 珠玉のプログラミング Jon Bentley / 小林健一郎訳 ぐぬぅ。男子ゆえ女子をこじらせようがないとはいえ、風邪が普通にこじれている。 というわけでアルゴリズムのことなどつらつら考えていた。 高速な安定ソートアルゴリズム “TimSort” の解説 : Preferred Research Timsort - Wikipedia, the free encyclopedia 要はソートすべき配列中にすでに存在する秩序を活用するのがtimsortなのだと。 だけどすでにソート済みの配列を活用するなら、こういう方法もありではというわけでentry。 If it ain't broke, don't fix it. ソート済みの配列に要素を加えるなら、要素を加
algorithm - bucket sort - 比較しなければソートは相当速い : 404 Blog Not Found
2012年01月11日07:00 カテゴリアルゴリズム百選Math algorithm - bucket sort - 比較しなければソートは相当速い 珠玉のプログラミング Jon Bentley / 小林健一郎訳 絶賛風邪こじらせ中につきコードと戯れることに。 新ソートアルゴリズム「配列挿入ソート」だ! - hp12c その名も「配列挿入ソート」! すでに突っ込み入ってるけど、それ、もしかしたら人類最古のアルゴリズムだから。 最古にして最速? おそらくプログラムを組んだことがない人でも「誰にも教えられずに」知った「天然の」アルゴリズムの筆頭に来るのがこのバケットソートではないでしょうか。 ソートしたいものに適当に番号を振っておく 番号がついたバケツを用意する ソートしたいものの番号がついたバケツにそれを放り込む 必要があればバケツの中身を同じやり方でソートする 番号順にバケツの中身をぶち
Algorithm - Suffix Array を JavaScript で再発明してみた : 404 Blog Not Found
2012年01月16日16:30 カテゴリアルゴリズム百選Lightweight Languages Algorithm - Suffix Array を JavaScript で再発明してみた WEB+DB 総集編 [Vol. 1〜60] もう10年以上前に某社のCTOだったころ、Suffix array(接尾辞配列)の解説を毎週の技術者ミーティングでしたら一名を除いて「ハァ?」状態だったことを思い出しつつ。 Suffix Arrayは何が画期的だったのか? 以下は、計算機科学者でなくても直感的に理解できると思います。 ソートされていない通常のデータの中にあるサブデータ(キー)を検索しようとすると、データの大きさに比例した時間(O(n))がかかる。 ソート済みのデータであれば、二分探索でデータの大きさの対数時間(O(logn))でキーを検索できる。 さらにキーからIDを定数時間で作成でき
重みをつけて乱択する (バイナリサーチ版) - m2
せっかく書いたのでバイナリサーチ版のっけときます。 http://jsfiddle.net/t58Vv/6/ // algorithm - 重みをつけて乱択する http://blog.livedoor.jp/dankogai/archives/51761113.html // バイナリサーチ版 var make_random_picker = function(picks){ var i, l = picks.length, t = 0, choices = picks.concat(); for (i = 0; i < l; ++i) { choices[i][1] = (t += choices[i][1]); } for (i = 0; i < l; ++i) { choices[i][1] /= t; } return function() { var r = Math.rand
algorithm - 重みをつけて乱択する : 404 Blog Not Found
2011年12月27日17:15 カテゴリ algorithm - 重みをつけて乱択する 数学ガール/乱択アルゴリズム 結城浩 同意なのだけど… Perlで生でrand関数をごちゃごちゃ使うコードはもう嫌だ | hirobanex.net とにかく、プログラムッチクというとなにかとランダムという要件が多いし、こんなコードばかりグチャグチャ書くのはもういやですね。 これを一般化するという問題はアルゴリズムの実習にちょうど手頃なサイズなので。 JavaScriptによる実装 頻度を高い順に並べて、乱数＜合計頻度となったところでそれを選択します。O(n)ですが選択肢を頻度順に並べることでその分ループが回る確率を抑えています。 (function(global){ var make_random_picker = function(picks){ var choices = Array.proto
Diff algorithm - 枕を欹てて聴く
id:smoking186 さんの指摘を受け, First Authorの名前などを付加しました. どうもです. 記事内のcodeは最適化などを施しておらず, 冗長に, 定義どおりに書いています. ifがまとめられたりとかしますが, そのあたりはご容赦を... Rubyでlevenshtein距離を見て以来, 個人的にdiffブームが来ていた. 計算量O(ND) / O(NP)のalgorithmなどがあるのは知っていたが, 論文(英語)および, 解説のみ, またはソースコードのみなど分かれているものが多く, algorithmに疎い自分には理解するのに大変時間がかかってしまった. しかしやっとわかったので, 解説+JS実装してみる. 解説とソースコードがセットだと, 多少はわかりやすくなるかと... 自分は正直これくらい細かく言われないとすぐにはわかんない人なので(the O(ND)だけ
javascript - Mathを再発明してみた : 404 Blog Not Found
2010年09月14日06:30 カテゴリMathLightweight Languages javascript - Mathを再発明してみた 「基本というからには四則演算で三角関数実装しないとねー」と思いつつ書いていたら… C言語による最新アルゴリズム事典 奥村晴彦 [javascript]三角関数の基本 Math.random()を除いてMathを全部再発明しおえたので。 多倍長演算バージョンを作る時の下ごしらえにもなるかも。 下ごしらえ 仕様は Math - MDC アンチョコはもはや最新というにはあまりに古い、しかし代わりなき「C言語による最新アルゴリズム事典」。低レベルな車輪を再発明する人必携! 初期化と定数 定数の精度はおおげさに。 MyMath = {}; MyMath.E = 2.718281828459045235360287471352662497757; MyMat
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
幅優先探索 - 素人がプログラミングを勉強していたブログ
昔流行ったやつ。幅優先探索で迷路の経路を出す時は、ノードをリストにして逆算していくか、マップを0で初期化して、通るたびに0, 1, 2…というように徐々に増やしていって、ゴールについたら一つずつ減っていくような道を探す、という方法が使える。 それぞれ辺のコストが異なる場合はキューをPriority Queueにしてコストの合計が最小であるところから探索すれば良い。で、これを発展させるとダイクストラ法になって、更に、探索順序を改良すると、AStarになる。このへんは、一度書いてみると理解が深まるのでオススメ。 <!DOCTYPE html> <html> <head> <meta charset="UTF-8"> <title>迷路探索</title> <style> textarea { font-family: monospace; } </style> </head> <body> <
JavaScript, Canvas スキャンライン・シードフィル アルゴリズムによる塗り潰し : Serendip – Webデザイン・プログラミング
HTML5 Canvas でバケツツールによる塗り潰しを実現するために、スキャンライン・シードフィル (Scan Line Seed Fill) というアルゴリズムを使ってみた。 アルゴリズムの詳細については、以下のサイトを参考にした。 参考：ActionScript入門Wiki@rsakane – 塗りつぶしアルゴリズム(スキャンライン – シードフィル編) ペイント・ルーチン (1)シード・フィル アルゴリズム 単純に言えば、水平方向に塗り潰し可能な範囲を探して塗り潰してゆき、それを塗り潰し可能な範囲が無くなるまで上下方向に繰り返していくといったもの。 JavaScript, Canvas スキャンライン・シードフィル アルゴリズムによる塗り潰しデモ 塗り潰し処理のコード var fillColor = function(startX, startY, imgData, penColo
JavaScriptで自動迷路生成｜S-Bot
現在JavaScriptを勉強中ですが、なぜか急に迷路生成のスクリプトを作りたくなったので書いてみました。 調べてみると迷路生成にはいくつかのアルゴリズムがあるらしく、その中でもっともシンプルな「棒倒し法」というナイスなものがあったので、それを採用することにしました。 参考：迷路自動生成アルゴリズム このアルゴリズムではまず下のようなグリッドを作ることから始まります。 この状態から中の黒い部分を棒倒しのように左右上下にランダムに倒していきます。 既に棒が倒れている場所には置けません、また2行目移行は上には倒せないというルールがあります。 すべて倒して、スタートとゴールを設定するとこうなります。 というわけで、そこそこシンプルに迷路を自動生成できました。 なぜこのアルゴリズムで迷路ができるのかは、僕に聞かないでください。 気が向いたら赤い点を操作できるようにしたり、高速化したり、HTM
ソートアルゴリズム - rikubaのブログ
バブルソート 挿入ソート シェルソート 選択ソート マージソート バブルソート function bubbleSort(data) { var l = 0, r = data.length - 1, i, temp, last; while(l < r) { i = r; last = l; while(i > l) { if(data[i-1] > data[i]) { temp = data[i-1]; data[i-1] = data[i]; data[i] = temp; last = i; } --i; } if(last == l) return; l = last; } } 挿入ソート function insertionSort(data) { var n = data.length, i, temp, j; for(i = 1; i < n; ++i) { temp =
QuickDrawはどのように素早く円を描いていたのか？ - ザリガニが見ていた...。
かつてのMac OS9までの描画エンジンの主役はQuickDrawが担っていた。GUIなOSでは、文字も含めてすべてをグラフィックとして扱うので、画面に見えているすべてのもの*1はQuickDrawによって描かれていたことになる。描画エンジンは、GUIなOS開発の要となる技術である。その出来が、GUIなOS開発の成否を分けるとも言える。 そして、最初期のQuickDrawは、ビル・アトキンソンがたった一人で開発したそうである。 当時（25年以上前）のCPUは、動作クロックが8MHzという性能だった。（現在は2GHz=2000MHzかつ、複数コアが当たり前） そのような性能であっても、違和感なくマウスで操作できるOS環境にするために、斬新な発想や試行錯誤を重ね、相当な努力の末に開発されたのがLisaやMacintoshであった。 Amazon.co.jp： レボリューション・イン・ザ・バレー
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
