prime's diary

そすうの日々を垂れ流しちゃうやつだよ

オセロの着手可能位置生成 【ビット演算テクニック Advent Calendar 2016 23日目】

はじめに この記事はビット演算テクニック Advent Calendar 2016の23日目の記事です。 www.adventar.org オセロとビット演算 オセロは盤面サイズが8x8=64マスなので、64bit変数を2つ用意し、1つめを自分の石(あるいは黒石)の位置を、2つめを相手の石(ある…

GPGPUで爆速でオセロを解く 【KMC Advent Calendar 2016 19日目】

はじめに この記事はKMC Advent Calendar 2016の19日目の記事です。 www.adventar.org GPGPUとは GPGPU(General-purpose computing on graphics processing units; GPUによる汎用計算)とは、GPUの演算資源を画像処理以外の目的に応用する技術のことである…

Bit scan reverseをAVXで並列化する

Bit scan reverse (bsr) 00000001010100010100000100101101 <-clz->*<---bit scan reverse---> 1になっている最も高位のビットのインデックスを0-indexedで計算します。0に対する結果は未定義(不定)です。 似た処理にcount leading zero(clz)があり、こち…

pclmulqdqを用いたビット単位のunpack【ビット演算テクニック Advent Calendar 2016 11日目】

この記事はビット演算テクニック Advent Calendar 2016 www.adventar.org の11日目の記事です。 ビット単位のunpack C++の固定長ビット配列を扱うクラスstd::bitsetを例として解説します。 std::bitset<128> unpacklo(const std::bitset<128> &a, const std:…

Delta swapとその応用 【ビット演算テクニック Advent Calendar 2016 3日目】

この記事はビット演算テクニック Advent Calendar 2016 www.adventar.org の三日目の記事です。 ビット列の部分列を入れ替える操作を効率的に行えるDelta swapを紹介します。xorが好きなのでDelta swapも好きなテクニックの一つです。 行える操作 マスクとず…

ビット列による部分集合表現 【ビット演算テクニック Advent Calendar 2016 1日目】

はじめに この記事はビット演算テクニック Advent Calendar 2016 www.adventar.org の1日目の記事です。 この記事ではビット演算を使って有限集合の部分集合を表現、操作するテクニックを紹介します。 本文中で説明を省略した部分については、詳しい説明のあ…

CUDAで再帰するとき

CUDAではDynamic Parallelism(GPU側から新たなカーネルを起動する)以外に普通の(シリアル実行の)再帰が可能です(Compute Capability 2.0以上)。 しかし、再帰的に関数を呼び出す場合、必要なスタックサイズが静的に割り出せないことがあり、このときはデ…

コミックマーケット89記念!ANSI C89コンパイラを作る【KMCアドベントカレンダー12日目】

この記事はKMC Advent Calendar 2015 - Adventar12日目の記事です。 宣伝 サークル「京大マイコンクラブ」は、コミックマーケット89で「木曜日 東地区 "モ" 42b」に配置されました! コミケWebカタログにてサークル情報公開中です https://t.co/BtKSerlV6R #…

高速文字列処理ライブラリを作った

この記事はポエムアドベントカレンダー4日目の記事です。 www.adventar.org 大量の文字列データを扱うことの多くなった現代において、文字列処理ライブラリの高速化は重要である。 しかしながら、個人レベルで汎用的かつ高速な文字列処理ライブラリを作成す…

RubyからGoの関数をつかわなくても再帰をやめなくてもアルゴリズムを改善する→はやい

qiita.com mattn.kaoriya.net という記事を読んだのでアルゴリズムを改善して速くしました。 いわゆる行列累乗のテクニックを使うと(乗算部分を除けば)N番目のフィボナッチ数はで求まります。 実際にはフィボナッチ数は指数的に増大するので乗算にかかる時…

【failに】ISUCON5の決勝に出たけど記録を残せなかった【人権はない】

お金が欲しいので(直球)、優勝賞金100万円のISUCONの決勝に出ました。予選については primenumber.hatenadiary.jp を参照。 当日起きれるか不安だったので前日入りしてカプセルホテルに泊まった。 人生初のカプセルホテルだったが、あまり寝られなかった。…

ISUCON5の予選に出て学生枠1位で通過した(チーム名: 古典論理の犬)

お金が欲しいので(直球)、優勝賞金100万円のISUCONの予選に参加して、13609点、二日目全体で11位(?)学生枠1位で通過した(学生枠で登録した中では一般枠で通過したチーム学生自治についで2位)。 isucon.net チーム チーム名: 古典論理の犬 チームメン…

std::atan2

第一引数はy座標、第二引数はx座標

gccでSIMD命令等のIntrinsicsを使う時のメモ

やりたいこと Intel Intrinsics Guideに載っている組み込み関数を使いたい 具体的には今作っているオセロAIの高速化のため 調べた環境 GCC 5.1 (Arch Linux) 使い方と注意 だいたいの(実際の実行環境で使用出来る)命令の組み込み関数は各関数で指定されたヘ…

AOJ 1351 Flipping Parentheses

問題文 ICPC Asia 2014 Tokyo G Flipping Parentheses | Aizu Online Judge 解法 想定解法と違うけど通ってしまった http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1174168#1 (を1、)を0とみなして01列として扱って、64bitまとめて操作する 各64bit…

Brainf*ck + リフレクション = BFmeta 【KMCアドベントカレンダー26日目】

おはようございます!! KMC2回生のprimeです!! この記事は今年もやります!KMCアドベントカレンダー!! - KMC活動ブログの26日目の記事です。昨日の記事は、primeさんのお詫び 【KMCアドベントカレンダー25日目】 - KMC活動ブログでした。 はじめに Brai…

ICPC アジア地区予選 東京大会 2014 参加記

結果 5完17位(University rank14位)でした。 Colorful Jumbo ChickenがおそらくWF出場権を得ます。今回の結果を考えると、仮に台湾大会でWF出場権を得てもおそらくWFは辞退することになります。 コンテスト中にしたこと 筆箱を忘れる .Xmodmapを書く .vimrc,…

ICPC 国内予選 2014 参加記

ICPCの国内予選に出たことについての感想を書きます。 チームと結果 チーム名: Primasta メンバー: @asi1024 @TakiTakiTakise @_primenumber 6問正答/全7問, ペナルティ: 23875 全体で5位、大学別4位、大学内1位 国内予選が始まるまで 京大から他にAlkachu,C…

Lenovo ideapad s210上のDebian wheezyで無線LANを使えるようにするには

必要な作業は多くないけど、日本語の情報もないので備忘録程度に書いておきます。 症状 Lenovo ideapad s210上のDebian wheezyで無線LANが使えない NetworkManagerの画面にそもそも無線接続の選択肢が出てこない 無線LANデバイスの型番を調べる なにはともあ…

ブラウザ上でBrainf*ckを実行・デバッグできるサービスを作りました.

Brainf*ckインタプリタ デバッグモードをONにして,「1ステップの実行時間」を0より大きい値にするとプログラム実行中のメモリの様子や今どこを実行しているかがリアルタイムでわかります.コード中に@があると,そこでプログラムが一時停止するので,簡易的なブレ…

実用Brainf*ckプログラミング

高校生の頃にBrainf*ckでFibonacci数を計算して表示するプログラムを書いて以来,何度かBrainf*ckのコードを書く機会があった.受験生の頃には,受験勉強をするふりをしてHanoiの塔を解くBrainf*ckのコードを書いた. 京大生になってKMCに入って,いろいろな面白…

はじめに

このブログにおける私の目的は,全宇宙に向けて,最近やったことを自慢するために,積極的に発信していくことです. このブログには手短に要点だけを書いて,まとまったドキュメントはprojectpnに貯めていく予定です.projectpnと同様,ジャンルは縛らずに興味の湧…