So-net無料ブログ作成

本のベストセラー

ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか [プログラミング]

すっごく細かい話を、すっごくわかりにくいテクニックで解くプログラミングの本。

どう使っていいのかもはやよくわからないが、

「へえー」っとなるプログラミングを集めたもの。

半分は数学みたいだった。

1序論
表記の法則が書かれていた。
Cの式評価優先順位とコンピュータ代数、その説明の一覧がついていた。
命令セットと実行時間モデルは、汎用RISCコンピュータの命令セットに似た命令セット備えたマシン用と考える。
基本RISC命令セット、Opcode簡略表記、オペランド、説明の一覧
同様の表記で「完全RISC」で追加される命令
実行時間は城山、除算、剰余意外のすべての命令は1サイクルで実行されると仮定し、乗算等には特別な時間を仮定しない。
分岐命令は分岐するにせよ、しないにせよ、1サイクルかかるとする。

2基本操作として
・右端のビット操作いろいろ、x&(x-1)だと1ワードで最右の1のビットをオフにするなど、いろいろな方法が示されている。
・論理演算と組み合わせた加算、-x=¬x+1とか
・論理式と算術式での不等式、符号なし整数と解釈される値を持つ2進論理式の不等式の例
・絶対値整数、マシンに命令がないなら、3つまたは4つの命令で分岐不要で行える。
・符号の拡張、1ワードの中にあるビット位置を符号ビットと考えて、それが、その他のビットの存在は無視して左に伝播すること。
・符号なしあkら符号付右シフトをつくる方法、マシンにsift right signed命令が無い場合。
・符号(sign)関数、ほとんどのマシンで4命令
・三つの値を持つ比較関数、sighnを少し一般化したもの。
・符号の移送、FortoranでISIGNとされるもの、ほとんどのマシンで4命令
・Zero Means 2**nフィールドのでコード、0または負の値が数量として何の意味も持たない場合、0の値を持つnびっとフィールドを2^Nとみなして0以外の値は通常の2進数としてエンコードする。
・比較述語、二つの量を比較する関数、比較が真なら1、偽なら0の単一ビットを生成。評価結果をふごういちにいれる分岐不要の式の例
・オーバーフローの検出、算術結果をターゲットレジスタで正確に表すには大きすぎるかまたは小さすぎることをいう。発生したときに状況ビットを使用することなくプログラマが検出するのに利用できる方法を検討
・add subtract multiplyの状況コードの結果、マシンの多くが状況コードを提供している。
・循環シフト、0-32の値域のnについてシフトがmod32の場合でもなりたつ。
・2倍長のadd/subtract、符号なしの加算と原産のオーバーフローの式の一つを使い、マシンのキャリービットにアクセスすることなく、2倍長の加算と減算を容易に実装する方法。
・2倍長のシフト、32ビットワードの対と考える
・他バイトのadd subtract 絶対値、1ワードで操作するとたいていはもっと早く実行できる。
・doz(difference or zero) max min dozでは多く引きすぎると結果が0になる。これをminとmaxの実装に使える。
・レジスタ交換、二つのレジスタの内容を3番目のレジスタを使わずに交換する方法
・二つ以上の値の交換、変数xは二つの値a,bだけを持つことができ、現在の値でないもう一方の値をxに代入したいが、コードがa、bの値から独立したい場合のコード

3 2のべき乗の境界
・符号なし整数を次に小さい8の倍数へ切り上げる、切り下げる。符号付整数で行う。符号付整数を0の方向に向かってもっとも近い8の倍数に丸めるなど。
・もっとも近い整数の代わりにもっとも近い2の整数乗に向かって丸める、floorやdeilingに似た関数を定義。
・2のべき乗の境界越えの検出。記憶域がアドレス0から2のべき乗のサイズのブロックに分割されているとして、境界越えを検出。

4 算術的な境界
・整数の境界の検査。整数xが富津の境界aとbの間にあることの検証。符号なし、符号付で検証。
・加算や減算による境界の伝播。最適化コンパイラが行う式の「範囲解析」。
・論理演算による境界の伝播。上と同じ変数の境界が与えられているとして符号なしで検証。符号付は途中まで。

5 ビットの数え上げ
・1のビットの数え上げ。IBM Stretchではワード中の1ビットや0ビットの個数を数えられた。この命令がないマシンでは2ビットごとに区切った各フィールドにもともとそこにあった二つのビットの和をセットし、その次に隣接する2ビットのフィールドの和を求め、その結果を4ビットの各フィールドにセットするを繰り返す。→分割統治という戦略。1ビットが少ないワード、配列の方法も解説。
・パリティ。ワードのパリティ計算。7ビット量にパリティビットを付加する。
・先頭から続く0を数える。二分木探索を用いて先頭から続く0を数える方法。右に伝播させる方法など。
・末尾へ続く0を数える。上と同じ問題に転換してしまうとよい。

