初心者の為の線形代数勉強会（1）

はじめに

初心者のための線形代数勉強会(2) - connpassに参加してきました。
次の本を教科書として、線形代数を学んでいこうという内容の会になります。

Amazon.co.jp： 線形代数学講義 改訂版: 対馬 龍司: 本

機械学習や画像処理、量子力学をはじめとして、なんらかを真面目に取り組もうとすると当然のように出てくるのがこの線形代数ですね。自分は不真面目な学生だったので、当時にちゃんと修めてなかった為、今になってよく見かけるそれらを理解する事が出来ませんでした。
正直なところ、今更やるのは遅きに失しているんじゃないかとも思いますが、きっと今やらなかったら5年、10年後にまた、あのときやっておけば・・・と思うのが必至なので今からでもやります。

「やればわかる。やらなければ一生わからん！」ってやつですね。

さて、今回既に第2回ですが、第1回は線形代数本編というよりもその準備として、集合、複素数、ベクトルといった辺りをおさらいした回でした。今回は第2章の行列からスタートしました。

基本的には教科書通りに進んでいるので、そちらを読めば問題ないです。ですが、会の中で気になった点や教科書に書いてなかったけど述べられた点などについてちょっとメモっておこうかと。
なお、本記事の内容は「自分が現時点でこの様に理解した」という事なので、厳密に正しいかといったことの保証は一切ありません。

第2章 行列

まずは行列の話です。数学Cをちゃんと高校でやった人は復習になると思います。自分は高校では教わりませんでしたが･･･。

2.1 2次のベクトルと行列

序盤は定義について述べてるだけなので、特に問題なし。2.1.2節、線形変換から見てみます。まずは初っぱなにこんな風な説明があります。

直行座標の与えられた平面を\( {R}^2 \)で表す。\( {R}^2 \)から \( {R}^2 \)自身への写像\(f:{R}^2 \to {R}^2 \)で定数項を含まない1次式で表されるものを\({R}^2\)の線形変換という。

いきなりこれだけ言われたら、何なの？って感じになりますね。その気持ちを堪えて続きを見てみると

\begin{align*} f \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} ax + by \\ cx + dy \end{pmatrix} \end{align*}

「線形変換」とは、この様に表される写像のことである。と述べられています。つまり、左辺の\(x\)と\(y\)の列ベクトルを線形変換した結果が右辺の\(ax+by\)と\(cx+dy\)の列ベクトルということですね。積の定義より、計算結果が右辺となるような行列の積は

\begin{align*} \begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} \end{align*}

ですね。並べて書くと

\begin{align*} f \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} ax + by \\ cx + dy \end{pmatrix} = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} \end{align*}

つまり

\begin{align*} f = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \end{align*}

です。さて、第1章で集合論をやったときにこんな図が出てきたと思います。

集合\(X\)から写像\(f\)を通じて、集合\(Y\)上へ像を作ってる図ですね。今回、線形変換を施すにあたって使用している、\(f\)と等しい\(a,b,c,d\)による行列は、この様に集合で論じられていた写像の具体的な実装の一例となっています。
他の分野をかじっているとき、「この行列を演算子として見る」といった様な事をしばしば聞いていたんですが、今まで全くイメージが湧いていませんでした。この線形変換のように、行列を写像として扱うこともできるからそのような表現をされていたという事で、やっと腑に落ちました。

例 2.1.6

例として、次のような図が提示されています

先のことを踏まえてこの例を見てみると、行列の積によって関数合成が成り立っている事を確かめられます。\(h(\mathbf x)\)は

\begin{eqnarray} h(\mathbf x) = f(g(\mathbf x))\\ = f \circ g(\mathbf x) \end{eqnarray}

と表せ、各写像に対応する行列を\(F, G, H\)とすると

\begin{align*} F = \begin{pmatrix} 1 & 0 \\ 0 & -1\end{pmatrix}, G = \begin{pmatrix} -1 & 0 \\ 0 & 1\end{pmatrix}, H = \begin{pmatrix} -1 & 0 \\ 0 & -1\end{pmatrix} \end{align*}

としてこの例では指定されているので、先の関数合成より

\begin{align*} f \circ g(\mathbf x) = FG\mathbf x = \begin{pmatrix} 1 & 0 \\ 0 & -1\end{pmatrix}\begin{pmatrix} -1 & 0 \\ 0 & 1\end{pmatrix}\mathbf x = \begin{pmatrix}-1 & 0 \\ 0 & -1\end{pmatrix} = H\mathbf x = h(\mathbf x) \end{align*}

これより、行列が関数として扱えている事がわかる。

命題 2.1.9

2つの列ベクトル\(\mathbf a = \begin{pmatrix} a \\ c\end{pmatrix}, b = \begin{pmatrix} b \\ d\end{pmatrix}\)によって作られる平行四辺形の面積\(S\)は行列\(A = (\mathbf a \mathbf b) = \begin{pmatrix} a & b \\ c & d\end{pmatrix}\)の行列式\(\Delta\)の絶対値\(\mid\Delta\mid = \mid ad - bc \mid\)に等しい

教科書の方では内積つかったり云々してますが、この時点では教科書中には内積やらは出てきてないのでそれらを使わない方向で説明。次のような図で考える。

