素数を数えるアルゴリズムの理解

与えられた整数に対し、以下の素数の数を数えるアルゴリズムを理解します。 Library Checkerで高速な実装を調べてみると、提出107115が最速ですが、このソースコードは未定義動作を含んでいます(ランキング上位を見てみると、62015, 107115, 147826, 150290…

MN-Core 2の機械語ゴルフに入門する

今週の水曜日にMN-Core勉強会があり、そこでMN-Core 2のエミュレータが公開されたようです。 そこで、MN-Core 2の機械語(アセンブリ言語がvsmと呼ばれているらしい?)のコードゴルフをやってみます。 MN-Core 2の機械語なんて書いたことないので、丁寧に勉…

60bit整数を高速に素因数分解する

Library CheckerのFactorizeという問題でfastestを取ったので、そのコードの解説です(速度ランキング)。 Factorizeは、までの整数が高々100個与えられ、それらを素因数分解せよ、という問題です。 概要 上位陣(13ms~15ms)の解法では、ECM(楕円曲線を用…

Unityのgit管理をWSL2でやる

最近久しぶりにUnityでゲーム作りをしています。 共同で開発するためにgitを使うのですが、gitコマンドをWSL2から使用するといまいちな感じになったので、何とかする方法のメモです。 プロジェクトはWSL2の外に作る UnityプロジェクトをWSL2の中(/home/lpha…

なぜドルコスト平均法しないほうがいいか

新年になりました。 タイトルに関してですが、なんだか話があったので軽くまとめておきます。 要点としては、 投資の期待値が標準偏差に比して大きい(インデクスファンドなどはこの条件を満たす)投資商品がある場合、 余剰資金があるなら、 何も考えずにそ…

世界一簡単な物理レジスタ方式アウトオブオーダーCPUの作り方

この記事は自作CPU Advent Calendar 2023の24日目の記事です。 みなさんが使っているパソコンのCPUは、そのほとんどがアウトオブオーダー実行をしているはずです。 しかし、アウトオブオーダーCPUの作り方が書かれた教科書はあまりないような気がします。 ト…

0.1+0.2≠0.3について

浮動小数点数を扱う時に注意しなければいけない例として、0.1 + 0.2が0.3にならない、というものがあります。 具体的には、0.1 + 0.2が0.30000000000000004になってしまい、0.3にならないプログラミング言語が多数存在します。 この問題について、以下の記事…

gccが呼び出し規約に従わないコードを出力する例

アセンブリプログラムを書いていたら、遭遇したのでメモです。 さすがにプログラム全てをアセンブリ言語で書くのは大変なので、性能上重要ではないところはコンパイラのコード生成に任せて、性能上重要なところだけアセンブリプログラムで書くということはあ…

x86のアドレッシングモードと使えないレジスタについて

x86はCISC命令セットであり、RISC命令セットと異なりメモリ上のデータを命令のオペランドに取ることができます。 x86のレジスタは(特に32ビットと64ビットは)おおよそ汎用ですが、一部のレジスタはアドレッシングに使えない制限があります。 よくわからな…

TAGE系分岐予測器のTAGEではない部分に関するメモ

(主にAndré Seznec氏が開発している)TAGE系分岐予測器は、TAGE部分以外の工夫にいろいろなバリエーションがあります。 しかしそれらは謎の短い略語で区別されており、覚えるのが困難です。 それに関するまとめのメモです。 cbp1(2004/12/5, 37th MICRO併…

絶対値のLeading Zero Anticipatory (LZA)の勉強

Leading Zero Anticipatory (LZA)は、二進法で表されたNビット符号つき整数A, Bを受け取り、A+Bを直に計算することなしにA+B+1の上位に0が何ビット並ぶか(Leading Zero Count, LZC)を(多少の誤差の範囲で)予測することです。 以前の記事(Leading Zero A…

RISC-VのZicondとかいう排除アートについて

2023年9月にZicond拡張というのが、ろくに議論もされずに*1承認されたようです。 RISC-Vもその場の思い付きで命令セットを拡張するような、歴史に学ばない命令セットに堕したということですね。 Zicond拡張の機能はRISC命令セットとして素晴らしいものですが…

variable tracking size limit exceededと出てコンパイルが遅い場合の対処法

以下の短いコードは、g++ -O2 -g main.cpp -cなどとコンパイルすると長い時間待たされた後、note: variable tracking size limit exceeded with ‘-fvar-tracking-assignments’, retrying withoutと出力され、その直後にコンパイルが終わります。 #include <array> i</array>…

LLVMのk乗和の最適化手法について

clangは-O1以上の最適化オプションをつけると、以下のコード(単純に考えるとΘ(n)命令必要そう)からループを取り除き、Θ(1)命令のコードに最適化します。 uint64_t sum( uint64_t n ) { uint64_t ret = 0; for( uint64_t i = 0; i < n; ++i ) { ret += i; }…

Yosysを使ってみる(その1)

Yosysというオープンソースの論理合成ツール(レジスタ転送レベルからゲートレベルに変換する一種のコンパイラ)があるので使ってみました。 github.com インストール 公式のREADMEとだいたい同じです。Makefileを書き換えてインストール場所を変更すれば、…

AVX-512の機能を使ったlogf(x)の実装(その2)

前回(AVX-512の機能を使ったlogf(x)の実装(その1) - よーる)の記事で、AVX-512でベクトル実行することを前提としたlogfの高速実装を作りました。 速度を重視しつつもできる限り精度に気を付けた結果、ほとんどの入力に対して誤差を1.5ULP未満とできまし…

AVX-512の機能を使ったlogf(x)の実装(その1)

2023年6月に光成滋生さんがAVX-512特有の機能(通常の浮動小数点数演算以外の命令)を使用したlogf(x)のベクトル実装を公開しました(解説記事→AVX-512によるvpermpsを用いたlog(x)の実装)。 具体的には、指数部を取り出すvgetexpps命令、仮数部を取り出すv…

中点の正しい計算方法

二つの浮動小数点数について、中点の数学的な値はです。 以下の記事に触発されたので、この中点を浮動小数点数に正しく丸めた値を得る方法について考えます。 中点はどうやって計算するべきか - kashiの日記 当該記事によれば、この問題は意外と難しく、分岐…

constexpr関数の評価速度

最近のC++では、constexprを使って手軽にコンパイル時計算ができます。 C++20ではstd::vectorやstd::stringなどの動的なデータ構造もconstexpr指定されたため、さらに利便性が高まりました。 コンパイル時に多少の探索を行って最適な値を発見して埋め込む、…

符号なし乗算器の作り方の勉強と11ビット乗算器の設計

ビット符号なし乗算器は、ビットの符号なし整数二つを受け取り、ビットの符号なし整数を出力する回路です。 ビット乗算器は、部分積を作る個のANDゲートと個の全加算器(full adder, FA)を組み合わせて作ることができます。 この構成で全加算器が個必要なの…

式テンプレートを利用してFastTwoSumを自動生成する

倍精度浮動小数点数doubleは53 bitしか精度がありません。 これを超える精度で計算したいけれど多倍長演算は遅いので避けたい、というときに役立つのがdouble-double(疑似四倍精度)です。 double-doubleはその名の通り、doubleを二つ組み合わせることで高…

もっと高速な完全精度 expf 関数の作り方

何年か前に、高速な完全精度(すべての入力に対して最近接丸めを行う) expf 関数の作り方を明らかにしました(高速な完全精度 expf 関数の作り方 - よーる)。 その中で、を求める際に使うは、倍精度浮動小数点数の53bit精度ですら精度が不足しているので、…

wslttyのスクロールバックを以前と同じ量にする

wslttyという、WSL用の端末エミュレータがあります。 GitHub - mintty/wsltty: Mintty as a terminal for Bash on Ubuntu on Windows / WSL wslttyは、以前はスクロールバックが事実上無制限だったのですが、最近のバージョンだとたったの25万行しか保持でき…

よく見るcarry-lookahead adderはBrent-Kung adder?

Nビット加算器の基本 Nビット整数二つを加算した結果を出力する回路を、Nビット加算器と呼びます。 Nビット加算器は、もっとも単純には、全加算器(full adder, FA)をN個直列につなげば作ることができます。 この構成法のことを、リプルキャリー加算器(rip…

Leading Zero Anticipation (LZA) の勉強

Leading Zero Count (LZC) は、二進法で表された符号なし整数の上位に0が何個連続しているかを数えることです。 例えば、32ビット符号なし整数で考えると、LZC(0x80000000)は0、LZC(0x7fffffff)は1、LZC(5)は29、LZC(2)は30、LZC(1)は31、LZC(0)は32、などで…

異世界とか(その3)

またちょっと違う世界に行っていました。 住人とはたくさんお話しできたのでよかったですね。 いろいろとちょうどいい世界でした。

128bit除算も定数除算最適化したい

一般に整数除算(ここでは剰余演算も含むこととします)を行う命令は遅いです。 そのため、除算はなるべく回避したいものです。 除数がコンパイル時定数の場合、コンパイラの最適化により、除算が取り除かれることがあります。 これを定数除算最適化と呼びま…

cat a.out を防ぐ(その2)

また実行形式ファイルをcatしてしまってコンソールが大変なことになったので、対策を強化しました。 今回はa.outという名前ではなかったので、前回(cat a.out を防ぐ - よーる)の対策が働きませんでした。 どういう文字列がコンソールを破壊するのかを調べ…

分岐を増やすと速くなる不思議な現象

マイクロベンチマークを書いていたのですが、表題のようなことが起こったのでメモです。 環境 g++ (GCC) 12.1.0 問題のソースコード a.cpp↓ #include <cmath> #include <bit> #include <tuple> std::tuple<unsigned long, double, double> f(double w) { unsigned long n = std::bit_cast<unsigned long>(w) & 3; double x = st</unsigned></unsigned></tuple></bit></cmath>…

間違ったポラードのロー法の使い方

概要 アルゴ式が公開している素因数分解するアルゴリズム(と称しているもの)は、特定の入力に対して正しく動作しません(無限ループします)。 ポラードのロー法が失敗した場合、疑似乱数生成器のシードのみを変更するのではなく、疑似乱数生成器自体を変…