Intel AVX について勉強しているが、使っているCPUがどのSIMD拡張をサポートしているのかを知りたくなった。なので色々調べてインラインアセンブラを使ったコードを書いてみた。Sandy Bridge (Core i7 2600K)でAVXが使えることは確認できた。 // sup_ext.c #…

全点対最短経路問題(All-Pairs Shortest Paths Problem)において、Floyd-Warshall法などで最短経路の距離行列が求められている場合に、その最短距離行列から対応する経路行列を構築するアルゴリズムについてのメモ。アルゴリズムはO(n^3)のアルゴリズムで単…