空白部分が求めたい面積S。こんな感じで座標に当てはめてみると、平行四辺形を含む大枠の矩形の面積は\( (a+b)(c+d) \)で表される。あとは縦線、横線が引かれている領域をそこから引けばいい。
引く対象の面積はいずれも三角形と台形の面積なので、容易に求められる。これらの和は

\begin{align*} \frac{ac}{2} + \frac{bd}{2} + \frac{(c+(c+d))b}{2} + \frac{(b+(a+b))c}{2}\\ = \frac{1}{2}(ac + bd + 2bc + bd + ac + 2bc)\\ = ac + bd + 2bc \end{align*}

これを先程の矩形の面積から引けばよいので

\begin{align*} (a+b)(c+d) - (ac + bd + 2bc) = ad - bc \end{align*}

以上より、命題が示された。

例 2.1.11

平面上の点\((x,y)\)を原点を中心に反時計回りに\(\alpha\)回転した点\((x', y')\)に移す写像を\(f:{R}^2 \to {R}^2 \)とする。\((x,y)\)と\((x',y')\)を複素平面上で考えると、それらの間の関係は定理1.2.6により

\begin{eqnarray} x' + iy' & = & (\cos \alpha + i\sin \alpha)(x+iy)\\ & = & (x\cos \alpha - y\sin \alpha) + i(x\sin \alpha + y\cos \alpha) \end{eqnarray}

と、教科書の方には定理1.2.6よりこの様な式を導出してますが、複素平面の極座標を用いてお手軽に導出してみます。

