概要 クイックソートは一般に高速なソートアルゴリズムとして知られています。 アルゴリズム中にはピボットを選択する部分がありますが、ここでなるべく中央値に近い値を選択すると、総比較回数を少なくすることができます。 しかし、最近の高性能プロセッサ…
リモートマシンにsshログインしようとしたところ、パスフレーズの入力後に何も反応しなくなることがありました。 正しくない公開鍵を使った場合や、正しくないパスフレーズを入力した場合はログインできないと応答が返ってくるので、リモートマシンの側の問…
輻輳が発生しています……
64bit符号なし整数を素因数分解するため、事前に32bit符号なし整数で表せる素数をリストアップしておくとします。 方法1: 素数のリストをビットベクトルで保持し、試し割り 32bit符号なし整数で表せる奇数が素数であるかを、0, 1で表した列（ビットベクトル…
以下にはABC152のE問題 Flatten のネタバレが含まれます。 この問題は多倍長整数を使用できる言語であれば愚直解が通ります。Haskellで書かれた愚直解のコードは、例えばSubmission #9632460 - AtCoder Beginner Contest 152が簡潔で読みやすいです。 foldr …
Karatsuba乗算、あるいはToom–Cook2乗算とは、入力a0、a1、b0、b1が与えられたとき、a0*b0、a0*b1+a1*b0、a1*b1の三つを出力する際、必要な乗算を四回から三回に減らせるアルゴリズムです。ただし、減算ができることを要求します。 長乗法（筆算と同様の手順…
RISC系の命令セットでは、一命令でレジスタに書き込める即値と、一命令では書き込めない即値が存在する設計になっています。 一命令では書き込めない即値の場合、二命令以上かけて即値を生成することになるわけですが、そこに存在する罠に引っかかった記録で…
今年もよろしくお願いします。 2020ってちょっと不思議な感じのする数字です。 今年は、きっかけを待つのではなくて、自分で行動を起こせる年にしたいです。 あと、お酒飲むのやめます。心身の健康に悪いので……。
ゴルフの話ではないです（ゴルフに役立たないとは言っていません）。 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に丸められます。 最近接丸めの場合、真の結果がどんな数でも"無限大"の方…
よく知られた事実ですが、指数的な回数の再帰呼び出しが行われるため、実用的ではありません。 フィボナッチ数列を計算する再帰関数は再帰の仕方がわかりやすいですが、よくわからない再帰の仕方の関数の場合はどうでしょうか？ 関数が呼ばれたときにデバッ…
きっともっとやすんだほうがいい
