サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
大谷翔平
primenumber.hatenadiary.jp
この記事はいろいろなコンピューター Advent Calendar 2023の9日目の記事です。 adventar.org Brainf*ckとは Brainf*ck(この記事では一部伏字にして表記しています)は難解プログラミング言語のひとつです。 コンパイラがなるべく単純になるように設計されており、わずか8種の命令+ - > < [ ] . ,のみが存在する手続き型プログラミング言語です*1。 詳しい言語仕様等はEsolang wikiの記事 brainfuck - Esolang 等を参考にしてください。 仕様は単純ですが、チューリング完全なので、理論上はどんな計算でもすることができます。 Brainf*ck CPUを作る 今回は、Brainf*ckのコンパイラでもインタプリタでもなく、ソースコードを直接実行できるCPUを作りました。 できたものがこちらになります。 github.co
この記事はいろいろなコンピューター Advent Calendar 2023(さっき作った)の1日目の記事です。 adventar.org 背景 さて、昨今のCPUはどんどん高速化し、クロック周波数も5GHzを超えることは珍しくなくなりました。 一方で、ここまで高速化すると問題になるのが光速です。 5GHzというのは50億分の1秒に1サイクルということなので、この間に光は真空中でも60mmしか進むことができません。 媒質中では屈折率に反比例して遅くなるので、例えば屈折率1.5の光ファイバーがあったとすると、40mmほどしか進めません。 一方で、単位体積あたりに詰め込める計算ユニットやメモリセルは有限なので、大きな並列度を持った計算機を作ったり、大容量の記憶装置を持ったりするには、それに応じた体積が必要です。 しかし、光に限らずあらゆるものは真空中の光速を超えることはできないので、大きくなれ
この記事はKMCアドベントカレンダー2021の4日目の記事です。 adventar.org 概要 元ネタ:『フカシギの数え方』 www.youtube.com 問題としてはN×Nマスのグリッド(頂点としては 頂点)を左上から右下まで移動する経路であって、同じところを二度通らないものの数を数える、というものになっています。 『フカシギの数え方』でお姉さんが数え上げていた問題を、実際に全探索で解いてみて、組合せ爆発の凄さを体感しつつ、GPGPUで頑張って高速化してみます。 CPUで全探索 これを全探索で解くためには、これまでに通った場所を覚えておいて、そこを通らないようにしつつ、右下の頂点までたどり着けるものを探せばよいです。 これはバックトラックによって簡単に数え上げることができます。 RustでCPU向けに実装したものがこちらになります github.com バックトラック部分の本体は f
この記事はKMCアドベントカレンダー 2日目の記事です adventar.org 概要 最近遊んでいるVRChatというゲームにはユーザーの作成したアバターやワールドをアップロードできる機能があります。さらに、アバターやワールドのバーテックスシェーダー*1/フラグメントシェーダー*2を自分で作ったものに差し替えてアップロードすることができます。 これを悪用(?)し、fragment shaderにBrainf*ckという難解プログラミング言語のインタプリタを実装することで、VRChatで、ゲームプレイ中に指定した任意の計算を実行することができるような仕組みを実装しました*3。 VRChatのワールドでBrainf'ckインタプリタ動いた! pic.twitter.com/92pfXoijzk— そすうぽよ (@_primenumber) 2020年11月30日 #VRChat のBrain
この記事はKMC Advent Calendar 2018 - Adventarの2日目の記事です。 adventar.org 概要 理研に設置されているスーパーコンピューター、菖蒲(Shoubu)・菖蒲SystemBでPEZY Computing社のPEZY-SC/SC2を使わせてもらいました。 性能とか使いやすさについて感想とか知見を述べます。 PEZY-SC/SC2について PEZY Computing社の開発したプロセッサで、メニーコアのMIMD(Multiple Instruction, Multiple Data)プロセッサであることが特徴です。 MIMDなので各コアで全く異なる命令を独立に実行できる点でGPUなどのSIMDプロセッサと異なります。 使えるようになるまで 理研に設置されているスーパーコンピューター、菖蒲(Shoubu)は一般の人でも申請して認められれば無料で使う
この記事はKMCアドベントカレンダー22日目の記事です。 adventar.org この記事では全国一億三千万のビット演算マニアのために、AVX512命令セットからビット演算に使えそうなものを紹介します。 AVX512の基本 AVX512とは Advanced Vector Extensions(AVX)というx86/x64のベクトル演算拡張命令を512ビット幅に拡張したものです。 普通のCPUではSkylake-SP/X/Wから使えるようになりました。 512bitのデータを一括で処理できます。ビット演算なら512並列ですよ512並列。 AVX512になって変わった主なこと レジスタ幅が最大512bit(ZMMレジスタ)に(それはそう) 論理レジスタ数が16から32に倍増 マスクレジスタ(k0-k7)の追加 各種ビット操作・バイト操作命令の追加 AVX512の命令セット AVX512は複
はじめに この記事はビット演算テクニック Advent Calendar 2016の23日目の記事です。 www.adventar.org オセロとビット演算 オセロは盤面サイズが8x8=64マスなので、64bit変数を2つ用意し、1つめを自分の石(あるいは黒石)の位置を、2つめを相手の石(あるいは白石)を表すために使うと合計128ビットで自然に表現できます。*1 自然に表現できるだけでなく、盤面の回転や反転などもDelta swapとその応用 【ビット演算テクニック Advent Calendar 2016 3日目】 - prime's diaryで紹介したような方法で効率的に行なえます。 着手可能位置の生成はタテ・ヨコ・ナナメの一直線上をpextなどで取ってきて表引きをすることにより、ある程度の速度で可能ですが、(38=6561なのでL1キャッシュに乗る程度の大きさとはいえ)メモリアク
はじめに この記事はKMC Advent Calendar 2016の19日目の記事です。 www.adventar.org GPGPUとは GPGPU(General-purpose computing on graphics processing units; GPUによる汎用計算)とは、GPUの演算資源を画像処理以外の目的に応用する技術のことである。 (出典: GPGPU - Wikipedia ) GPUは並列演算に特化しており、大量のスレッドをハードウェアで処理でき、汎用CPUに比べて演算処理性能が高いという特徴があるので、これを用いて演算を高速に行おうというのがGPGPUのアイデアです。 ただ、良いことばかりではなく、汎用CPUに比べてプログラミング上の制約が大きいなど、性能を出し切るのはかなり難しいです。 GPGPUでオセロを解く 今回はGPGPUを用いてオセロの終盤の完全読
はじめに この記事はビット演算テクニック Advent Calendar 2016 www.adventar.org の1日目の記事です。 この記事ではビット演算を使って有限集合の部分集合を表現、操作するテクニックを紹介します。 本文中で説明を省略した部分については、詳しい説明のある参考文献を紹介しておきます。 2021/01/03: 高速ゼータ変換/メビウス変換/畳み込みに関する部分を全面的に書き換えました。 表現方法 S={A,B,C,D}という4要素の集合があったとします。 各要素を次のように2進数の数字と対応付けます。 A: 0001 B: 0010 C: 0100 D: 1000 こうすると、Sの部分集合は存在する要素のビットごとの論理和を取ることで4ビットのビット列として一意に表すことができ、例えば {A,B,C}: 0111 {B,D}: 1010 のようになります。 以後、
この記事はKMC Advent Calendar 2015 - Adventar12日目の記事です。 宣伝 サークル「京大マイコンクラブ」は、コミックマーケット89で「木曜日 東地区 "モ" 42b」に配置されました! コミケWebカタログにてサークル情報公開中です https://t.co/BtKSerlV6R #C89WebCatalog— 京大マイコンクラブ (@KMC_JP) 2015年10月30日 部誌、自作ゲーム、そして今回の本題であるコンパイラのソースコードを置く予定です。 3日目(12月31日)東地区 "モ" 42bです!よろしくお願いします!!*1 本題 今度のコミックマーケットは89回目です。コミックマーケット89は通称C89と呼ばれています。 C89といえばC言語の最初の標準規格ANSI-C:1989(通称C89, ANSI C89など)ですね! こうなったらやること
この記事はポエムアドベントカレンダー4日目の記事です。 www.adventar.org 大量の文字列データを扱うことの多くなった現代において、文字列処理ライブラリの高速化は重要である。 しかしながら、個人レベルで汎用的かつ高速な文字列処理ライブラリを作成することは難しい。 今回は汎用性を少し下げることにより圧倒的な高速化をした文字列処理ライブラリ「A」を制作した。 ソースコード gist.github.com ライブラリの仕様 文字列の制約 すべての文字がAで構成されていること 制約を満たす文字列の例 AAAAAA AAAAAAAAAA 制約を満たさない文字列の例 aaa ABCDE 制約を満たさない文字列を用いた場合、正しくない結果を得る可能性がある。 利用方法 ライブラリ中では専用の効率的なデータ構造により文字列を管理する。そのため、利用するにはstd::stringから変換処理を行
qiita.com mattn.kaoriya.net という記事を読んだのでアルゴリズムを改善して速くしました。 いわゆる行列累乗のテクニックを使うと(乗算部分を除けば)N番目のフィボナッチ数はで求まります。 実際にはフィボナッチ数は指数的に増大するので乗算にかかる時間が支配的になるのでもっと遅くなります(Karatsuba法なら、高速フーリエ変換を使えば)。 単純な足し算のループでは足し算の桁数を考えると なのでそれよりは随分と速くなります。 40番目ぐらいでは実行時間はほとんど0なので100万番目のフィボナッチ数を求めてみます。 こちらが元のソースコード def fib(n) f0, f1, v = 0, 1, 0 n.times do |x| if x <= 1 v = x else v = f0 + f1 f0, f1 = f1, v end end return f0 + f1
お金が欲しいので(直球)、優勝賞金100万円のISUCONの予選に参加して、13609点、二日目全体で11位(?)学生枠1位で通過した(学生枠で登録した中では一般枠で通過したチーム学生自治についで2位)。 isucon.net チーム チーム名: 古典論理の犬 チームメンバー: @lastcat_ @nonylene @_primenumber チーム名の由来 KMC内でISUCONに出るぞ!!ってなって6人集まったのでnotaで働いてる人(@nonamea774 @pastak @uiureo, チーム学生自治)とそうでない人でそれぞれチームを作った。 not notaなのでnot not a ⇒ aってなって二重否定の除去マンだ、古典論理の犬だ!!ってなって決まった。 流れ 予選まで 8月の末ぐらいからチームで何回か練習をした。 最初にISUCON1からやろうとしてAMIとかもないし流
おはようございます!! KMC2回生のprimeです!! この記事は今年もやります!KMCアドベントカレンダー!! - KMC活動ブログの26日目の記事です。昨日の記事は、primeさんのお詫び 【KMCアドベントカレンダー25日目】 - KMC活動ブログでした。 はじめに Brainf*ckというプログラミング言語をご存じでしょうか。ご存じの方はこの節を飛ばして「Brainf*ckでプログラミングする」に進んでいただいて構いません。 ご存知でない方に簡単に説明すると、Brainf*ckはなるべくコンパイラが小さくなるように設計されたプログラミング言語で、最低限の手続き型言語の機能を実装しており、わずか8命令だけ*1でプログラミングできるという、まさに手続き型言語のエッセンスを凝縮したプログラミング言語です。 Brainf*ckの言語仕様 プログラムは最初、0で初期化された無限長の配列*2
このページを最初にブックマークしてみませんか?
『prime's diary』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く