Bisection method - Wikipedia
This article is about searching zeros of continuous functions. For searching a finite sorted array, see binary search algorithm. For the method of determining what software change caused a change in behavior, see Bisection (software engineering). A few steps of the bisection method applied over the starting range [a1;b1]. The bigger red dot is the root of the function. In mathematics, the bisectio
Pythonを使って高速素数判定をしてみる - Pashango’s Blog
みなさん、素数を数えてますか？ 『素数』は１と自分の数でしか割ることのできない孤独な数字。 暗号化できたり、乱数を作れたり、心を落ち着いたりして、私達に勇気を与えてくれます。 素数といえば「エラトステネスのふるい」ですが、あれは大きい桁の素数を生成しようとすると、とんでもなく時間が掛ります。 今回は、どんな大きな桁の素数でも高速で素数判定するプログラムを作ってみます。 基本は「フェルマーの小定理」 素数判定の基本は「フェルマーの小定理」です、数式は１行だけのごく簡単なものです。 a^(p-1) mod p の答えが1以外ならpは合成数である ただし、aとpが素の関係（最大公約数が1)であること 2つの数を「べき剰余算」して答えが1以外なら合成数(not 素数)という事です。 aに2を代入してqが素数なら答えが1になる、たったこれだけです簡単でしょ？ def is_prime(q): q =
微分方程式の数値計算（オイラー法）-数学アルゴリズム演習ノート-
数値計算による物理シミュレーションで出てくる微分方程式は、積分など解析的な方法では解くのが困難、もしくは解けない事があります。しかし、微分方程式とは言ってみれば変数の「変化」のしかたを表した方程式ですので、単純にその方程式にしたがって変数を変化させてその結果を積み重ねていけば（数値積分）、大体の様子はわかるはずですね。さらにそのように数値計算で解くのは、「計算機」たるコンピュータの最も得意とする分野とも言えるでしょう。 例えば、dy/dx=2x、x=1でy=1という微分方程式があったとします。これは積分すれば解析的にも簡単に解けます（y=x2)が、初期値を入れた後、y をdy/dx=2x に従って変化させていっても大体の値は求まるわけです。まず、x=1でのyは1で傾きはその時点でのx*2の値,すなわち2です。これを使ってx=1.1でのyを求めてみましょう。 すでに傾きがわかっているので、x
修正オイラー法
vは速度です。常微分方程式が2つ出てきましたが難しいことはありません。それぞれに修正オイラー法を適用して解いていきます。 #include <stdio.h> double f1(double x,double v); double f2(double x,double v); int main() { double t,dt,x,v,tmax; double k0[2],k1[2]; dt=0.01; //刻み幅設定 x=1.0; //位置初期値 v=0.0; //速度初期値 tmax=100; //繰り返し最大回数 FILE *output; output=fopen("output.data","w"); fprintf(output,"%f %f\n",x,v); for(t=0;t<tmax;t+=dt) { k0[0]=f1(x,v); k0[1]=f2(x,v); k1[0]
オイラー法
vは速度です。常微分方程式が2つ出てきましたが難しいことはありません。それぞれにオイラー法を適用して解いていきます。 #include <stdio.h> double f1(double t,double x,double v); double f2(double t,double x,double v); int main() { double x,v,t,dt,tmax; double k0[2]; FILE *output; output=fopen("output.data","w"); /*初期値*/ x=1.0; v=0.0; dt=0.01; tmax=100; for(t=0.0;t<=tmax;t+=dt) { k0[0]=dt*f1(t,x,v); k0[1]=dt*f2(t,x,v); x=x+k0[0]; v=v+k0[1]; fprintf(output,"%f
ルンゲクッタ法
vは速度です。常微分方程式が2つ出てきましたが難しいことはありません。それぞれにルンゲクッタ法を適用して解いていきます。 #include <stdio.h> double f1(double t,double x,double v); double f2(double t,double x,double v); int main() { double t,x,v,dt,tmax; double k1[2],k2[2],k3[2],k4[2]; x=1.0; //位置の初期値 v=0.0; //速度の初期値 dt=0.01; //刻み幅 tmax=500.0; //繰り返し最大回数 FILE *output; output=fopen("output.data","w"); for(t=0;t<tmax;t+=dt) { k1[0]=dt*f1(t,x,v); k1[1]=dt*f2(t,
COS類似度 - 小宮日記
文章の類似度を計算する場合などにCOS類似度というのが 使われるらしい。 二次元で考えた場合、ベクトルAとベクトルBの類似度は、 COS類似度＝AとBの内積/(norm(A)*norm(B))normは my $norm_1 = 0.0; map { $norm_1 += $_ ** 2 } values %{$vector_1}; $norm_1 = sqrt($norm_1);のように、ベクトルの要素をそれぞれ二乗して積算して、SQRTをとったもの。 二次元の場合は、norm([x,y])=sqrt(x^2+y^2)=距離ですね （このへんはボナメソのペナルティでもおなじみ。L1norm、L2norm） 内積をノルムで割ってるのは、正規化がかかるためのようです。 ベクトルによって長かったり、短かったりするでしょうから。 ベクトルとベクトルの間の角度が、類似度を表現するわけです。 内積は
bayonやCLUTOが爆速な理由 - download_takeshi’s diary
クラスタリングツールbayonを使っていて、常々「どうしてこんなに高速に処理できんのかなぁ」と疑問に感じていました。repeated bisectionという手法自体がk-means法などと比べると効率がいいのですが、それにしても、それだけでは説明がつかないほど爆速なわけです。 うまく例えられませんが、自前でk-meansのスクリプトを書いて比べてみると、自転車と新幹線くらいちがうという印象です。はじめてCLUTOを触った時、数万件程規模のクラスタリング処理が本当に「あっ」という間に終わってしまい、びっくりした記憶があります。 きっと実装面でなにか特殊なことがあるんだろうなと思い、mixiエンジニアブログでbayonの記事を改めて読み漁っていたら、以下の部分が目に止まりました。 このクラスタの評価は、クラスタの各要素とクラスタの中心とのcosine類似度の和としています。この和が大きいほど
人材獲得作戦の問題を反復深化深さ優先探索で - 簡潔なQ
人生を書き換える者すらいた。: 人材獲得作戦・４ 試験問題ほか 反復深化深さ優先探索は、深さ優先探索の深さのリミットを少しずつ増やしながら行う探索で、幅優先探索に近い性質をもつ探索。 ゲーム木のように浅くて広い探索木の場合にメモリ効率が良く好まれる。 再帰で書けるので幅優先よりシンプル。 #include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; string maze; vector<int> depths; size_t w; bool search(int x, int depth) { if(depth<=depths[x])return false; depths[x]=depth; if(maze[x]=='*')return false; i
人材獲得作戦の問題をWarshall-Floydで - 簡潔なQ
人生を書き換える者すらいた。: 人材獲得作戦・４ 試験問題ほかを今度はWarshall-Floydで解いてみた。 Dijkstraが特定の2点間の最短経路を求めるのに対して、Warshall-Floydは全ての2点間の最短経路を一括で求める。 またWarshall-Floydの良い点として、負辺の処理および負閉路の検出も可能ということが挙げられる。 負辺に対応した単一始点最短経路探索のBellman-Fordというのもあるようだけれど、Warshall-FloydのオーダーがO(|V|^3)なのに対してBellman-FordはO(|V||E|)らしいので、ある程度疎でない限りWarshall-Floydでいいんじゃないかな。 効率は悪いが、まあWarshall-Floydの練習ってことでどんまい。綺麗だし。 #include <iostream> #include <string> #i
もっと高速に－線分交差判定－
線分交差判定といっても、すべての与えられた線分に対して、同様な計算を 行って判定していたのでは、無駄が多いように見えます。場合によっては もっと単純な軽い判定で行えるはずです。そこで、 『場合分けによるラフチェック』を もっと簡単に－線分交差判定－のプロシージャ に追加して、次のように変更します。 '構造体 Private Type POINT x As Double y As Double End Type '座標 p1,p2 を結ぶ線分と座標 p3,p4 を結ぶ線分が交差しているかを調べる 'ただし、線分が重なっている場合(3点,4点が一直線上にある)、「交差している」、と判定します。 Private Function intersectionEX(p1 As POINT, p2 As POINT, _ p3 As POINT, p4 As POINT) As Boolean 'x座標
もっと簡単に－線分交差判定－
ここでは、線分交差判定の定石ともいえる方法を紹介しています。 線分と直線の見落としがちな大切な定義です。
Bayesian Setsによる関連文書検索システムStupa - mixi engineer blog
都会よりも田舎が好きなfujisawaです。Bayesian Setsというアルゴリズムを使って、関連する文書を高速・高精度に検索できるシステムを作成しましたので、そのご紹介をさせていただきます。 Bayesian Setsとは Bayesian Setsはいくつかアイテムを入力すると、それを補完するようなアイテムを返してくれるアルゴリズムです。原著論文の先頭に"Inspired by Google Sets"と書かれているように、Google Setsを参考にして作成されています。実際にどのような出力が得られるか、Google Setsに以下の表のクエリを検索して試してみますと、 クエリ 出力 apple, banana chocolate, strawberry, vanilla, cherry, ... apple, macintosh software, windows, mac,
トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター
トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター：最強最速アルゴリズマー養成講座（1/4 ページ） プログラミングにおける重要な概念である「探索」を最速でマスターするために、今回は少し応用となる探索手法などを紹介しながら、その実践力を育成します。問題をグラフとして表現し、効率よく探索する方法をぜひ日常に生かしてみましょう。 まだまだ活用可能な探索 前回の「知れば天国、知らねば地獄――『探索』虎の巻」で、「探索」という概念の基礎について紹介しました。すでに探索についてよく理解している方には物足りなかったかと思いますが、「問題をグラフとしてうまく表現し、そのグラフを効率よく探索する」というアルゴリズマー的な思考法がまだ身についていなかった方には、得るものもあったのではないでしょうか。 前回は、「幅優先探索」と「深さ優先探索」という、比較的単純なものを紹介しましたが
チームラボ / teamLab
森ビル デジタルアート ミュージアム：エプソン チームラボボーダレス 2024.2.09(金) - 麻布台ヒルズ、東京
第7回 転置索引の構築 | gihyo.jp
はじめに これまで、転置索引の構造や具体的なデータ構造を見てきました。今回は、検索したいテキスト文書から、どのようにこの構造を構築するかを説明していきます。 ディスクベースの構築方法 第3回では、表を作成しそれを転置させることで転置索引を構築しました。実際にコンピュータに処理をさせる場合も、メモリ上の2次元配列で同様に構築することが可能となります。しかし、通常の転置索引は非常に疎な表となるため、この方法ではメモリを使いすぎてしまいます。また、リンクリストなどのメモリ上でのデータ構造を用いることにより、上記の方法と比較して少ないメモリ量で構築することもできます。 これらの方法はいずれも、対象とする文書集合を変換した転置索引が実メモリに収まる場合にのみ可能となる方法となります。しかし多くの場合、転置索引は実メモリよりも大きくなります。そのような場合はディスクを用いた構築方法が必要となり、効率的
【SEOリサーチ】本文のテキストが鍵を握る！ Yahoo!検索アルゴリズム2009年12月更新分の調査レポート
『MarkeZine』が主催するマーケティング・イベント『MarkeZine Day』の 最新情報をはじめ、様々なイベント情報をまとめてご紹介します。 MarkeZine Day
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
NWB Community Wiki : Fruchterman-Rheingold browse
グラフ描画入門 - Wolfram Mathematica
ネットワーク構造の可視化