図にして表すと次のような図で、左が\(x,y\)平面上で\(\alpha\)回転させたイメージ。それを複素平面上の極座標で考えたイメージが右の図で、座標\((x,y)\)を\(z_1 = re^{i\theta_1}\)。また、\(\alpha\)と同じ角度の\(\theta_2\)を考え、\(z_2 = re^{i\theta_2}\)とすると、これらの積\(z_1 z_2\)が\(z'\)となる。

式にしてみると

\begin{align*} z_1 \cdot z_2 = r_1 r_2 e^{i(\theta_1 + \theta_2)} \end{align*}

となり、長さ\(r\)は\(z_1\)のものだけあればよく、\(z_2\)については回転分だけが欲しいので\(\mid z_2 \mid = 1\)つまり\(r_2 = 1\)とすると

\begin{align*} z_1 \cdot z_2 = r_1 e^{i(\theta_1 + \theta_2)} \end{align*}

となるので、回転を単なるかけ算として扱うことが出来る。
さて、\(z = x + iy\)だったので、複素平面上でここから\(\alpha\)回転させるには\(e^{i\alpha}\)を掛ければよいので

\begin{eqnarray} z' & = & e^{i\alpha}(x + iy)\\ & = & (\cos \alpha + i\sin \alpha)(x + iy)\\ & = & \cos \alpha \cdot x - \sin \alpha \cdot y + i(\sin \alpha \cdot x + \cos \alpha \cdot y)\\ \end{eqnarray}

であるから、つまり

\begin{align*} \begin{pmatrix} x' \\ y'\end{pmatrix} = \begin{pmatrix}\cos \alpha \cdot x - \sin \alpha \cdot y \\ \sin \alpha \cdot x + \cos \alpha \cdot y\end{pmatrix} = \begin{pmatrix}\cos \alpha & -\sin \alpha \\ \sin \alpha & \cos \alpha\end{pmatrix}\begin{pmatrix}x \\ y\end{pmatrix} \end{align*}

として回転を表せる

2.2 行列の定義と演算

いままで見てたのは2行2列程度の行列でしたが、ここでもっと一般的な行列について見ることとなります。\(m\)行\(n\)列の行つのことを\((m, n)\)型行列とも言うそうです。
\((m, n)\)型の行列\(A\)と\((n, r)\)型の行列\(B\)についてはそれらの行列で積を求め、\((m, r)\)型の行列を導く事が出来ます。これはつまり\((m, n)\)型の行列（\(m \neq n\)）は\(n\)次元から\(m\)次元への写像を表していると考えることが出来るためで、これはそもそも異なる次元が結果として出てくるので単位行列（恒等写像\(I\)）は存在しない。

p.42 2.3.5

行列のトレースについて

\begin{align*} tr AB = tr BA \end{align*}

とある。これはあくまで行列の積を二分割して入れ替える事が出来るというだけであり、自由に入れ替えていいというわけではない事に注意。

\begin{align*} ○tr ABCD = tr BCDA \\ ×tr ABCD = tr ADCB \end{align*}

p.42 2.3.2 掃き出し法による逆行列の計算

やり方については教科書を参照。

ここで行われている行基本変形の操作は、その操作に対応する正則行列を左から掛ける事に対応している。つまり、行列\(A\)に対して行基本変形で逆行列を求めるという操作は、\(m\)回目に行基本変形で掛ける正則行列を\(R_m\)として、n回の操作で終わる場合

\begin{align*} R_n \cdots R_1A = I \end{align*}

と表せる。さて行列\(A\)について、式(2.32)、(2.33)より

\begin{align*} A\mathbf x = \mathbf y \Leftrightarrow \mathbf x = A^{-1}\mathbf y \end{align*}

であるから、先程の行基本変形より

\begin{align*} \mathbf x = I \cdot \mathbf x = R_n \cdots R_1A\mathbf x = R_n \cdots R_1\mathbf y \\ \end{align*}

となるので、\(\mathbf x = A^{-1}\mathbf y\)より

\begin{align*} R_n \cdots R_1 = A^{-1} \end{align*}

である。ちなみに列基本変形では右から\(R_m\)を掛けていくのに相当するので、行基本変形と同様には扱えない。

Javaバイトコードの読み方

先日、Javaクラスファイル入門 - connpassにてバイトコードの読み方について話してきたので、折角だからこちらにも書いてみます。
内容的にはあくまで入門ということで、サンプルとして取り上げたコードを読むために必要な範囲の知識のみ、加えてあまり厳密な事までには言及していません。とりあえずこんな感じで動いてるという雰囲気を掴む事を主眼に起きました。厳密な定義なんてわざわざ自分が言わなくても仕様書見れば書いてありますしね。

Javaバイトコードとは？

通常、コンピュータを動かすための命令は高級言語がなんであれ、最終的にはアセンブラ、ひいては機械語となって処理されます。
Javaでは様々なプラットフォーム上で動作するJava仮想マシンを用意し、その仮想マシン上で動作する、先述のアセンブラの位置に該当する言語を解釈して実行します。大雑把に言ってしまえば、それがバイトコードということですね。

バイトコードを学ぶ意義としてもアセンブラと同様の事が言えます。最終的にどういう挙動になるのかを理解することは、より上位のコードを書く上でも助けになるでしょう。
私よりもちゃんとしたエンジニアのお言葉を聞きたい人は下記のIBM developer worksの記事を読むといいと思います。

Java bytecode:

Javaバイトコードの閲覧方法

javapコマンドを使います。この辺りは同勉強会で自分よりも先に、バイナリの解析について講師をしていただいた虎塚さんの記事を見ていただいた方が早いので、そちらに譲ります。

実例その１

以下のコードについて考えます

このコードをコンパイルして、javapにかけると次の様なコードが出力されます

Constant poolはひとまず置いておきましょう。定数やらが定義されているところです。本稿で着目すべき対象はその下、ブラケットで囲まれている箇所になります。抜き出すと以下の通り。

前半部分がコンストラクタ、後半部分がmain関数のバイトコードに相当します。javaのコードにはコンストラクタを書いていませんでしたが、このバイトコードから自動的に補完されていることがわかりますね。
さて、更にmain関数のみに着目して、そのバイトコード本体を見てみましょう。それだけを抜き出したものが次のコードです。

左の番号は行番号ではなく、実際にクラスファイル上でバイトコードが含まれている構造の中で何バイト目の位置にあるかを表したものです。
さて、これらの処理について概要を見てみます。詳細については後述するなりしますので、一旦は意味不明な言葉が出てきても突き進んでください。 また、以降で述べる命令についての正確な定義はJava Virtual Machine Specification (PDF)を参照下さい。

getstatic命令

getstatic命令はクラスのstaticフィールドを取得します。今回のコードではConstant poolの#2に該当する部分、java/lang/System.out:Ljava/io/PrintStream;より、java/lang/System.outを取得しています。

ldc命令

実行時コンスタントプールから項目をpushします。何処にpushするのかは後述。今回のコードでは#3、つまり文字列helloをpushする事を意味します。

invokevirutal命令

クラスに基づくディスパッチを行い、インスタンスメソッドを起動します。今回のコードでは#4、つまり java/io/PrintStream.println:(Ljava/lang/String;)V の型に一致するインスタンスメソッドを実行します。つまりはSystem.out.println(String)を実行することになります。

return命令

メソッドからvoidをreturnします。main関数の定義より、返値はvoidである必要があるのでこの命令が実行されます。

以上より、このmain関数では

1. 使用するフィールド（System.out）の取得
2. 引数（文字列hello）を渡す
3. 関数（println）の実行
4. voidをreturn

という手順で動作していることがバイトコードから読み取れます。

もうちょっと踏み込んでみる

さて、今の例では何をやっているかに軽く触れただけで、細かいところはスルーしてきました。ここで今のコードを理解するのに必要な最低限の事柄に触れておきます。

Java仮想マシンスタック

Java仮想マシンはプログラム実行時に必要なデータを保持する領域をいくつか持ちます。先程の処理を理解する為に、Java仮想マシンスタックについて見ていきます。

このスタックはスレッド作成と同時に作られる領域であり、フレーム（後述）を保持するためのものです。各スレッド毎にこのスタックを保持することになります。

こんな感じですね。各スレッド毎のスタックは独立しています。

フレーム

スタックに積まれている、このフレームというもの。これらはメソッド毎に作成され、そのメソッドのローカル変数やオペランドスタック（後述）などを保持します。メソッドの定義が同じものであっても、メソッドの実行毎にそれぞれがフレームを持つことになります。再帰処理などで同じ定義のメソッドを呼んでも状態がそれぞれ独立して保持されているのはこのためですね。

オペランドスタック

位置づけとしては前述の図の通り、フレームの中にあります。このスタックの役割は色々ありますが、ここで注目するのは

• メソッドの呼び出し時に渡すパラメータの準備
• 呼び出したメソッドから結果の受け取り
• Javaバイトコードの命令セットからの利用

といった所です。例として、バイトコードのiadd命令を見てみましょう。この命令の概要は

1. オペランドスタックから値を2つpopしてくる
2. それら2値の和を取る
3. 結果をオペランドスタックへpushする

という具合です。オペランドスタックの状況を図を交えて見てみます。

まず、スタックに和を計算する対象の2値、aとbが入っている状態とします。iadd命令はこれらをpopします。

iaddがpopした2値の和を計算します。popされているのでスタックは空になっています。

計算結果をpushします。この処理を経て、オペランドスタックには計算結果の値が1つだけ積まれている状態になります。

ローカル変数配列

ローカル変数配列はローカルで使われる変数を保持するのに使われる他、状況によってはメソッド起動時のパラメーター引き渡しに使われます。例えばクラスメソッドの起動では、配列のindexが0の位置から連続したローカル変数として引き渡される事になります。

例えば、クラスXのメソッドAから、このクラスのクラスメソッドBを引数 x,y,z を渡して呼び出すとします。適当に書くならこんな感じでしょうか

class X {
    public static void A () {
        X.B(x, y, z);
    }

    private static void B(int x, int y, int z) {
        return x + y + z;
    }
}

このとき、Bのフレームにはローカル変数配列のindexが0の位置から順にx, y, zが入っている状態として、Bが開始されることになります。

最後に

一応、勉強会の時はもう一歩複雑な例について、スタックの様子も見ながらバイトコードをトレースして挙動を観察すると言うことをやりました。それについては省きます。スタック周りがわかってれば、あとは仕様書でコードの挙動を追えばそれでわかる範囲のものですから。

コードだけ載せておきますと、こんな感じで変数の定義と計算、クラスメソッドの呼び出しが含まれるものになります。興味ある人は実際にコンパイルしてクラスファイルをjavapにかけてみるといいと思います。そんなに長くもないので、軽い気持ちで出来る練習になるかと。

バイトコードの命令について、詳細な仕様はOracleの公式ドキュメントで、"The Java Virtual Machine Specification, Java SE 8 Edition"の方を閲覧してもらえばよいと思います。命令の一覧はchapter6にあります。フレームやらオペランドスタックやらの話はchapter2の2.6です。

OSvのCLI周辺コードをみてみる

※この記事は OSv Advent Calendar 2014 9日目の記事です

最近、ちょこちょことOSvを触らせてもらってるので、OS関連周りにはあまり明るくないながらも書かせてもらう事にしました。 こっち方面を専門としている訳ではない為、間違っている箇所などありましたらご指摘ください。

さて、CLI周りについてなのですが、前回のOSvもくもく会#4の時にこの辺りの構造について見ていたのでそこら辺触れてみようかと。adventcalendar始まってみたら @syuu1228 さんとかぶり気味だったので変えようかと思ったけど、そんなにホイホイとネタが出てくるわけでもないので突き進みます。

OSvのCLIについて

元々、OSvがjavaアプリを動かすという想定で始まっている事もあり、しばらくはCLIのシェルとしてCRaSHってのを使ってました。それをリプレースする物として、Luaで書かれたCLIが作られたそうです。後者については既に三日目のcalendarで軽く触れられてますね。

このCLI周りについて、チラッと見てみた事を徒然と書いていきます。 そうそう、OSvは凄い勢いで機能追加やらされてるので、今回書いている事もすぐに変わってしまうかもしれません。この記事は v0.16-12-gbc3b9f6 を元に書いています。

CLIのコードを見てみる

最初の一歩

場所については先ほど触れた三日目の記事で紹介されている通り、こちらにあります。pathを見ての通り、このCLIもmoduleの1つとして実装されていますね。ディレクトリ内はこんな感じ

$ ls -1
cli.c
cli.lua
cli.so
commands
doc
lib
Makefile
module.py
rpmbuild
test

module.pyはこのmoduleの起動処理辺りが書いてある様で、内容は下記の通り

from osv.modules.api import *
from osv.modules.filemap import FileMap
from osv.modules import api

require('lua')
require('ncurses')
require('libedit')
require_running('httpserver')

usr_files = FileMap()
usr_files.add('${OSV_BASE}/modules/cli').to('/cli') \
        .include('cli.so') \
        .include('cli.lua') \
        .include('lib/**') \
        .include('commands/**')

full = api.run('/cli/cli.so')
default = full

cli.soをrunしてますね。この段階で、cli.cがcliコマンド（これも例の三日目の記事で使ってましたね）の実装となり、これがcli.luaに処理を渡してcommandディレクトリ配下に記述のあるluaで書かれたコマンドを実行してるのかなーって予想が立ちますね。

cli.c

そんでは、cli.cを見てみましょうか。全部トレースしていくとこの記事だけでは終わらなそうなので、要所だけ。 main()内では大筋として、テストコマンド、単一コマンド実行、シェルの起動に分かれている様です。

int main (int argc, char* argv[]) {
    ...
    if (test_command != NULL) {
        ...
        lua_getglobal(L, "cli_command_test");
        ...
    else if (optind < argc) {
        /* If we have more arguments, the user is running a single command */
        ...
        lua_getglobal(L, "cli_command_single");
        ...
    } else {
        /* Start a shell */
        ...
           lua_getglobal(L, "cli_command");
        ...
    }
    ...
}

こんな感じで各々のパターンに応じてluaでglobalとして作られているメソッドを読んでいる様です。

cli.lua

さて、簡単な所から見てみる事にして、cli_command_singleから見てみましょう。

function cli_command_single(args, optind)  local t = {}
  for i = optind, #args do
    table.insert(t, args[i])
  end
  cli_command(t)
end

用はアレですね。例えば

 $ cli -a http://192.168.122.72:8000 ls -lh

とかって記述した場合、ls -lh の部分だけ抜き取ってcli_commandに投げる感じですかね。 cli_command_testは紙面の都合で飛ばさせてもらい、cli_commandに進んでみます。要所をピックアップすると

function cli_command(args)
  ...
  if #arguments > 0 then
    command = arguments[1]
    ...
    filename = command_filename(command)
    if file_exists(filename) then
      local cmd = dofile(filename)
      local cmd_run = true

      ...
      if cmd_run then
        local status, err = pcall(function() cmd.main(arguments) end)
        if not status then
          print_lua_error(command, err)
        end
      end
    else
      print_cmd_err(command, "command not found")
    end
  end
end

ざっと読むと、ここに渡された引数の最初の文字列と一致するファイルを探し、そのファイルに実装されているものがコマンドの実態として扱われ、実行されるということですね。ちなみにcommand_filename()はlib/util.lua内にあり、

function command_filename(name)
  return string.format('%s/%s.lua', context.commands_path, name)
end

となっています。commands_pathは巡り巡ってcli.c内にて #define CLI_COMMANDS_PATH "/cli/commands" として定義されていますね。以上より、CLI実行時、各コマンドの処理は/cli/commands内の当該luaファイルが実行されている事まで追えました。lsコマンドなら/cli/commands/ls.luaですね。

コマンドの実装

ということで、コマンドを実装してやるには先述のディレクトリへluaプログラムを置いてやればいいんだろうという判断に至ったわけですが、これ、散々述べている様にLuaで書かれてるんですよ･･･。なんか足りないコマンドを実装してやろうとは思ったんですが、Luaはneovimで使うぞー！って聞いて本買ってみた程度なので、実装能力はほぼ絶無な為、今のところ断念中。

これはOSv全体にわたって言える事なんですが、使ってる言語多すぎでは･･･。ぱっと見た限りでもC++11、python、go、luaが飛び交っております。でもLuaはちょっと興味あるので、これを機に弄ってみるとおもしろいんじゃないかとは目論んでます。

というわけで

何はともあれ、現在private betaが行われているOSv。まだまだとりつく島もないような大規模ではないので、興味あったら読んでみる（できれば何か実装してみたりする）と面白いんじゃないかと思います。パッチの送り方等については四日目の記事を参照ください。

補数表現について

補数って？

2進数を扱うとき、符号付きの場合を考えると決まって出てくる「2の補数表現」ってやつ。 これ自体は「補数」と一般的に言われるものの定義から明確なので、何も問題は無いんです。

補数 - Wikipedia

wikipedia先生でも述べられている通り、補数とは\( {b} \)進法において、自然数\( {a} \)を表現するのに必要な最小限の桁数を\( {n} \)としたとき

\begin{align*} {b}^{n} - {a} \end{align*}

である。つまり「補数」とは、表したい数について「必要な桁数 +1」桁の最小の数から、その表したい数を引いた値。言い換えれば、表したい数に対して和をとれば桁が上がる値のなかで最小のものということになる。
この辺りについては 原書で学ぶ64bitアセンブラ入門（2） - わらばんし仄聞記 でも触れましたが、例えば10進数で考え、61という値の補数は39になります。

以上より、2進数においては各ビットを反転させたものに1を足したものが「2の補数」であることは容易に理解出来ます。

1の補数表現

さて、悩みのタネであった「1の補数表現」です。
先述の定義にそのまま当てはめて考えてしまうと、「1進法」？なんだそれは･･･。と、完全にポルナレフ状態になってしまいます。

さて、またもwikipedia先生の出番です。
符号付数値表現 - Wikipedia

こちらで書いてある通り、英語の時点では「1の補数」とは "ones' complement" であり、「2の補数」は "two's complement" と表されています。2の補数についてはいいでしょう。英語の方でも2を基数として補完する値ということが読み取れます。
問題の「1の補数」ですが、 "ones'" となっています。-sで終わる複数形の名詞について所有格を示す為には、末尾にアポストロフィだけを付記する事からわかる通り、これは、複数の "1" の並びを補う値という意味が読み取れます。

これはつまり、最初にリンクを貼ったwikipediaのページにある「減基数の補数」を2進数の場合において表している訳で、実際その辺りの書き分けが英語では出来ますよということも述べられていますね。
減基数の補数は英語で "diminished radix complement" というそうで、そこら辺については以下を参照してもらうといいかと。

Method of complements - Wikipedia, the free encyclopedia

つまり

補数をとる対象Nについて、適当な値aについて考えると

N's complement -> Nの冪乗と相補関係（aに対して、「a以上であり、かつ最小のNの冪乗」となるために足すべき数）
Ns' complement -> Nを複数並べたものと相補関係（aに対して、全て桁がNで埋まるように足すべき数）

という違いが存在する。

一般的に「2の補数」と合わせて述べられる「1の補数」は「2進法における減基数の補数」の事であり、これはつまりがビットを反転させたものと一致する。昔は負数の表現に、先頭のビットを1として、残りのビットを対応する正の数を反転させたものを使っていたそうです。その辺りはwikipediaの方が詳しいのでそちらを見てもらったほうがいいですが、この場合、0と-0という0の表現が2つ出来てしまう事になる為に計算が複雑になるため、現在、負の値については+1して-0の位置に-1が来るようにしたものを使います。

さて、2の補数が各ビットを反転させたものに1を足したものとして表現できることは先に述べたとおり。また、直前で述べた負数の表現は「1の補数を求めた（＝ビットを反転させた）ものに1を足す」事によって-0を省いた負数表現をしていました。つまり、やっている事は同じ操作ですね。
これより、「負の値を求める時は2の補数」を求める。また、その導出については「全部のビットを反転させて1を足す」という操作の全てがリンクしたことになります。

ほとんどwikipedia読んで思ったことを書いたばかりな感じですが、自分の中では全部つながってスッキリした感じがします。
なにか間違っている点があったら、ご指摘お待ちしてます。

池袋物理学勉強会

池袋物理学勉強会(6) - connpass へ行ってきました。

唐突なのでさわりを述べておくと、以下の本を進めていき、後々は量子力学がわかるようになろうというのを目指している勉強会です。

Amazon.co.jp： 量子力学を学ぶための解析力学入門 増補第2版 (KS物理専門書): 高橋 康: 本

さて、本日は第二章の演習問題を解く回だったのですが、その内の1問を担当したので折角だから忘れないうちに書いておきます。

P.50 演習問題2 問1

設問

空間の与えられた2点を結ぶ線のうち、直線が最短であることを変分法を用いて示せ

解答

題意より、下のような図を考えます。

与えられる2点をa,bとし、その間を結ぶ線分\( l \)（図の青い線分）が最短となる時の式が直線を示す様になっていれば良い。

線分\( l \)上の微小区間\( {ds} \)を考える。\( {ds} \)は

\begin{align*} {ds} = \sqrt{ {\left({dx}\right)}^2 + {\left({dy}\right)}^2 } \end{align*}

である。線分\( l \)は

\begin{align*} l = \int {ds} \end{align*}

と表せるので、先ほどのより

\begin{eqnarray} l=\int \sqrt{ {\left({dx}\right)}^2 + {\left({dy}\right)}^2 } \\= \int {dx} \sqrt{ 1 + {\left(\frac{dy}{dx}\right)}^2 } \end{eqnarray}

で表すことが出来る。\( l \)は汎関数であり、これが停留値をとればよく、つまり変分\( \delta{l} \)が

\begin{align*} \delta{l} = 0 \end{align*}

となればよい。\( {\frac{dy}{dx}} = {y'} \)と置くと

\begin{align*} l=\int {dx} \sqrt{ 1 + {y'}^2 } \end{align*}

であるから

\begin{eqnarray} \frac{\delta{l}}{\delta{y'}}=\int {dx}(1+{y'}^2)^{-\frac{1}{2}} \cdot {y'}\\ \delta{l} = \int {dx} \cdot {y'}(1+{y'}^2)^{-\frac{1}{2}} \cdot {\delta{y'}} \end{eqnarray}

\( {y'} \)を\( {\frac{dy}{dx}} \)に戻して

\begin{eqnarray} \delta{l} = \int {dx} \frac{dy}{dx} {\left\{1 + {\left(\frac{dy}{dx}\right)}^2\right\}}^{-\frac{1}{2}} \frac{d\delta{y}}{dx}\\ \frac{\delta{l}}{\delta{y}} = \int {dx} \frac{dy}{dx} {\left\{1 + {\left(\frac{dy}{dx}\right)}^2\right\}}^{-\frac{1}{2}} \cdot \frac{d}{dx} = 0 \end{eqnarray}

となればよいので、つまり \begin{align*} \frac{d}{dx} {\left[\frac{dy}{dx} {\left\{1 + {\left(\frac{dy}{dx}\right)}^2\right\}}^{-\frac{1}{2}}\right]} = 0 \end{align*}

であればよい。これは、\( {C} \)を定数として

\begin{align*} \frac{dy}{dx} {\left\{1 + {\left( \frac{dy}{dx} \right)}^2 \right\}}^{-\frac{1}{2}} = {C} \end{align*}

の時に成り立つ。よって

\begin{eqnarray} \frac{dy}{dx} = {C}{\left\{1 + {\left( \frac{dy}{dx} \right)}^2 \right\}}^{\frac{1}{2}}\\ {\left(\frac{dy}{dx}\right)}^2 = {C}^2{\left\{1 + {\left( \frac{dy}{dx} \right)}^2 \right\}} \end{eqnarray}

\( {\left(\frac{dy}{dx}\right)}^2 = \alpha \)とすると

\begin{eqnarray} \alpha = {C}^2(1 + \alpha)\\ (1-{C}^2)\alpha = {C}^2\\ \alpha = \frac{{C}^2}{1-{C}^2} \end{eqnarray}

つまり

\begin{align*} \frac{dy}{dx} = {\left(\frac{{C}^2}{1-{C}^2}\right)}^{\frac{1}{2}} \end{align*}

であり、\( {\left(\frac{dy}{dx}\right)}^2 \)は定数であることがわかる。これより\( {l} \)は

\begin{align*} {l} = \int {dx}\sqrt{1 + {C}} \end{align*}

で表せ、\( \sqrt{1 + {C}} \)をまた定数\( {a} \)と置くと

\begin{eqnarray} {l} = \int {a} {dx}\\ = {ax} + {b} \end{eqnarray}

つまり、\( {l} \)は直線である。

余談

途中から\( {y'} \)の二次方程式とおいて、もっとシンプルに解答まで到れる方法もありますが、そこら辺は気が向いたら追記します。
また、問題が変分法を用いて解けということで上記のようにしていますが、Euler-Lagrangeの式を使ってもあっさりできます。
とりあえず、数式は書くのが大変だということがよくわかりました。

原書で学ぶ64bitアセンブラ入門（10）

14章、入出力ストリームについてです。

Using the C stream I/O functions

システムコールの章では、入出力に関してopen read write closeというシステムコールのラッパー関数について見てきました。この章ではバッファ付きI/Oを使う関数について見ていきます。

バッファ付きI/Oを使った方が読み込みが効率的になり、その仕組みは次のようになっています。例として1byteの読み込みを実行すると仮定します。

1. 1byteをバッファから読み込もうとする
2. バッファに対象のデータが無い
3. バッファを満たすだけのデータ（一般的に8192byte）をバッファに読み込む
4. バッファに読み込まれたデータから目的の1byteを取得する

この際、バッファからの読み込みは高速な為、ある程度のbyte数を読み込む必要がある場合は最初以外バッファとのやり取りになるので高速に行えます。つまり、8192byte以下の容量ならば実際に呼んでいるシステムコールは1回だけで満足させることが出来ます。

Opening a file

ストリームI/O関数を使ってファイルを開くには、fopenを使います。fopenのプロトタイプは

FILE *fopen ( char *pathname, char *mode );

となります。まぁ、よく見るfopenそのままですね。第1引数がファイル名で第2引数がモードです。モードについても今更ですが、折角本にも書いてあるので一応記しておきます。

mode	内容
r	読み込みのみ
r+	読み書き
w	書き込みのみ。ファイルは初期化されるか新規作成する
w+	読み書き。ファイルは初期化されるか新規作成する
a	書き込みのみ。ファイルに追記するか新規作成する
a+	読み書き。ファイルに追記するか新規作成する

fopenの返値はFILEオブジェクトのポインタです。システムコールのopenでは返値がファイルディスクリプタの番号だったので、ここら辺が異なりますね。まぁ、第2、第3引数も違いますが･･･。
FILEオブジェクトについての詳細には本書では触れていません。そこまで知る必要が無いということで、大抵の場合、FILEオブジェクトはファイルといくつかのファイルについての"状態監視"データ要素へのバッファのポインタを内包した構造体であるとだけ触れています。
返値はポインタということで、アセンブラではquad-wordサイズの領域を確保しておけばそこに保存し、後で使うことが出来ます。ということで、実際に使ってみるとこの様になります。

fscanf and fprintf

fscanf fprintfは第1引数にFILEオブジェクトへのポインタを指定出来るようになっています。scanf printfは第1引数をそれぞれstdin stdoutに固定してfscanf fprntfを呼び出すといった程度の違いです。

fgetc and fputc

fgetc fputcのプロトタイプは

int fgetc ( FILE *fp );
int fputc ( int c, FILE *fp );

fgetcの返値は基本的に読み込まれた文字。fputcの返値は基本的に書き込んだものと同じ文字です。
さて、fgetcで1文字を取得した後、余分に取りすぎた場合を考慮し、その1文字をストリームへ戻すための関数ungetcがあります。プロトタイプは

int ungetc ( int c, FILE *fp );

ungetcで戻せるのは1文字だけで、繰り返しungetcを実行したからといって際限なくストリームへ戻せるというわけではありません。
この館数の使いどころとして真っ先に思い浮かぶのが構文解析を行うケースで、例えば12345,23456という,区切りの2数値について考えてみると、12345までを1文字ずつ取得して数値として解析していき、,をfgetcしてストリームから得た段階で数値が終わっていた事が判明します。この1字先読みして取得してある,を一旦ストリームへ返す事により、数値である範囲を解析した後、それまで行ってきた解析のループ上で,を解析して必要な処理を行う等の対応が可能になります。これが無いと処理が一般化しづらくて大変ですね。

fgets and fputs

fgets fputs。この辺りもよく見かけるモノなので、特別な説明はここでする必要も無いでしょう。一応、プロトタイプは

char   *fgets ( char *s, int size, FILE *fp );
int     fputs ( char *s, FILE *fp );

本書ではそれぞれの実行時に終端文字の扱いがどうなるかがあれこれ書いてあるので、それらをまとめると

• fgets

  • 改行を読み込んだなら、バッファも改行が保存される
  • 常に読み込んだデータの最後に0x00を置く

• fputs

  • 改行や終端に0x00を加えるといった操作は使用者の責務

fread and fwrite

fread fwrite関数はデータの配列を読み書きするように設計されています。プロトタイプは

int fread ( void *p, int size, int nelts, FILE *fp );
int fwrite (void *p, int size, int nelts, FILE *fp );

第1引数は配列。型は問わず。第2引数は配列要素のサイズで、第3引数は配列の要素数。neltsはおそらくnumber of elementsの略？最後は言わずもがな、FILEオブジェクトへのポインタ。
customers配列の100要素をファイルへ書き込むにはこんな感じ

mov     rdi, [customers]
mov     esi, Customer_size
mov     edx, 100
mov     rcx, [fp]
call    fwrite

fseek and ftell

本書では関数の引数説明程度のことしか書かれてないので、適当にmanでも見てください。

fclose

ストリームを閉じる関数です。ストリームはまだデバイス上へ書き込まれていないデータをバッファに持っているかもしれないので、ちゃんとfcloseを呼び出して書き込ませましょう。場合によってはまだ書き込まれていなかったデータが消失する事になります。

原書で学ぶ64bitアセンブラ入門（9）

続いて13章、Structについてです。
今更ですけど、今回この本で読むまでアセンブラに構造体があるなんて知らなかったです。

Struct

例えばCの構造体で

といった、Customerという名の構造体について考えます。
こんな構造体をアセンブラ上でも実現するとして、結局はアドレス、もしくは先頭位置からのoffsetがわかればそれぞれのフィールドに対応する領域はわかるので、こんな風にして各要素へデータを入れるのと同様の事が出来ます。

まぁ、nameやaddressやらのデータについてはこのコード中には定義されてないですが、どっかで適宜定義されていると思っておいてくださいな。
挙動としては1～2行目でCustomer構造体のサイズに相当する136byteをメモリ割り当てしてます。3行目で一旦cにそのアドレスを保存。4行目で構造体の最初のフィールドであるint idに即値で7を入れてます。5，6行目はname[64]の領域にどこぞで定義されているハズのnameを7行目のstrcpyを使ってコピーするための準備。9～11行目も似たようなものですね。8行目や12行目は構造体先頭からのオフセットで各フィールドを示せるよう、都度raxをセットし直してます。

Symbolic names for offsets

先の例だと位置を数値で直指定なので、当然ながら構造がちょっと変わったらコードの関係するところを全修正の憂き目にあいますね。
ということで、構造体を示すキーワードを使って、ちゃんと構造体を定義してみると

        struc   Customer
id      resd    1
name    resb    64
address resb    64
balance resd    1
        endstruc

こんな感じになります。構造体の構成はstrucからendstrucまでの間で示されます。
この書式で定義しておくと、各フィールド名を個別にequ命令でoffset値として定義しておくのと同等の効果が得られます。但し、このままだと各フィールド名がグローバルでの扱いになってしまうので、それの回避としてこんな感じに。

         struc    Customer
.id      resd    1
.name    resb    64
.address resb    64
.balance resd    1
         endstruc

こうしてprefixとしてドットを付けておくと、参照するにはCustomer.nameみたいに指定しなければなりません。ただ、ちょっと名前が長くなるので面倒ですね。
他に構造体を定義しておくとうれしい事として、(構造体名)_sizeとして、この構造体の占めるバイト数を取得できるということがあります。今回の場合なら、Customer_sizeですね。これらを使ってさっきのコードを書き直すと

こんな風になります。mallocする領域にCustomer_sizeを使ったり、raxからのオフセット指定にフィールド名を使ったりしてますね。これならフィールドの大きさが後で変わったりしても大丈夫。

と、思いきや、これだけで大丈夫なのは今回の場合は運が良かったというか、たまたまそうなってるだけです。何が問題かというと、C言語の構造体では要素のサイズによって、開始位置がアラインメントされてなければならないというのがあります。例えば、今回double-wordサイズのbalanceが始まる位置は、Customerの先頭から数えて132byteの位置からです。これは4の倍数なのでdouble-wordのbalanceに対してはアラインメント不要です。

さて、ではaddressが1byte長くなって65byteになったなら？
C言語上ではbalanceの開始位置をずらし、136byte目からbalanceのフィールドとなるようにします。一方、アセンブラの方はこのままでは133byte目にbalanceが来てしまい、つまりCの構造体とは異なるモノができあがってしまいます。

左図が元の状態で、右図がaddressフィールドを1byte長くし、アラインメントを入れた場合です。アセンブラでも右図のようにしてC言語の場合と合わせたいので、構造体の定義を

            struc   Customer
c_id        resd   1
c_name      resb   64
c_address   resb   64
            align  4
c_balance   resd   1
            endstruc

と、align 4を入れて調整します。

本章の残りは構造体の配列について説明してますが、要はそれも各配列要素となる構造体に対してアラインメントしておかないとダメだよという話です。