ゴルフの話ではないです（ゴルフに役立たないとは言っていません）。 C言語のwrite関数は、unistd.hで宣言された、ファイルディスクリプタを通じて書き込む関数です。その宣言は以下のようになっています。 ssize_t write(int fd, void* buf, size_t len) コ…

これはBrainf*ck Advent Calendar 2019 - Adventar25日目の記事です。 Brainfuck命令セットを実行するCPUをVerilog HDLで記述し、FPGAで動かしてみた記録になります。 まず、ハードウェアを意識しつつ命令セットシミュレータ（というかインタプリタ）を作成…

東大のプロセッサ実験のwiki *1を見ると、読み出しアドレスをクロックに同期してregに書き込めば、（write-firstの）BlockRAMに推論されると書かれています。 そこで、1read/1write・読み書き両方ともクロック同期のRAMを、以下のように書いてみます。 modul…

機械語には複数種類の分岐命令があり、しかも一つの分岐命令でも異なる意味論で使ったりします。 どういう意味論を持っているか、まとめてみました。 以下では、無条件分岐命令か、あるいは条件分岐命令で条件が成り立った場合の意味論についてまとめます。 …

この記事は、Brainf*ck Advent Calendar 2019 - Adventarの八日目の記事です。 Brainfuckをインタプリタで実行するとかなり遅いです。 高速に実行する一つの簡単な方法に、「C言語に変換する」という方法があります。 Wikipediaにも書いてありますが、以下の…

boost::container::static_vectorのような動作をする、容量の上限Nがコンパイル時に決められた値であり、実行時に配列の要素数sizeを（上限までの範囲で）変更できるようなデータ構造を考えます。 これを実現するには最低何bitの空間が必要でしょうか？ 要素…

なんか違った気がする

まずA1セルに1を入れ、A2セルには=A1*2と記入します。次に、A2セルのフィルハンドル（セルの右下にカーソルを合わせたときに出現する十字型のカーソル）を下にドラッグし、100セルほどコピーします。 このようにすると、2Nという数列を計算することができま…

次の短いC++プログラムをg++ -g -O1などでコンパイルしてみると、非常に時間がかかります。最適化レベルは、-O0以外のどの最適化でも発生します。 struct Int { int n; Int() : n(0) {} }; struct Array { Int data[8000]; Array() : data{} {} } arr; [Wand…

主要型（principal type）のある体系とは、以下の性質を満たすような体系です。 型環境と項が与えられた時、につく型（一般に複数ありうる）は、何らかの型を具体化したものになっている。 一方、主要型付け（principal typing）のある体系とは、以下の性質…

先週、以下のように書きました。 という項には、という型がつく という項にはという型がつく これらを組み合わせても、の型検査を通すことができない しかし、は、簡約が停止する この矛盾がよくわからなかったのですが、詳しく調べたところ分かったので書い…

論理体系のうちの一つとしてのCoCではなくて、ラムダキューブの位置頂点であるλCと言った方が適切かもしれません。 λCは、全称型・型演算子・依存型をすべて含む、非常に表現力の高い型付きラムダ計算の体系です。 表現力が高いにもかかわらず、型検査が通れ…

切り替えて時間を有効に使いたい

void explicit_bzero(void* s, size_t n)という関数があります。これの動作は、void bzero(void* s, size_t n)という関数と同じです。 void bzero(void* s, size_t n)という関数は、memset(s, '\0', n)と同じ動作をします。つまり、memset関数の方が上位互換…

普通の電卓には対数を求める機能はないと思いますが、何とかして求めてみます。 たとえば、を求めてみます。 2×2=4、4×2=8、8×2=16……のように2nを求めていきます。すると、210=1024が10の累乗数に近いことが分かります。この関係から、であることが分かりま…

追記とお詫び（2023/06/25 07:45） 紹介していたコードが一文字間違っており、完全精度となっていない（どころかほとんどの入力に対して正しい値を返さない）実装になっていました。 const double t = std::fma( k, -ln2l, std::fma( k, ln2h, static_cast<double>(x</double>…

最近のglibcは数学関数の高速化に取り組んでいるため確実なことは言えませんが、多くの環境ではC/C++の数学関数はこのglibcの実装を使うことになっているはずです。 glibcのexp関数の実装は、IBM Accurate Mathematical Libraryを使っているようです。 参考…

以下に紹介するのは15年前の技術なので、全然最新じゃないですね。 最近の分岐予測器でも使われる優秀な技術ということでしょう。 folded history グローバル履歴数百ビットを、高々20ビット程度に圧縮するハッシュ関数をどう作るかという問題の解決策です。…

高性能なプロセッサを作るためには、予測精度の高い分岐予測器が不可欠です。 ほとんどの分岐予測器は、主に以下の情報を使います。 * 分岐命令のあるアドレス(プログラムカウンタの値、PC） * 直近のいくつかの分岐について、分岐が成立だったか、不成立だ…

すごく重箱の隅っぽいことについてです。 計算結果が有限だがINFに丸められる場合 方向丸め（正の無限大への丸め）の場合、真の結果が正規化数で表せる最大数よりも大きい場合、+INFに丸められます。 最近接丸めの場合、真の結果がどんな数でも"無限大"の方…

よく知られた事実ですが、指数的な回数の再帰呼び出しが行われるため、実用的ではありません。 フィボナッチ数列を計算する再帰関数は再帰の仕方がわかりやすいですが、よくわからない再帰の仕方の関数の場合はどうでしょうか？ 関数が呼ばれたときにデバッ…

きっともっとやすんだほうがいい

Linuxのシステムコール62番は、64bit版の場合、lseekです。 off_t lseek(int fd, off_t offset, int whence); lseekシステムコールは、第一引数にファイルディスクリプタ、第二引数にどれだけ移動させるか、第三引数に動作の種類を受け取り、最終的な位置を…

結構前の、constexpr関数を高速化する方法 - よーるという記事で、低速なconstexpr文脈の中でもある程度の速さで配列操作を行う方法として、パック展開を利用した配列を一気に構築する手法を紹介しました。 これを利用したバイトニックソートは、たとえば私…

Brainfuckのインタプリタの書き方によって、実行速度が変わるのかが気になったため書いてみました。 もちろん、前処理、特にその場でコンパイル (just in time compile) をするなどすれば高速化は容易です。 そうではなく、ごく単純なswitch文を使うような、…

オープンなISAであるRISC-Vには、32bit版も定義されています。 spikeは、RISC-Vの公式が開発している命令セットシミュレーターです。 以下の手順で必要なソースコードを持ってきます。 $ git clone https://github.com/riscv/riscv-tools.git $ cd riscv-too…

なんか最近忙しくないはずなのに、忙しいような気がしています。 たぶん原因は、塊として認識できない、こまごましたやらないといけないことが多いことのような気がします。 あとは、それをやることのできる時間が限られている（持ち時間が少ないという意味…

今日は七夕だったようですが、あいにくの雨でした。 出力ファイルを全部つなごうとcat *.outと打ったところ、a.outも巻き込まれてコンソールが大変なことになりました。 このミスは二回目なので、対策することにしました。 あまりうまい方法が思いつきません…

ちょっと違う世界に行っていました。 そこの住人は親切で、 いや、不親切な対応もあったような気がしますが、トータルでは親切だったなぁという印象でした。 それ以外はあんまり印象に残っていないってことは、そんなに違わなかったってことなのでしょう。

最近テンプレートメタプログラミング (Template meta programming, TMP) から離れているなぁと思ったので、また書いてみました。 Quine（クワイン）とは、自分のソースコードを出力するプログラムのことです。 ソースコードは以下に公開してあります。C++11…