crit-bit 木 (その3)

crit-bit木 は Ruby で試したものですが、 本番の C 言語の落ち穂拾いをしてみます。D. J. Bernstein の qhasm の C 言語で記述したソースコードの中に含まれている crit-bit 木 の挿入手続きは次のような goto を使った箇所があります。 ここでは、 挿入し…

Chibi Scheme のゴミ集め

Chibi Scheme の組み込み手続きは C 言語の関数で記述してあり、 C 言語の auto 変数をヒープ中の Scheme のセルに束縛しています。 そのため、 ゴミ集め時に C 言語のコール・スタックを調べる必要が生じ、 3 つの方式を処理系のビルド時に選べるようになっ…

巨大整数のビット論理演算

2の補数を求めることができるようにしたので、ビット論理演算も追加することにします。SRFI-60 や Ruby がそうであるように、巨大整数の内部表現がどのようなものであっても、ビット論理演算時は 2 の補数表現で、負の数は無限に 1 の符号ビットが続いている…

巨大整数のシフト演算

巨大整数の算術シフト arithmetic-shift を実装します。SRFI-60 (Scheme requests for implementation) にしたがって、シフト量が正のときは左シフト、負のときは右シフトします。巨大整数の符号にかかわらず左シフトは 2 のべき乗との乗算、右シフトは 2 の…

巨大整数の10進基数変換

符号なし巨大整数の低レベル関数を使って符号付き整数を作った上で、10進数文字列から巨大整数に変換する手続きと、巨大整数を 10 進数で表示する手続きをカラツバ系列の基数変換法で書いてみました。符号付き整数は符号部と符号なし整数部の配列をまとめた…

Burnikel と Ziegler による再帰除算 (4)

簡便にできる最適化をいくつかおこなっておきます。まず、Burnikel 等の論文には桁が少ないときでも、再帰除算はスクールブック除算と遜色ない速度で演算できると記載されていますが、自分の環境でそうなるのは gcc の最適化抑制オプション -fno-inline を追…

Burnikel と Ziegler による再帰除算 (3)

再帰除算を動作させるには低レベルの符号なし多桁整数のシフト・加減演算が必要です。さらに、速度比較にスクールブック除算も必要になります。桁ベクトルのコピーと数値埋めの手続きがあります。コピーは異なる桁ベクトル間のコピーに使い、同じ桁ベクトル…

Burnikel と Ziegler による再帰除算 (2)

再帰除算を C99 言語で書いてみます。Ruby のコードを読むとわかるように、再帰除算を記述するには符号なし巨大整数の加減乗とバイナリの場合は左右シフトが必要です。それらもあわせて実装していきます。符号なし巨大整数演算は、符号付きの巨大整数演算の…

64ビット被除数を32ビット除数で割り算

スクールブック除算では、64ビットから32ビットを割るのに uint64_t を使って 64 ビット除算をおこないました。ところで、64 ビットプロセッサで bigint の各桁に uint64_t を使うことにしたときは、128 ビットから 64 ビットを割らなければならず、GNU C 独…

32ビットと32ビットをかけて64ビットを得る乗算

64 ビットから 32 ビットを割る除算で最初に使っていた、32 ビットと 32 ビットをかける乗算です。除算を 16 ビットに 16 ビットをかける方式に差し替えたため、エントリを別に分けておきます。この乗算は 16 ビット 2 桁同士を 32 ビット乗算を使ってかけて…

スクールブック除算による符号なしバイナリ多倍長精度整数除算

Plan9 libmp の符号なし多倍長精度整数除算は、32 ビットや 64 ビットのバイナリ符号なし整数列同士の除算をおこなっています。Knuth The Art of Computer Programming Vol. 2 (1998) の除算アルゴリズム D (スクールブック除算) にしたがっており、正規化、…

符号なし 256 ビット整数の被除数左ビットシフト除算

C言語で記述されたビットシフト筆算法の除算のコードの大半は、除数を右シフトして被除数から引き算していく書き方になっているようです。例えば、古い GNU C のランタイムの整数除算などがそうなっています。これは筆算のやりかたをそのまま手順化してある…

Plan9 libmp のカラツバ乗算

Plan9 libmp はカラツバ乗算を利用しています。どのように途中結果を求めたり一時領域に保存するのか、オープンソース版のソースを読んで調べてみました。⇒ https://github.com/brho/plan9/blob/master/sys/src/libmp/port/mpmul.cPlan9 libmp の多倍長整数…

符号なし加算の桁あふれと符号なし減算の桁借り

C 言語のほとんどの実装は、符号なし整数を剰余項として扱うだけで、桁あふれの発生を通知する機構を持つ数値型を提供していません。剰余項の加算の桁あふれは範囲チェックをすり抜ける原因になり、桁あふれを無視したことがセキュリティ・ホールになった事…

Ephemeron - ハッシュ表とコピー・コレクタによる実装

揮発性 key-value マップである「Ephemeron Table」をハッシュ表とコピー・コレクタで書いたので、要点を備忘録として残しておきます。ハッシュ表にオープン・アドレス法を、コピー・コレクタに Cheney 法を採用しています。オープン・アドレス法にしたのは…

3 色マークでリスト出力の write と write-shared の区別化

R7RS Scheme では write は循環参照だけをラベル付けで出力し、write-shared は循環参照であろうがなかろうがすべての共用されているセルをラベル付けで出力するものとして、区別しています。一方、「遅延スイープでストップ&コピーの待機領域をマークに使…

遅延スイープでストップ&コピーの待機領域をマークに使用してリスト出力を改良

昨日の「ストップ&コピーの待機領域をマークに使用してリスト出力」は、リスト出力するごとに待機領域のセル先頭に対応する全スロットをゼロクリアするという富豪的プログラミングをしていました。これではあんまりに無駄なことをしているため、ゼロクリア…

ストップ&コピーの待機領域をマークに使用してリスト出力

CEK ベースの仮想マシンにライタを追加することにします。この仮想マシンではセルの破壊走査を許しているため、循環参照を作ることができます。そのため、リスト出力で循環参照を辿ってしまって無限ループに入り込まないようにすることにします。⇒ 遅延スイ…

pack/unpack

C 言語でリトル・エンディアンとビッグ・エンディアンの両方を扱うコードを書いていて、いい加減、めんどくさく感じ始めたので、Perl 言語の pack/unpack のように、nNvV テンプレートで一発変換できるようにしてみました。C 言語で pack/unpack を使う元ネ…