Windows 10 May 2020 Update 後に DvorakJ を使う

親指シフトなどかな入力系を使っている場合は以下が参考になります(本稿も当該記事を参考にしています。ありがとうございます)。 Windows 10 May 2020 Update とDvorakJ での親指シフト入力の問題を解消する 症状 Dvorak配列にしてローマ字入力をすると、[…

最大公約数をもっと高速に求める番外編(その2)

前回のコードを最適化していきます。 主要なループ*1のうち、最も時間がかかるのはctz部分(3サイクルレイテンシのBSF命令にコンパイルされます)です。 これを少しでも早く実行開始できれば、さらに高速に動作するはずです。 ここで、二の補数表現の特徴か…

最大公約数をもっと高速に求める番外編(その1)

なんだか最近最大公約数を高速に求めたい読者(競技プログラマ?)が多いようなので、書いておきます。 最大公約数を求める改良版アルゴリズムとして、Stein's algorithm(Binary GCD)というものがあります。 ナイーブな実装では、普通の互除法よりも遅いで…

ウィンナ・チューバの仕組みの予想

ウィンナ・チューバ - Wikipediaを見ていて、どういう仕組みになっているのか面白いと思ったので、メモです。 私は金管楽器を*1演奏したことが一切ないので、以下に書かれていることは、あくまで物理的な計算に基づいた憶測です。 Wikipediaによれば、ウィン…

毎週末に何かしらの締め切りがあって、インプットもアウトプットもできない日々が続きます…… あまりこういう癖をつけないように、来週からは何か少しずつでも始めましょう。

0からN-1までの数が入った配列

今までは以下のように作っていましたが、 template<std::size_t... Indeces> constexpr auto make_iota_impl( std::index_sequence<Indeces...> ) { return std::array { Indeces... }; } template<std::size_t N> constexpr auto make_iota() { return make_iota_impl( std::make_index_sequence<N>() ); } C++20で</n></std::size_t></indeces...></std::size_t...>…

PPM-like分岐予測器とTAGE分岐予測器の違い

An Alternative TAGE-like Conditional Branch Predictor https://hal.inria.fr/hal-01799442/document という論文に載っていて、 TAGE分岐予測器は、PPM-like分岐予測器と異なり、 * グローバル分岐履歴の最長一致で予測を立てるのではなく、二番目に長く一…

いそがしい一週間の終わり

世界から人間が消えた気がする

あまりしゃべらないと調子よくない気がする ちゃんと調整していきたいです

make_index_sequenceを短く書いた(C++11用)

std::make_index_sequence<N>は、std::index_sequence<0, 1, 2, ..., N-1>に展開される、メタプログラミングを行う場合や最適化に便利なエイリアステンプレートです。 しかし、以下の問題点があります。 C++14で追加されたため、C++11環境では使えない*1 多くの</n>…

バーチャルっていろいろときれいなのがいいね

リングバッファを作るときstd::dequeを使うのはちょっと楽でちょっと損

容量に上限があるキューを実現するためには、リングバッファを用いるのが最も効率的です。 しかし、ポインタの操作を含むコードを自分で書くのは間違いのもとです。効率を最優先する場合以外は、ライブラリを使うほうが良いです。 C++の場合、std::deque*1を…

gshare分岐予測器について、の補足

gshare分岐予測器について - よーるの補足です。 分岐命令の上位アドレスとグローバル分岐履歴をxor、について 吉瀬 謙二, 片桐 孝洋, 本多 弘樹, 弓場 敏嗣:「高性能プロセッサのための代表的な分岐予測器の実装と評価」Technical Report UEC-IS-2003-2, Ve…

gshare分岐予測器について

gshare分岐予測器というのは、単純な構造の分岐予測器の中では最も性能が良い分岐予測器であり、1993年に発表されました。 このgshare分岐予測器について、あまり教科書に書いていないことを調べたので、まとめておきます。 この記事には、以下のものが含ま…

いつも通りの日々の連続?

クイックソートのピボットは中央値でなく四分位数を選択したほうが高速

概要 クイックソートは一般に高速なソートアルゴリズムとして知られています。 アルゴリズム中にはピボットを選択する部分がありますが、ここでなるべく中央値に近い値を選択すると、総比較回数を少なくすることができます。 しかし、最近の高性能プロセッサ…

sshでログインできなくなった問題と解決策

リモートマシンにsshログインしようとしたところ、パスフレーズの入力後に何も反応しなくなることがありました。 正しくない公開鍵を使った場合や、正しくないパスフレーズを入力した場合はログインできないと応答が返ってくるので、リモートマシンの側の問…

近況

輻輳が発生しています……

64bit符号なし整数を素因数分解するのにかかる時間

64bit符号なし整数を素因数分解するため、事前に32bit符号なし整数で表せる素数をリストアップしておくとします。 方法1: 素数のリストをビットベクトルで保持し、試し割り 32bit符号なし整数で表せる奇数が素数であるかを、0, 1で表した列(ビットベクトル…

ABC152のE問題 Flatten を遅い方法で解いた

以下にはABC152のE問題 Flatten のネタバレが含まれます。 この問題は多倍長整数を使用できる言語であれば愚直解が通ります。Haskellで書かれた愚直解のコードは、例えばSubmission #9632460 - AtCoder Beginner Contest 152が簡潔で読みやすいです。 foldr …

Karatsuba乗算の最適化をした

Karatsuba乗算、あるいはToom–Cook2乗算とは、入力a0、a1、b0、b1が与えられたとき、a0*b0、a0*b1+a1*b0、a1*b1の三つを出力する際、必要な乗算を四回から三回に減らせるアルゴリズムです。ただし、減算ができることを要求します。 長乗法(筆算と同様の手順…

64bit版RISC-Vで即値を生成するときの罠

RISC系の命令セットでは、一命令でレジスタに書き込める即値と、一命令では書き込めない即値が存在する設計になっています。 一命令では書き込めない即値の場合、二命令以上かけて即値を生成することになるわけですが、そこに存在する罠に引っかかった記録で…

新年になりました

今年もよろしくお願いします。 2020ってちょっと不思議な感じのする数字です。 今年は、きっかけを待つのではなくて、自分で行動を起こせる年にしたいです。 あと、お酒飲むのやめます。心身の健康に悪いので……。

write関数の変な使い方

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

FPGA上で動くBrainfuckCPUを作った

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

VivadoのBlockRAM推論がおかしい

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

分岐命令の意味論一覧

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

Brainfuck コードを最適化コンパイルする~C++メタプログラミングで~

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

容量上限付き可変長配列の空間計算量

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

ロスってこんな形なのかな

なんか違った気がする