6 ワードの探索
・最初の0バイトの検出。Cのストリング表現は明示的な長さを持たない。末尾は0。長さを知る関数strlenの高速版をつくるには、ワード境界まで1バイトづつロードして検査、境界に達したらワード単位でレジスタにロードし、その中に0倍とが含まれているか調べる。単純な検査、分岐不要コード、nlzを用いない最左の0バイト検出、多項式の評価による最左の0バイト検出方法など。
・指定された長さを持つ最初の1のビット列の検出。shifとandを用いた例

7 ビットやバイト単位の並べ替え
・ビットやバイトの逆転、リトルエンディアンとビッグエンディアン形式でのデータ交換操作に必須。
・ビットのシャッフル。暗号化に応用できる。外側完全シャッフル演算など解説。
・ビット行列の転置。行と列の転換。8×8行列、32×32行列の転置例解説。
・圧縮あるいは一般化された抽出。extract命令への類推からそう呼ばれる。APL言語のcompress演算と同じ。
・一般的順列あるいは「羊と山羊」演算。順列を表現する方法を検討。
・並べ替えと添え字変換。配列の要素数がコンピュータのワードかそれ以上の場合に有益。

8 乗算
・多倍長乗算。筆算の方法でおこなうより、部分関野配列を展開するより、それぞれの新しい行を計算しながら積になる行に加えていくほうが効果的。
・64ビット積の上位32ビット。32ビット整数の積の上位32ビットを計算する問題を考える。
・積の上位半分の符号付と符号なしの間の変換。
・定数の乗算。sift、left, addの連続で定数の乗算が行える。

9 整数除算
・この章と次の章でコンピュータの除算に関する秘訣とアルゴリズムを与える。式の定義、使う定理について定義。
・多倍長除算。伝統的筆算の方法でできるが複雑。クヌースのアルゴリズムDwoCでコーディングしたものの例。
・符号付の除算から符号なしのshort除算へ。short除算は1ワード同士の除算。符号付のlong除算を使う方法。符号付のshort除算を使う方法。
・符号なしのlong除算。long除算はダブルワードを単独のワードで割る除算を表すことにする。0で割った場合を含むオーバーフローの結果は不定。ハードウェアのshift-and-subtractアルゴリズムを使う方法、short除算を使う方法解説。

10 整数定数による除算
多くのコンピュータで除算は非常に時間がかかるので可能なら避けるべき。除数が定数のときdivide命令をさける方法。
・2のべき乗による符号付除算、shirf right asigned をkビット行うと、数値を2のk乗で割れると仮定するのは過ち。
・2のべき乗による除算の符号付剰余。計算方法解説。
・2のべき乗以外での符号付除算と剰余。基本となる秘訣は、およそ2の32乗/dであるような、除数dの逆数の1種をかけて、咳の左32ビットを取り出す。もうすこし複雑なので例(3、7の除算)で解説。
・除数が2以上の符号付除算。上の例のなかで3つの例があるだけとして、説明。
・除数が-2以下の符号付除算。いったん他の例におきかえて商をマイナスにする方法を解説。
・コンパイラへの組み込み。コンパイラが定数による除算を乗算にかえる方法解説。
・その他の話題。他の定理の証明など。
・符号なし除算。2のべき乗による符号なし除算は、単一のshift right logical命令で実装でき、剰余はand immediateで命令できる。3、7の例。
・除数が1以上の符号なし除算解説。
・コンパイラへの組み込み。(符号なし)ここでの証明で使った式は実行に困難。キーポイントを解説。
・その他の話題(符号なし)。符号なしの場合のその他の定理について解説。
・modulusおよびfloor除算への応用、非定数が負なら1加えるステップを省略する方法ではうまくいかない。
・類似した方法、magicアルゴリズムをコーディングする代わりに、いくつかの小さい除数についてマジックナンバーとシフト量を与える表を用意する方法。
・マジックナンバーのサンプル、W=32とW=64の表。
・定数による整除算。整除算=事前に何らかの方法で剰余が0とわかっている除算。定理で解説。ユークリッドのアルゴリズムによる乗法の逆元の計算、ニュートン法による乗法の逆元の計算を使用して解説。
・定数による除算後に剰余が0か調べる。除数dの乗法の逆元を使う。

