スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す（C ） | 配電盤

魔方陣の解の列挙は並列化しやすそうな問題ですが、ここでの方針では、探索効率を上げるためには条件分岐が不可欠なので、（「数」を求めるだけだとしても）GPGPUでうまくやる方法がわかりません。そこで、CPUに載っているコアのみで並列化します（Xeon Phiなら簡単なのでしょうか→追記参照）。 一番外側の、0から(1<<25)-1まで変化する変数iのループをOpenMPで並列化します（schedule(guided)では遅くなります。schedule(auto)はVisual C++でサポートされたら試します）。変数iは上の図の緑の部分（カンで5個にしました）を各数5ビットで表現し、つなげたものです。マスに入りうる数は1から25までなので、5ビットというのはちょっと冗長ですが、とりあえずはよしとしましょう。 出力はバイナリ形式で、1つの解に25バイト使います（1つのマスに入る数を1バイトで表現

[hapilaki]

まさにこれ→モビルスーツの性能の違いが戦力の決定的差ではないと言うことを教えてやる

[mustelidae]

そういえば組み合わせ爆発のおねえさん元気かな

[snobocracy]

こうやって大人気ない大人が壁となって立ちはだかるのはとても良いこと。

[plutonium]

「多分これが一番早いと思います」

[fukken]

こういう、有能な子どもの更に上を行く大人げない大人は大事。あと「力技で何でもやりゃいいってもんじゃない」も（まあ力技の方が速い問題も多いのだが）

[justsize]

こういう大人気ない大人の存在こそ、世界を盛り上げる。

[nazoking]

この最適解プログラミングを二時間以内でできるプログラマの能力を当てにせず全探索させる仕様書を書くのが職業SE…ううっ

[amematarou]

スパコン京も大した実績がないのは使いこなすプログラムを日本人が作れないからっていうのは聞いたことある

[youichirou]

アルゴリズムの問題とすれば、こいつをT2K-Tsukubaで走らせたらどうなるのか気になる。

[kamei_rio]

大人気ないがアルゴリズムに年齢などないので正しい

[ustar]

なるほど大人気ない

[c_shiika]

人間ベンチマーク

[yuyakko]

アルゴリズムの大切さ

[tamtam3]

高校生もスパコン実行前にGitHubにコードをあげれば、みなからForkされて劇速になったに違いない

[t_f_m]

アルゴリズマーの案件だ

[akatuki_sato]

今日のイオリア・シュヘンベルグはここですか

[death6coin]

いともたやすく行われる大人げない行為

[arvante]

UNICORNが聞こえる（幻聴）。

[wata88]

全探索って男の子って感じだよなー

[arajin]

「Core i7 4930K（12スレッド）で、出力先をRAMディスクにした結果は593秒（約10分）でした。」並列化していないと「解の数え上げで約5000秒（確認済み）、解の列挙で約3日（未確認）」ぐらいらしい。

[Drunkar]

アルゴリズムが一番重要ってはなし

[gyu-tang]

早いっ

[akio0911]

【Share】スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す（C++）

[ene0kcal]

筑波の高１vs東大物理卒の准教授の図。

[vivit_jc]

うん？うん。

[kasumani]

スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す（C++） 筑波大学のスパコン「T2K-Tsukuba」で約2時間36分かけて5×5の魔方陣（≠魔法陣）の全解を求めたというニュースがありました。 Tags: fro

[hazisarashi]

うける

[akausii]

PCだと10分 --

[UhoNiceGuy]

漏れも作ってみよ

[diet55]

カッチョイイ！！ QT @hatebu: スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す（C ） | 配電盤 (52 users)

[kkobayashi]

力技VSアルゴリズムだな

[Kureduki_Maari]

.｡oO(ふぇ？) スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す（C++）

[itochan]

ここ試験に出ます

[tmtms]

"「スパコン」ではなく「パソコン」だったらどうなのだろう、と思って試してみたら、10分でした"

[dobonkai]

大人気なさは僅かにあるけれどこういう大人の背中を見せることで若者が奮起して欲しいと切に願う。

[fb001870]

頭いい人たちがいる

[kusigahama]

Core i7 4930Kが163.2GFLOPS、T2K-Tsukubaが95.4TFLOPSなので584倍のハードウェア性能差がある。なのに15.6分の1の時間で終わってるので、高校生よりこのおっさんのコードの方が9119倍速いことになる

[t_shimaya]

実装自体は力技でも、やろうとしてること(アルゴリズムや条件付け)が上手ければうまく回るもんだな。

[puchiban]

なぜ筑波大がスパコン・リソースをそのようなことに使ったのか?の方が気になってしょうがない。

[kuippa]

意外と３×３のグリッド総和を対角線上で２個取ればもっと少なくなりそうだけど