ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか [プログラミング]
すっごく細かい話を、すっごくわかりにくいテクニックで解くプログラミングの本。
どう使っていいのかもはやよくわからないが、
「へえー」っとなるプログラミングを集めたもの。
半分は数学みたいだった。
１序論
表記の法則が書かれていた。
Cの式評価優先順位とコンピュータ代数、その説明の一覧がついていた。
命令セットと実行時間モデルは、汎用RISCコンピュータの命令セットに似た命令セット備えたマシン用と考える。
基本RISC命令セット、Opcode簡略表記、オペランド、説明の一覧
同様の表記で「完全RISC」で追加される命令
実行時間は城山、除算、剰余意外のすべての命令は1サイクルで実行されると仮定し、乗算等には特別な時間を仮定しない。
分岐命令は分岐するにせよ、しないにせよ、１サイクルかかるとする。
２基本操作として
・右端のビット操作いろいろ、x&(x-1)だと1ワードで最右の1のビットをオフにするなど、いろいろな方法が示されている。
・論理演算と組み合わせた加算、-x=¬x+1とか
・論理式と算術式での不等式、符号なし整数と解釈される値を持つ２進論理式の不等式の例
・絶対値整数、マシンに命令がないなら、３つまたは４つの命令で分岐不要で行える。
・符号の拡張、１ワードの中にあるビット位置を符号ビットと考えて、それが、その他のビットの存在は無視して左に伝播すること。
・符号なしあkら符号付右シフトをつくる方法、マシンにsift right signed命令が無い場合。
・符号(sign)関数、ほとんどのマシンで４命令
・三つの値を持つ比較関数、sighnを少し一般化したもの。
・符号の移送、FortoranでISIGNとされるもの、ほとんどのマシンで４命令
・Zero Means 2**nフィールドのでコード、０または負の値が数量として何の意味も持たない場合、０の値を持つｎびっとフィールドを２＾Nとみなして０以外の値は通常の２進数としてエンコードする。
・比較述語、二つの量を比較する関数、比較が真なら１、偽なら０の単一ビットを生成。評価結果をふごういちにいれる分岐不要の式の例
・オーバーフローの検出、算術結果をターゲットレジスタで正確に表すには大きすぎるかまたは小さすぎることをいう。発生したときに状況ビットを使用することなくプログラマが検出するのに利用できる方法を検討
・add subtract multiplyの状況コードの結果、マシンの多くが状況コードを提供している。
・循環シフト、０-３２の値域のｎについてシフトがmod32の場合でもなりたつ。
・2倍長のadd/subtract、符号なしの加算と原産のオーバーフローの式の一つを使い、マシンのキャリービットにアクセスすることなく、2倍長の加算と減算を容易に実装する方法。
・2倍長のシフト、32ビットワードの対と考える
・他バイトのadd subtract 絶対値、1ワードで操作するとたいていはもっと早く実行できる。
・doz(difference or zero) max min doｚでは多く引きすぎると結果が０になる。これをminとmaxの実装に使える。
・レジスタ交換、二つのレジスタの内容を3番目のレジスタを使わずに交換する方法
・二つ以上の値の交換、変数ｘは二つの値a,bだけを持つことができ、現在の値でないもう一方の値をｘに代入したいが、コードがa、bの値から独立したい場合のコード
３ ２のべき乗の境界
・符号なし整数を次に小さい8の倍数へ切り上げる、切り下げる。符号付整数で行う。符号付整数を０の方向に向かってもっとも近い８の倍数に丸めるなど。
・もっとも近い整数の代わりにもっとも近い２の整数乗に向かって丸める、floorやdeilingに似た関数を定義。
・2のべき乗の境界越えの検出。記憶域がアドレス０から2のべき乗のサイズのブロックに分割されているとして、境界越えを検出。
４ 算術的な境界
・整数の境界の検査。整数ｘが富津の境界aとbの間にあることの検証。符号なし、符号付で検証。
・加算や減算による境界の伝播。最適化コンパイラが行う式の「範囲解析」。
・論理演算による境界の伝播。上と同じ変数の境界が与えられているとして符号なしで検証。符号付は途中まで。
５ ビットの数え上げ
・１のビットの数え上げ。IBM Stretchではワード中の1ビットや０ビットの個数を数えられた。この命令がないマシンでは2ビットごとに区切った各フィールドにもともとそこにあった二つのビットの和をセットし、その次に隣接する2ビットのフィールドの和を求め、その結果を4ビットの各フィールドにセットするを繰り返す。→分割統治という戦略。1ビットが少ないワード、配列の方法も解説。
・パリティ。ワードのパリティ計算。7ビット量にパリティビットを付加する。
・先頭から続く０を数える。二分木探索を用いて先頭から続く０を数える方法。右に伝播させる方法など。
・末尾へ続く０を数える。上と同じ問題に転換してしまうとよい。
６ ワードの探索
・最初の０バイトの検出。Cのストリング表現は明示的な長さを持たない。末尾は０。長さを知る関数strlenの高速版をつくるには、ワード境界まで1バイトづつロードして検査、境界に達したらワード単位でレジスタにロードし、その中に０倍とが含まれているか調べる。単純な検査、分岐不要コード、nlzを用いない最左の０バイト検出、多項式の評価による最左の０バイト検出方法など。
・指定された長さを持つ最初の１のビット列の検出。shifとandを用いた例
７ ビットやバイト単位の並べ替え
・ビットやバイトの逆転、リトルエンディアンとビッグエンディアン形式でのデータ交換操作に必須。
・ビットのシャッフル。暗号化に応用できる。外側完全シャッフル演算など解説。
・ビット行列の転置。行と列の転換。8×8行列、32×32行列の転置例解説。
・圧縮あるいは一般化された抽出。extract命令への類推からそう呼ばれる。APL言語のcompress演算と同じ。
・一般的順列あるいは「羊と山羊」演算。順列を表現する方法を検討。
・並べ替えと添え字変換。配列の要素数がコンピュータのワードかそれ以上の場合に有益。
８ 乗算
・多倍長乗算。筆算の方法でおこなうより、部分関野配列を展開するより、それぞれの新しい行を計算しながら積になる行に加えていくほうが効果的。
・64ビット積の上位32ビット。32ビット整数の積の上位32ビットを計算する問題を考える。
・積の上位半分の符号付と符号なしの間の変換。
・定数の乗算。sift、left, addの連続で定数の乗算が行える。
９ 整数除算
・この章と次の章でコンピュータの除算に関する秘訣とアルゴリズムを与える。式の定義、使う定理について定義。
・多倍長除算。伝統的筆算の方法でできるが複雑。クヌースのアルゴリズムＤｗｏＣでコーディングしたものの例。
・符号付の除算から符号なしのshort除算へ。shoｒｔ除算は1ワード同士の除算。符号付のlong除算を使う方法。符号付のshort除算を使う方法。
・符号なしのlong除算。long除算はダブルワードを単独のワードで割る除算を表すことにする。０で割った場合を含むオーバーフローの結果は不定。ハードウェアのshift-and-subtractアルゴリズムを使う方法、short除算を使う方法解説。
１０ 整数定数による除算
多くのコンピュータで除算は非常に時間がかかるので可能なら避けるべき。除数が定数のときdivide命令をさける方法。
・2のべき乗による符号付除算、shirf right asigned をｋビット行うと、数値を２のｋ乗で割れると仮定するのは過ち。
・2のべき乗による除算の符号付剰余。計算方法解説。
・2のべき乗以外での符号付除算と剰余。基本となる秘訣は、およそ２の32乗/ｄであるような、除数ｄの逆数の1種をかけて、咳の左32ビットを取り出す。もうすこし複雑なので例（３、７の除算）で解説。
・除数が2以上の符号付除算。上の例のなかで３つの例があるだけとして、説明。
・除数が-2以下の符号付除算。いったん他の例におきかえて商をマイナスにする方法を解説。
・コンパイラへの組み込み。コンパイラが定数による除算を乗算にかえる方法解説。
・その他の話題。他の定理の証明など。
・符号なし除算。2のべき乗による符号なし除算は、単一のshift right logical命令で実装でき、剰余はand immediateで命令できる。３、７の例。
・除数が1以上の符号なし除算解説。
・コンパイラへの組み込み。（符号なし）ここでの証明で使った式は実行に困難。キーポイントを解説。
・その他の話題（符号なし）。符号なしの場合のその他の定理について解説。
・modulusおよびfloor除算への応用、非定数が負なら１加えるステップを省略する方法ではうまくいかない。
・類似した方法、magicアルゴリズムをコーディングする代わりに、いくつかの小さい除数についてマジックナンバーとシフト量を与える表を用意する方法。
・マジックナンバーのサンプル、W＝32とW=64の表。
・定数による整除算。整除算＝事前に何らかの方法で剰余が０とわかっている除算。定理で解説。ユークリッドのアルゴリズムによる乗法の逆元の計算、ニュートン法による乗法の逆元の計算を使用して解説。
・定数による除算後に剰余が０か調べる。除数ｄの乗法の逆元を使う。
１１ いくつかの初等関数
・整数平方根。符号なし。ニュートン法による解説。初期近似値を二分探索。ハードウェアのアルゴリズム解説。
・整数立方根。ニュートン法はあまり効果なし。ハードウェアのアルゴリズム解説。
・整数乗。ｎの2進数分解法によるｘのｎ乗の計算。
・整数対数。logの計算。底２と１０の例。単純なテーブル検索、１０の繰り返し乗算。修正版二分探索。底２の対数から底10の整数対数への変換（２つのテーブル検索などいろんな方法で）
１２ 数の表現のための一風変わった基数
実用的でhあないが、面白い数の位取りの表現についての議論。
・-2進数。明示的な符号や、その他の最上位ビットに負の重みをもたせるような不規則なものを用いることなしに、不でもせいでも整数を表すことができる。
・-1+i進数。すべての複素整数を明示的な符号やその他の変則的なことなしに、一つの数として表すことができる。
・その他の基数について解説。
・どれか最も効率的な基数か？ここの計算では2進表現はe進表現より焼く1.0632倍コスト高としていた。
１３ グレイコード
・グレイコード・・・ｎビットから成る数を一度に１ビット変えていくだけで２のｎ乗すべての組み合わせを循環的に表す。これがグレイコードの性質。グレイコード化された整数とその次の整数とで1ビットだけが異なるコード化の方法。
この概念は10進数などの任意の基数に対して応用できるように一般化可能。ここでは、2進数のグレイコードについてのみ議論。
その中でも反射2進グレイコードについてのみ議論。
・グレイコード化された整数のインクリメント
・-2進のグレイコード
・簡単な歴史と応用。ベル研究所のフランク・グレイにちなんで命名された、位置センサーに使われている。
１４ ヒルベルト曲線
ペアノは平面曲線で「平面空間を充填する（うめつくす）」という、驚くべき特性を有するものを発見。これは基数３の小数を使って証明できる。
ヒルベルトはペアノ曲線の一つの変種を発見。正方形の各々の辺を2等分し、もとの正方形を４つの小さな正方形に分割。そしてそれがさらにちいさな４つの正方形に分割と続く。その分割の各々の段階で正方形をたどる曲線を与える、これがペアノーヒルベルト曲線。ヒルベルト曲線は分割処理の極限の曲線。ヒルベルト曲線は基数２の小数、つまり2進小数で説明できる。
ここでは次数ｎのヒルベルト曲線をその曲線列のうちのｎ番目の曲線と意味して使う。
・ヒルベルト曲線を生成する再帰的アルゴリズムを考える。
・ヒルベルト曲線の道のりから座標を求める方法解説。
・ヒルベルト曲線上の座標の距離を求める方法解説。
・ヒルベルト曲線の座標のインクリメント方法解説。
・非再帰型の生成アルゴリズム
・その他の空間充填曲線解説。
・応用。空間充填曲線は圧縮やハーフトーン化、テクスチャ解析といった画像処理へ応用できる。
１５ 浮動小数点
整数演算と論理演算を使った浮動小数点数値の操作の提案はIEEE算術としてしられているが美しくない。
・IEEE規格の解説。単精度と倍精度形式に限定して。
・整数演算を用いた浮動小数点数値の比較。非数でない数値ではそれを符号と大きさを持った整数とみなしたとき正しく順序づけられる。
・先頭桁の分布。なんか先頭桁が１の割合について考えているようだ、指数フィールドを大きくとりすぎるとかなんとか。
・種々の数値一覧。正確でない値は表現可能なもっとも近い数に丸められている。ー極大とか。
１６ 素数に関する式
・素数に関する式の歴史からハイライトを復習。フェルマとか。
・ウィランズの式、ｎ番目の素数を求める。
・ウォーメルの式、ウィランズの式を改良して三角関数とfloor関数を取り除いた。原理的には整数演算だけを使う簡単なコンピュータプログラムで計算可能。
・その他の面倒な関数を表す式。
付録A ４ビットマシンのための算術表
加算、減算（行一列）、符号付乗算、符号なし乗算、符号付short除算（行÷列）、符号なしshort除算（行÷列）、符号付short除算の剰余（行÷列）、符号なしshort除算の剰余（行÷列）
付録B ニュートン法
手短な解説。
どう使っていいのかもはやよくわからないが、
「へえー」っとなるプログラミングを集めたもの。
半分は数学みたいだった。
１序論
表記の法則が書かれていた。
Cの式評価優先順位とコンピュータ代数、その説明の一覧がついていた。
命令セットと実行時間モデルは、汎用RISCコンピュータの命令セットに似た命令セット備えたマシン用と考える。
基本RISC命令セット、Opcode簡略表記、オペランド、説明の一覧
同様の表記で「完全RISC」で追加される命令
実行時間は城山、除算、剰余意外のすべての命令は1サイクルで実行されると仮定し、乗算等には特別な時間を仮定しない。
分岐命令は分岐するにせよ、しないにせよ、１サイクルかかるとする。
２基本操作として
・右端のビット操作いろいろ、x&(x-1)だと1ワードで最右の1のビットをオフにするなど、いろいろな方法が示されている。
・論理演算と組み合わせた加算、-x=¬x+1とか
・論理式と算術式での不等式、符号なし整数と解釈される値を持つ２進論理式の不等式の例
・絶対値整数、マシンに命令がないなら、３つまたは４つの命令で分岐不要で行える。
・符号の拡張、１ワードの中にあるビット位置を符号ビットと考えて、それが、その他のビットの存在は無視して左に伝播すること。
・符号なしあkら符号付右シフトをつくる方法、マシンにsift right signed命令が無い場合。
・符号(sign)関数、ほとんどのマシンで４命令
・三つの値を持つ比較関数、sighnを少し一般化したもの。
・符号の移送、FortoranでISIGNとされるもの、ほとんどのマシンで４命令
・Zero Means 2**nフィールドのでコード、０または負の値が数量として何の意味も持たない場合、０の値を持つｎびっとフィールドを２＾Nとみなして０以外の値は通常の２進数としてエンコードする。
・比較述語、二つの量を比較する関数、比較が真なら１、偽なら０の単一ビットを生成。評価結果をふごういちにいれる分岐不要の式の例
・オーバーフローの検出、算術結果をターゲットレジスタで正確に表すには大きすぎるかまたは小さすぎることをいう。発生したときに状況ビットを使用することなくプログラマが検出するのに利用できる方法を検討
・add subtract multiplyの状況コードの結果、マシンの多くが状況コードを提供している。
・循環シフト、０-３２の値域のｎについてシフトがmod32の場合でもなりたつ。
・2倍長のadd/subtract、符号なしの加算と原産のオーバーフローの式の一つを使い、マシンのキャリービットにアクセスすることなく、2倍長の加算と減算を容易に実装する方法。
・2倍長のシフト、32ビットワードの対と考える
・他バイトのadd subtract 絶対値、1ワードで操作するとたいていはもっと早く実行できる。
・doz(difference or zero) max min doｚでは多く引きすぎると結果が０になる。これをminとmaxの実装に使える。
・レジスタ交換、二つのレジスタの内容を3番目のレジスタを使わずに交換する方法
・二つ以上の値の交換、変数ｘは二つの値a,bだけを持つことができ、現在の値でないもう一方の値をｘに代入したいが、コードがa、bの値から独立したい場合のコード
３ ２のべき乗の境界
・符号なし整数を次に小さい8の倍数へ切り上げる、切り下げる。符号付整数で行う。符号付整数を０の方向に向かってもっとも近い８の倍数に丸めるなど。
・もっとも近い整数の代わりにもっとも近い２の整数乗に向かって丸める、floorやdeilingに似た関数を定義。
・2のべき乗の境界越えの検出。記憶域がアドレス０から2のべき乗のサイズのブロックに分割されているとして、境界越えを検出。
４ 算術的な境界
・整数の境界の検査。整数ｘが富津の境界aとbの間にあることの検証。符号なし、符号付で検証。
・加算や減算による境界の伝播。最適化コンパイラが行う式の「範囲解析」。
・論理演算による境界の伝播。上と同じ変数の境界が与えられているとして符号なしで検証。符号付は途中まで。
５ ビットの数え上げ
・１のビットの数え上げ。IBM Stretchではワード中の1ビットや０ビットの個数を数えられた。この命令がないマシンでは2ビットごとに区切った各フィールドにもともとそこにあった二つのビットの和をセットし、その次に隣接する2ビットのフィールドの和を求め、その結果を4ビットの各フィールドにセットするを繰り返す。→分割統治という戦略。1ビットが少ないワード、配列の方法も解説。
・パリティ。ワードのパリティ計算。7ビット量にパリティビットを付加する。
・先頭から続く０を数える。二分木探索を用いて先頭から続く０を数える方法。右に伝播させる方法など。
・末尾へ続く０を数える。上と同じ問題に転換してしまうとよい。
６ ワードの探索
・最初の０バイトの検出。Cのストリング表現は明示的な長さを持たない。末尾は０。長さを知る関数strlenの高速版をつくるには、ワード境界まで1バイトづつロードして検査、境界に達したらワード単位でレジスタにロードし、その中に０倍とが含まれているか調べる。単純な検査、分岐不要コード、nlzを用いない最左の０バイト検出、多項式の評価による最左の０バイト検出方法など。
・指定された長さを持つ最初の１のビット列の検出。shifとandを用いた例
７ ビットやバイト単位の並べ替え
・ビットやバイトの逆転、リトルエンディアンとビッグエンディアン形式でのデータ交換操作に必須。
・ビットのシャッフル。暗号化に応用できる。外側完全シャッフル演算など解説。
・ビット行列の転置。行と列の転換。8×8行列、32×32行列の転置例解説。
・圧縮あるいは一般化された抽出。extract命令への類推からそう呼ばれる。APL言語のcompress演算と同じ。
・一般的順列あるいは「羊と山羊」演算。順列を表現する方法を検討。
・並べ替えと添え字変換。配列の要素数がコンピュータのワードかそれ以上の場合に有益。
８ 乗算
・多倍長乗算。筆算の方法でおこなうより、部分関野配列を展開するより、それぞれの新しい行を計算しながら積になる行に加えていくほうが効果的。
・64ビット積の上位32ビット。32ビット整数の積の上位32ビットを計算する問題を考える。
・積の上位半分の符号付と符号なしの間の変換。
・定数の乗算。sift、left, addの連続で定数の乗算が行える。
９ 整数除算
・この章と次の章でコンピュータの除算に関する秘訣とアルゴリズムを与える。式の定義、使う定理について定義。
・多倍長除算。伝統的筆算の方法でできるが複雑。クヌースのアルゴリズムＤｗｏＣでコーディングしたものの例。
・符号付の除算から符号なしのshort除算へ。shoｒｔ除算は1ワード同士の除算。符号付のlong除算を使う方法。符号付のshort除算を使う方法。
・符号なしのlong除算。long除算はダブルワードを単独のワードで割る除算を表すことにする。０で割った場合を含むオーバーフローの結果は不定。ハードウェアのshift-and-subtractアルゴリズムを使う方法、short除算を使う方法解説。
１０ 整数定数による除算
多くのコンピュータで除算は非常に時間がかかるので可能なら避けるべき。除数が定数のときdivide命令をさける方法。
・2のべき乗による符号付除算、shirf right asigned をｋビット行うと、数値を２のｋ乗で割れると仮定するのは過ち。
・2のべき乗による除算の符号付剰余。計算方法解説。
・2のべき乗以外での符号付除算と剰余。基本となる秘訣は、およそ２の32乗/ｄであるような、除数ｄの逆数の1種をかけて、咳の左32ビットを取り出す。もうすこし複雑なので例（３、７の除算）で解説。
・除数が2以上の符号付除算。上の例のなかで３つの例があるだけとして、説明。
・除数が-2以下の符号付除算。いったん他の例におきかえて商をマイナスにする方法を解説。
・コンパイラへの組み込み。コンパイラが定数による除算を乗算にかえる方法解説。
・その他の話題。他の定理の証明など。
・符号なし除算。2のべき乗による符号なし除算は、単一のshift right logical命令で実装でき、剰余はand immediateで命令できる。３、７の例。
・除数が1以上の符号なし除算解説。
・コンパイラへの組み込み。（符号なし）ここでの証明で使った式は実行に困難。キーポイントを解説。
・その他の話題（符号なし）。符号なしの場合のその他の定理について解説。
・modulusおよびfloor除算への応用、非定数が負なら１加えるステップを省略する方法ではうまくいかない。
・類似した方法、magicアルゴリズムをコーディングする代わりに、いくつかの小さい除数についてマジックナンバーとシフト量を与える表を用意する方法。
・マジックナンバーのサンプル、W＝32とW=64の表。
・定数による整除算。整除算＝事前に何らかの方法で剰余が０とわかっている除算。定理で解説。ユークリッドのアルゴリズムによる乗法の逆元の計算、ニュートン法による乗法の逆元の計算を使用して解説。
・定数による除算後に剰余が０か調べる。除数ｄの乗法の逆元を使う。
１１ いくつかの初等関数
・整数平方根。符号なし。ニュートン法による解説。初期近似値を二分探索。ハードウェアのアルゴリズム解説。
・整数立方根。ニュートン法はあまり効果なし。ハードウェアのアルゴリズム解説。
・整数乗。ｎの2進数分解法によるｘのｎ乗の計算。
・整数対数。logの計算。底２と１０の例。単純なテーブル検索、１０の繰り返し乗算。修正版二分探索。底２の対数から底10の整数対数への変換（２つのテーブル検索などいろんな方法で）
１２ 数の表現のための一風変わった基数
実用的でhあないが、面白い数の位取りの表現についての議論。
・-2進数。明示的な符号や、その他の最上位ビットに負の重みをもたせるような不規則なものを用いることなしに、不でもせいでも整数を表すことができる。
・-1+i進数。すべての複素整数を明示的な符号やその他の変則的なことなしに、一つの数として表すことができる。
・その他の基数について解説。
・どれか最も効率的な基数か？ここの計算では2進表現はe進表現より焼く1.0632倍コスト高としていた。
１３ グレイコード
・グレイコード・・・ｎビットから成る数を一度に１ビット変えていくだけで２のｎ乗すべての組み合わせを循環的に表す。これがグレイコードの性質。グレイコード化された整数とその次の整数とで1ビットだけが異なるコード化の方法。
この概念は10進数などの任意の基数に対して応用できるように一般化可能。ここでは、2進数のグレイコードについてのみ議論。
その中でも反射2進グレイコードについてのみ議論。
・グレイコード化された整数のインクリメント
・-2進のグレイコード
・簡単な歴史と応用。ベル研究所のフランク・グレイにちなんで命名された、位置センサーに使われている。
１４ ヒルベルト曲線
ペアノは平面曲線で「平面空間を充填する（うめつくす）」という、驚くべき特性を有するものを発見。これは基数３の小数を使って証明できる。
ヒルベルトはペアノ曲線の一つの変種を発見。正方形の各々の辺を2等分し、もとの正方形を４つの小さな正方形に分割。そしてそれがさらにちいさな４つの正方形に分割と続く。その分割の各々の段階で正方形をたどる曲線を与える、これがペアノーヒルベルト曲線。ヒルベルト曲線は分割処理の極限の曲線。ヒルベルト曲線は基数２の小数、つまり2進小数で説明できる。
ここでは次数ｎのヒルベルト曲線をその曲線列のうちのｎ番目の曲線と意味して使う。
・ヒルベルト曲線を生成する再帰的アルゴリズムを考える。
・ヒルベルト曲線の道のりから座標を求める方法解説。
・ヒルベルト曲線上の座標の距離を求める方法解説。
・ヒルベルト曲線の座標のインクリメント方法解説。
・非再帰型の生成アルゴリズム
・その他の空間充填曲線解説。
・応用。空間充填曲線は圧縮やハーフトーン化、テクスチャ解析といった画像処理へ応用できる。
１５ 浮動小数点
整数演算と論理演算を使った浮動小数点数値の操作の提案はIEEE算術としてしられているが美しくない。
・IEEE規格の解説。単精度と倍精度形式に限定して。
・整数演算を用いた浮動小数点数値の比較。非数でない数値ではそれを符号と大きさを持った整数とみなしたとき正しく順序づけられる。
・先頭桁の分布。なんか先頭桁が１の割合について考えているようだ、指数フィールドを大きくとりすぎるとかなんとか。
・種々の数値一覧。正確でない値は表現可能なもっとも近い数に丸められている。ー極大とか。
１６ 素数に関する式
・素数に関する式の歴史からハイライトを復習。フェルマとか。
・ウィランズの式、ｎ番目の素数を求める。
・ウォーメルの式、ウィランズの式を改良して三角関数とfloor関数を取り除いた。原理的には整数演算だけを使う簡単なコンピュータプログラムで計算可能。
・その他の面倒な関数を表す式。
付録A ４ビットマシンのための算術表
加算、減算（行一列）、符号付乗算、符号なし乗算、符号付short除算（行÷列）、符号なしshort除算（行÷列）、符号付short除算の剰余（行÷列）、符号なしshort除算の剰余（行÷列）
付録B ニュートン法
手短な解説。
ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか
- 作者: ジュニア,ヘンリー・S. ウォーレン
- 出版社/メーカー: エスアイビーアクセス
- 発売日: 2004/09
- メディア: 単行本
コメント 0