11 いくつかの初等関数
・整数平方根。符号なし。ニュートン法による解説。初期近似値を二分探索。ハードウェアのアルゴリズム解説。
・整数立方根。ニュートン法はあまり効果なし。ハードウェアのアルゴリズム解説。
・整数乗。nの2進数分解法によるxのn乗の計算。
・整数対数。logの計算。底2と10の例。単純なテーブル検索、10の繰り返し乗算。修正版二分探索。底2の対数から底10の整数対数への変換(2つのテーブル検索などいろんな方法で)

12 数の表現のための一風変わった基数
実用的でhあないが、面白い数の位取りの表現についての議論。
・-2進数。明示的な符号や、その他の最上位ビットに負の重みをもたせるような不規則なものを用いることなしに、不でもせいでも整数を表すことができる。
・-1+i進数。すべての複素整数を明示的な符号やその他の変則的なことなしに、一つの数として表すことができる。
・その他の基数について解説。
・どれか最も効率的な基数か?ここの計算では2進表現はe進表現より焼く1.0632倍コスト高としていた。

13 グレイコード
・グレイコード・・・nビットから成る数を一度に1ビット変えていくだけで2のn乗すべての組み合わせを循環的に表す。これがグレイコードの性質。グレイコード化された整数とその次の整数とで1ビットだけが異なるコード化の方法。
この概念は10進数などの任意の基数に対して応用できるように一般化可能。ここでは、2進数のグレイコードについてのみ議論。
その中でも反射2進グレイコードについてのみ議論。
・グレイコード化された整数のインクリメント
・-2進のグレイコード
・簡単な歴史と応用。ベル研究所のフランク・グレイにちなんで命名された、位置センサーに使われている。

14 ヒルベルト曲線
ペアノは平面曲線で「平面空間を充填する(うめつくす)」という、驚くべき特性を有するものを発見。これは基数3の小数を使って証明できる。
ヒルベルトはペアノ曲線の一つの変種を発見。正方形の各々の辺を2等分し、もとの正方形を4つの小さな正方形に分割。そしてそれがさらにちいさな4つの正方形に分割と続く。その分割の各々の段階で正方形をたどる曲線を与える、これがペアノーヒルベルト曲線。ヒルベルト曲線は分割処理の極限の曲線。ヒルベルト曲線は基数2の小数、つまり2進小数で説明できる。
ここでは次数nのヒルベルト曲線をその曲線列のうちのn番目の曲線と意味して使う。
・ヒルベルト曲線を生成する再帰的アルゴリズムを考える。
・ヒルベルト曲線の道のりから座標を求める方法解説。
・ヒルベルト曲線上の座標の距離を求める方法解説。
・ヒルベルト曲線の座標のインクリメント方法解説。
・非再帰型の生成アルゴリズム
・その他の空間充填曲線解説。
・応用。空間充填曲線は圧縮やハーフトーン化、テクスチャ解析といった画像処理へ応用できる。

15 浮動小数点
整数演算と論理演算を使った浮動小数点数値の操作の提案はIEEE算術としてしられているが美しくない。
・IEEE規格の解説。単精度と倍精度形式に限定して。
・整数演算を用いた浮動小数点数値の比較。非数でない数値ではそれを符号と大きさを持った整数とみなしたとき正しく順序づけられる。
・先頭桁の分布。なんか先頭桁が1の割合について考えているようだ、指数フィールドを大きくとりすぎるとかなんとか。
・種々の数値一覧。正確でない値は表現可能なもっとも近い数に丸められている。ー極大とか。

16 素数に関する式
・素数に関する式の歴史からハイライトを復習。フェルマとか。
・ウィランズの式、n番目の素数を求める。
・ウォーメルの式、ウィランズの式を改良して三角関数とfloor関数を取り除いた。原理的には整数演算だけを使う簡単なコンピュータプログラムで計算可能。
・その他の面倒な関数を表す式。

付録A 4ビットマシンのための算術表
加算、減算(行一列)、符号付乗算、符号なし乗算、符号付short除算(行÷列)、符号なしshort除算(行÷列)、符号付short除算の剰余(行÷列)、符号なしshort除算の剰余(行÷列)

付録B ニュートン法
手短な解説。


ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか

ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか

  • 作者: ジュニア,ヘンリー・S. ウォーレン
  • 出版社/メーカー: エスアイビーアクセス
  • 発売日: 2004/09
  • メディア: 単行本




nice!(1)  コメント(0)  トラックバック(0) 
共通テーマ:

nice! 1

コメント 0

コメントを書く

お名前:
URL:
コメント:
画像認証:
下の画像に表示されている文字を入力してください。

※ブログオーナーが承認したコメントのみ表示されます。

トラックバック 0


この広告は前回の更新から一定期間経過したブログに表示されています。更新すると自動で解除されます。