Intel AVX について勉強しているが、使っているCPUがどのSIMD拡張をサポートしているのかを知りたくなった。なので色々調べてインラインアセンブラを使ったコードを書いてみた。Sandy Bridge (Core i7 2600K)でAVXが使えることは確認できた。 // sup_ext.c #…
全点対最短経路問題(All-Pairs Shortest Paths Problem)において、Floyd-Warshall法などで最短経路の距離行列が求められている場合に、その最短距離行列から対応する経路行列を構築するアルゴリズムについてのメモ。アルゴリズムはO(n^3)のアルゴリズムで単…
Quick LaTeX ガジェットをサイト内に設置し、そのガジェットで数式を生成し、それをコピー＆ペーストすることで、Google Site で数式を使うことはできる。テスト結果
Sun Ultra 24 Workstation (プロセッサは Intel Core2Duo E8600 (3.3GHz)) で GSL (GNU Scientific Library) の CBLAS の SGEMM の性能を測った。結果は以下図(行列サイズは16の倍数)。僕が実装したスカラーとブロックの行列乗算アルゴリズムと比較した(ブロ…
https://www.spoj.pl/problems/ONP/を解くために書いたRubyのコードを、後々使えそうだからポストする。 $priority = [[['+',0],['-',1],['*',2],['/',3],['^',4]]] def recur(s, idx) op_stack = Array.new p = idx while p < s.length c = s[p].chr case c…
Round 1 落ちです。悔しいな。去年よりは実力がついたとは思うが、それでもまだまだ対応できる問題の種類が少なく、レベルが低い。
Code Jam - Google’s Coding Competitions 参戦記録として書いておく。 結果は約1時間半で全問解けて、65位。それぞれ30分ぐらいずつかかった。出だし好調と言える結果だが、全問解いた方は約2400人もいる。Round 1の合計通過人数が3000人なので、Round 1を…
アフィン暗号の復号化についての情報が、検索してもすぐには見つけられなかったのでメモ。アフィン暗号は文字 r を２つのキー a,b を用い、E(r)=(a*r+b)%N 式により暗号化、D(r)=((r-b+N*k)/a)%N 式により復号化する方法(Nは文字種数、k は(r-b+N*k)0 (mod a…
217.81/250383.99/5000/1000Challenges: 1/1Total: 651.80Room rank: 1 Division rank: 7Rating: 871 -> 1064Division rank 7位は過去最高。250,500の両問題とも解法はすぐに思いついたが、コーディングの仕方が少し非効率だった。緑に戻れた。
今週は雑用が多い。中間試験答案の採点とその統計データ作り。そして、来週の旅行(出張?)のための申請と、なかなかまとまった時間が取れない。研究計画書を今日までに書く予定だったのに、ほとんど手をつけられてない。
３日ほど前から、ボールジャグリングを１日30分弱行っている。基本といえるカスケードは完璧にできるようになったが、その後、なかなか上達しないままだった。今度は、このページを参考にしながら、地道に簡単な技からできるようにしようということで、ハー…
昨日の午後あたりから鼻水が水っぽい。風邪をひいたらしい。前回にいつひいたのかは覚えていないが、だいぶ前で、半年ぐらい前だと思う。 大学に入学した当初は３カ月に１回ぐらいはひいていたが、生活のバランスを良くしたら、ひきにくくなった。 今回、風…
先週はシンポジウムに参加するために広島に行って来た。数々の研究発表等を聴いて、思うことがあるが、まだ考えが整理できていない。考えを整理する前に、乱雑な机の上を整理した。２月末までに出す必要があった論文を書くために、資料を置いていったらいつ…
約4ヶ月ぶりの更新。なんだろうね、自分が大した人間ではないと認識するには充分な体験をしたと思う。最近はネガティブに考えてしまうときと、ポジティブに考えられるときが交互にやってきて、気持ちの浮き沈みが激しく、安定していない。今後については、5…
まとめのエントリを書くのを忘れていた。面倒なので、適当に少しだけ書く。冬休みはあっという間に過ぎた。 研究関係では論文の査読結果が月末に送られてきた。結果があまり魅力的ではないので、もっと付け足した方が良いといった内容。ごもっともです プロ…
今日は朝から授業のレポートを書いている。昨日から気合を入れて書き初めて、完成度が半分ぐらいのところまで来た。分からない部分は適宜調べながら書いているが、なかなか資料が分かりにくい。それでも諦めずに何回も読んでいると、たまに腑に落ちる部分が…
Cell Challenge 2009 の規定課題部門の課題が公表された。編集距離(Edit Distance)か。編集距離の問題はUVaでも解いたことがあるけど、なかなかアルゴリズムが理解できなかった記憶がある。Cellで高速化しやすいアルゴリズムがあるのかどうかは知らないけど…
10月のまとめを先日書いたばかりのような気がする。もう一ヶ月過ぎたのか。11月は学外に行くことが多く、その疲れがなかなかとれず、ひどく調子が悪かった。研究関係何をやっていたのかと問われれば、何をやっていただろう。確かに論文はいくつか読んだし、…
10月も終わったので書いておこう。研究関係今期授業は一課目しかとってないので、いろいろできそうと思ってやってみたが、広く浅くやりすぎた。全体的にみるとあまり進んでいない。先月の終わりごろから取り組んだドキュメントの英訳は訳し終わり、その後に2…
他のところでいろいろ書いているから、ここには書くことがない。とりあえず、C++で書いたバブルソートのアルゴリズムをポスト。 template <class T> void BubbleSort(vector<T>& a, const int n) { for (int i = 0; i < n; i++) for (int j = n-1; j >= i+1; j--) if (a[</t></class>…
今回のDIV2の250と500はやるだけの問題だった。1000は多倍長整数を使う方法では計算が時間内に終わりそうもないので、どうすればいいか考えたが、よい方法が思いつかなかった。Challenge Phaseでは、500の問題で閏年の判定が間違っている方と、月名にスペル…
８月はインターンシップ、９月はなんやかんやで過ぎ去り、夏休みもあと一週間ほどで終わります。それで、９月の行動を振り返ってみたいと思う。研究関係一番大きいことは、卒論を改善した論文を論文誌に投稿したこと。スピードチャレンジに参加したことでな…
PS3(Fedora 7)にMPICH1.2をインストールした。(今のところは4台に入れた)メモしておく。0. MPIを使ってやり取りをしたい全てのホストに対して、以下の設定をする。1. rshで使うポートを開放する。セキュリティを気にしないなら# /usr/sbin/ntsysvを実行し、i…
UVa Online Judgeの問題を解く前の準備作業をある程度自動化した方が、ストレスが減ると思ったので作った。使用法:1. 以下のファイルをダウンロード (2009-06-14に追記: Openomyがサービス終了していたのでSkyDriveにに再アップロードした)。http://cid-8f0a…
5週間に及ぶインターンシップも明日で終わり。今日はインターンの成果発表を行った.発表スライドができあがったのが、発表の1時間前だったのでほとんど練習出来なかった。そのため途中何を言っていいのかわからなくなったところがあった。来週は大学に戻りま…
事情があって金曜日は休んで、実家に帰った。 で、今朝5:00に家を出て、アパートに戻って来た。 9:30に着いたので、所要時間4時間半。
UVa Online Judgeの!! Really Strange !!を解いた。独力で方程式を導出できた。うれしいので解説を書く。まず、問題文からはf(n) = 2(n-1) + f(n-1)というnに関する漸化式が作れる。ここに、f(1) = 2 問題のサイズnが小さければ、この漸化式を元にした再帰関…
インターン11日目終わり。先週までは移植、高速化対象のプログラムのプロファイリング、ボトルネック探り、関数情報のまとめ、そして最適化しやすい形にプログラムを組み換えた。 今日からコーディングファイズに入った。たぶん1日7時間ぐらいコードを書くこ…
前回は書かなかったな。今回は一問も解けなかった。Ratingの推移だけ書いておく。867->927->833GreenとGrayを行ったり来たり。最初の頃の勢いがなくなって本来の実力が表面化してきたということか。地道に実力をつけ、年内にはDIV1に昇格したいな。
Round 1AはA,Bのsmallしか通せず、15点で1281位。Round 1Bは一問も通せず、順位付かず。で、Round 1で敗退です。実力相応の結果です。
