2018-02-22

不正アクセスの単語整理

セキュリティはAPでは午後必須科目ですから、
絶対に覚えたいところですね、17個もありますけど。

ちなみに、その17個は下記参考書に則って選択しています。
「平成29・30年版ニュースペックテキスト応用情報技術者」TAC出版

ソーシャルエンジニアリング

「ソーシャル」と聞くとどうしても「社会的な」と翻訳してしまいますが、
元々"social"という英語は「人のあつまりの」という意味がありますから*1、
ここから「人を介した（不正アクセス）技術」という意味でこの言葉が使われています。
総務省のHPによれば、

電話でパスワードを聞き出す
肩越しにキー入力を見る（ショルダハッキング）
ごみ箱を漁る（トラッシング）

が具体例として挙げられていますが、他にも手口は色々はあります。

キーロガー

キー入力の記録（ログ）を取ることで、パスワードなどの機密情報を盗み出す手法です。

バックドア

"back door"は「裏口」という意味です。
バックドアという不正アクセスは、

まず攻撃対象のパソコン・サーバに裏口を作るソフトを忍ばせ
そのソフトが実行されることで実際に裏口が作られ
その裏口から攻撃を受ける（データの盗み出しなど）

という手口です。

フットプリンティング

直訳すれば「足跡をつけること」であり、そこから、攻撃対象への事前調査を意味します。
whois情報等を調べて、攻撃対象のセキュリティシステムを推測したり、
CGIなどのWebサービスに悪意のある入力を与えた時の反応を見て、
ソフトウェアの弱点を推測したりする手口です。

ブルートフォース攻撃

"brute-force"に「強引な」という意味があります。
このうち"brute"は「獣の」という意味を持っていますが、ややマイナスな印象を持っており、
「野蛮な」「知性の低い」というニュアンスがあります。
総当たり攻撃などが分類されます。

パスワードリスト攻撃

名前の通り、攻撃者が別途入手したパスワードのリストを元に、
パスワードをこじ開けようとする手口です。
パスワードの流用を避ける理由は、パスワードリスト攻撃を回避するためです。

SQLインジェクション

"injection"は「挿入」という意味です。
次の項目のコマンドインジェクションもそうですが、
検索単語が入力されることが期待されているところに、SQLの命令文を混ぜて入力することで、
SQLが想定しない出力をさせて、不正に情報を得る手口のこと。
IPAのHPにも同様の事例が紹介されています。

コマンドインジェクション

上記のSQLインジェクションのOSコマンド版です。
具体的には、直接OSコマンドを実行できるシェルスクリプトに対して、
キーワード等が入力されることを期待差異れているところに、OSコマンドを混ぜて入力することで、
シェルスクリプトが想定しないOSコマンドを実行し、
不正に情報得たり、データ破壊を行ったりすることです。
IPAのHPでは、コマンドインジェクションで乗っ取ったサーバを経由して、
第三者のサーバを攻撃する事例が紹介されています。

クロスサイトスクリプティング

手口としては、上述のSQLインジェクションやコマンドインジェクションと似ています。
「クロスサイト」とは「２つのサイトを跨いで」という意味であり、ここでは、

不正なスクリプト（命令）を受け付けると、問題のある動作をしてしまうWebサイト
不正なスクリプトのリンクが貼られているサイト（掲示板サイトなど）

の２つが登場します。そして、ユーザが2.の方のサイトでリンクをクリックしてしまうと、
ユーザが意図せず、問題のあるWebサイトに不正なスクリプトを送ってしまい、
その結果として、ユーザが偽のWebサイトに誘導され、個人情報等をだまし取られてしまう、
というのが代表的な手口です。
IPAのHPで図付きで解説されていますが、私は余りピンときませんでした。

クロスサイトリクエストフォージェリ

"forgery"は「偽造」という意味で、「リクエストフォージェリ」で
「サーバへのリクエストを偽造する」ということを指しています。
登場するのは、上述のクロスサイトスクリプティングと似ていて、

偽造が容易なリクエストを受け付ける、問題のあるWebサイトサーバ
不正なリクエストを含むURLのリンクが貼られているサイト（掲示板サイトなど）

の２つです。Webサイトサーバへのリクエストは、
本来ユーザが正規の方法で（Webサイト上の操作で）送信しますが、
これを、不正なリクエストを含むURLのリンクをユーザが踏むことで、
ユーザが意図せず、Webサイトサーバにリクエストを送信してしまい、
それを偽造されたリクエストと見抜けないWebサイトサーバが、
ユーザからの意図したリクエストと判断し、それに従った処理をしてしまう、
というのが、クロスサイトリクエストフォージェリの流れです。
これも、IPAのHPに事例が載っています。

ゼロデイ攻撃

ソフトウェアはリリース後に脆弱性が明らかになることがあります。
通常は、脆弱性が発見されるとすぐにその箇所を修正するソフトが配布され、
その配布日をワンデイと呼びます。
ゼロデイ攻撃は、ワンデイより前にその脆弱箇所を突いた攻撃のことです。

ディレクトリトラバーサル攻撃

「ディレクトリ」は「フォルダ」とも呼ばれる、
ファイルを（仮想的に）分類・格納するシステムです（と今更説明するまでもないですが）。
"traversal"は「横断する」という意味で、「ディレクトリトラバーサル」とはつまり、
本来は横断されないはずのディレクトリへ不正に横断され、
外部からのアクセスが想定されていないデータへアクセスされてしまう攻撃です。
日経のHPが分かりやすいと思います。

DoS攻撃

"DoS"とは"Denial of Service"の略語で、「サービス妨害」という意味です。
昔からあるサーバ攻撃手法で、大量のリクエストをサーバに送り付ける等の方法で、
サーバ処理負荷を上昇させ、処理を遅くしたり、サーバをダウンさせたりする手口です。
情報を盗み出すというよりも、サービスの妨害やシステムの破壊を目的とした不正アクセスです。

フィッシング

元々は「釣り」を意味する"fishing"から来た言葉ですが、
「偽のWebサイトへ誘導して、個人情報等を盗み取る」という意味から
"phishing"（発音は同じ）と綴られることが多いです。

IPスプーフィング

"spoof"は「だます、ひっかける」という意味ですが、インターネットセキュリティの分野では
「なりすます」という意味を帯びます。
IPスプーフィングとは、IPアドレスをなりすますことで、攻撃をしやすくする手口です。
具体的には、あるサーバに対して、あたかも内部からのアクセスかのようにIPを偽造して
アクセスすることで、相手の防御システムをかいくぐる方法です。

セッションハイジャック

ユーザとサーバとの通信のやり取りを「セッション」と言います。
セッションハイジャックとは、このやり取りに紛れて、サーバに不正な操作を行う攻撃です。

DNSキャッシュポイズニング

DNSはURLをIPアドレスに変換する（名前解決する）サーバです。
DNSはこの変換を行うために、URLとIPアドレスの対応リストを持っていますが、
このリストにないURLを変換する時や、定期的なリスト更新のために、
別のDNSに対してIPアドレスを問い合わせることをします。
この機能を悪用して、

攻撃者がDNSに対して、DNSが持っていないだろうURLの名前解決をリクエストする
DNSが他のDNSに対して、同様のリクエストをする
その回答が送られてくる前に、攻撃者が偽のIPアドレスの回答を送り付ける
それを正規の回答と勘違いし、自分のリストに追加してしまう

というのが、DNSキャッシュポイズニングです。
"poisoning"は「毒を盛る」という意味です。
この攻撃を受けたDNSを使うと、該当するURLに対して偽のIPアドレスを回答してしまうので、
ユーザは正しいURLを入力したにも関わらず、偽のWebサイトに誘導されてしまうのです。

*1:そして、元々は「村の祭り」という意味でしかなかった「社会」という漢語を、"society"の訳語として日本人が当てたのです。

2018-02-17

原点を通る3次関数の接線の式を代数的に求めてみる

その他

3次関数の接線に関する問題は、接点の座標を使って接線の関数を立て、
その接線が3次関数上にない決められた点を通るので…という流れで解くのがセオリーです。
微分を用いた、いわゆる「逆手流」の解き方ですね。

3次関数 $y=px^3+qx^2+rx+s$ の接線が点 $(a,b)$ を通るときの、
接線の式を求めよ、という問題は、
接点の $x$ 座標を $t$ と置くことで、接線の式を
$y=(3pt^2+2qt+r)(x-t)+pt^3+qt^2+rt+s$ と表せるので、
これが点 $(a,b)$ を通るということは、
$b=(3pt^2+2qt+r)(a-t)+pt^3+qt^2+rt+s$ が成り立つので…という流れで、
接点の $x$ 座標を $t$ を求め、そこから接線の方程式を求める、
という方法です。

点 $(a,b)$ がたとえ原点、つまり点 $(0,0)$ であっても同様であり、
某有名予備校の某講師曰く、
「ここ（＝点 $(a,b)$ ）が原点だとぉ、誘惑に負けて
　 $y=mx$ なんて置いちゃう輩がいるけど、駄目だよぉ！」
というやつです。

じゃぁこれを敢えて $y=mx$ と置いて解こうとするとどうなるのか、
ちょっとやってみようと思います。

カルダノ＝タリタリアの公式

カルダノ＝タリタリアの公式（単にカルダノの公式とも）とは、
3次方程式の解の公式です。
中学・高校で、2次方程式 $ax^2+bx+c=0$ の解の公式
$x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}$
を習いましたが、これの3次方程式バージョンです。

この公式自体については、他の書籍やWebサイトに譲りますが、
導出までの手順としては、

3次方程式 $ax^3+bx^2+cx+d=0$ を立体完成する
$x+\frac{b}{3a}=X$ と書き換える
更に $X=u+v$ で置き換える
書き換えた $u$ 、 $v$ の式は $u$ 、 $v$ の恒等式であることを利用して、 $u^3+v^3$ 、 $u^3v^3$ の値を求める
2次方程式の解と係数の関係を用いて、 $u^3$ 、 $v^3$ の値を求める
$u$ と $v$ との関係に注意して、3つの $u$ 、 $v$ の組を求める
ここから $X$ の値を算出し、最後に $x$ の値を算出する

という流れです。

今回は、この流れを途中まで利用して、
先の問題、「接線の式を敢えて $y=mx$ と置いて解いてみる」をやってみます。

方針

接線 $y=mx$ が3次関数 $y=f(x)$ と接しているということは、
これを連立させることで得られる3次方程式 $f(x)-mx=0$ が
重解を持っているということになります。

ところで、2次以上の方程式が複素数を解に持っている場合、
その共役の複素数も解であるという決まりがありますから、
3次方程式が重解を持っている、という時点で

その重解は実数である
残りの解も実数である

ことが判明し、3つの実数解（うち2つは重解）を持っていると言うことができます。

このこと踏まえて、先ほどのカルダノ＝タルタリアの公式の流れを進むと、
5.の「 $u^3$ 、 $v^3$ を求める」タイミングで、これが重解である必要が出てきます。
これを使って、 $m$ の値を求めます。

例題

例題として、次の問題を解いてみます。

3次関数 $y=x^3-3x^2-1$ の接線が原点を通るとき、この接線の関数を求めよ

普通に導関数を用いて答えを求めると、
（過程は省略しますが） $y=-3x$ 、 $y=\frac{15}{4}x$ が正解です。

回答

3次関数の接線として、 $y$ 軸に平行なものは存在しないので、
原点を通る直線の関数は実数 $m$ を用いて $y=mx$ と置ける。

これが3次関数 $y=x^3-3x^2-1$ に接しているので、
この2式を連立させ $y$ を消去することで得られる
3次方程式 $x^3-3x^2-mx-1=0$ が実数の重解を持つことになる。

ここで、この3次方程式を以下のように変形する：
$x^3-3x^2-mx-1=0$
$(x-1)^3-3x-mx=0$
$(x-1)^3-(m+3)(x-1)-(m+3)=0$

ここで $x-1=X$ と置くと、
$X^3-(m+3)X-(m+3)=0$ となり、
この $X$ の3次方程式が実数の重解を持つこととなる。

更に、 $X=u+v$ と置く。
すると、この3次方程式の解の一つの値に対して、自由に $u$ を定めることができ、
それに対応して $v$ が定まることになる。
すなわち、 $X=u+v$ で置き換えた
$(u+v)^3-(m+3)(u+v)-(m+3)=0$ は、 $u$ 、 $v$ の恒等式である。

上式を変形すると、
$u^3+v^3+\{3uv-(m+3)\}(u+v)-(m+3)=0$ となるが、
式中の $u+v$ について、

1) $u+v=0$ の場合
$u=-v$ であるので、この式は $m=-3$ となる。
なお、この時 $X=0$ 、 $x=1$ であるから、
重解を持つとした3次方程式に代入すると、こちらも $m=-3$ となり矛盾がない。

2) $u+v\neq0$ の場合
$u^3+v^3+\{3uv-(m+3)\}(u+v)-(m+3)=0$ が $u$ 、 $v$ の恒等式であるので、
$u^3+v^3=m+3$
$uv=\frac{m+3}{3}$ i.e. $u^3v^3=\frac{(m+3)^3}{27}$
が成り立つ。
従って、 $u^3$ 、 $v^3$ は、
$t$ の2次方程式 $t^2-(m+3)t+\frac{(m+3)^3}{27}=0$ の解である。

この解を、 $u^3=\alpha$ 、 $v^3=\beta$ とすると、
$u={}^{3}\sqrt{\alpha}, {}^{3}\sqrt{\alpha}\omega, {}^{3}\sqrt{\alpha}\omega^2$
$v={}^{3}\sqrt{\beta}, {}^{3}\sqrt{\beta}\omega, {}^{3}\sqrt{\beta}\omega^2$
( $\omega=\frac{-1+\sqrt{3}i}{2}$ と定義する、これは1以外の1の3乗根2つの内の1つであり $\omega^3=1$ を満たす。)
となるが、 $uv=\frac{m+3}{3}$ が成立する必要があるので、
1つの $u$ について、1つの $v$ が対応することになる。
具体的には、 $uv$ は実数である必要があるので、3つの $u$ 、 $v$ の組、
$(u,v)=({}^{3}\sqrt{\alpha}, {}^{3}\sqrt{\beta}), ({}^{3}\sqrt{\alpha}\omega, {}^{3}\sqrt{\beta}\omega^2), ({}^{3}\sqrt{\alpha}\omega^2, {}^{3}\sqrt{\beta}\omega)$ が解となる。

ところで、 $X$ の3次方程式が実数の重解を持つということは、
上記3つの組から算出した3つの $u+v$ の値の内、2つが同一であることを意味する。
つまり、 ${}^{3}\sqrt{\alpha}\omega={}^{3}\sqrt{\beta}\omega$ 、 ${}^{3}\sqrt{\alpha}\omega^2={}^{3}\sqrt{\beta}\omega^2$ が成り立つ必要があるので、
$u^3$ 、 $v^3$ を解とする $t$ の2次方程式 $t^2-(m+3)t+\frac{(m+3)^3}{27}=0$ の解も
重解であることになる。

この2次方程式の判別式を $D$ とすれば、
$D=(m+3)^2-4\cdot\frac{(m+3)^3}{27}=0$ となる。
この $m$ の3次方程式を解くと、
$(m+3)^2(1-4\cdot\frac{m+3}{27})=0$
$(m+3)^2(4m-15)=0$
$m=-3, \frac{15}{4}$
となる。

1), 2)より、 $m=-3, \frac{15}{4}$ であるから、
求める接線の関数は、
$y=-3x$ 、 $y=\frac{15}{4}x$ となる。

感想

これは、普通に接線の公式を使った方がいいわ。
$y=mx$ なんて置いちゃう輩の末路はこうなるということです。

補足

ちなみに、実は3次方程式にも解の公式というのは存在します。

$ax^3+bx^2+cx+d=0$ （ $a\neq0$ ）の時、
判別式 $D$ は
$D=-4ac^3-27a^2d^2+b^2c^2+18abcd-4b^3d$
となります。
この時、
$D>0$ ：異なる3つの実数解を持つ
$D=0$ ：重解を持つ（2重解or3重解はわからない）
$D<0$ ：1つの実数解と2つの虚数解を持つ
となります。

2018-02-10

再帰的（リカーシブ）・再入可能（リエントラント）・再使用可能・再配置可能

応用情報技術者試験

紛らわし首記4つの用語についてまとめ。

再帰的（リカーシブ）

プログラムを1つでも学んだことがあるなら、階乗を求める関数を見たことがあると思うが、
あれがまさしく再帰処理をしている。

int factorial(int n){
    if(n==0){
        return 1;
    }else{
        return factorial(n-1) * n;
    }
}

上記は階乗を求めるC言語の関数であるが、factorial()という関数の中で、factorial()を、
つまり自分自身を呼び出している。これがまさに再帰的であるということである。
殆どすべてのプログラム言語で、再帰処理は実行可能である。
BASICでさえ、書き方を工夫すれば再帰処理を実装することができる。

再入可能（リエントラント）

業界的には「リエントラント」の方が通じるらしいので、以降ではこちらで書き進める。
リエントラントな処理とは、その処理を実行中に、更に同じ処理が呼び出されたとしても、
両方の処理が正しく処理を完了できる、ということである。
まずは、この「更に同じ処理が呼び出される」という状況であるが、
以下の3つのパターンがある：

ある処理を実行中にその処理自身が自分を呼び出す
ある処理を実行中に割り込みが入り、その割り込み処理がその処理を呼び出す
別々の場所で、同じ処理が呼び出される

このうち、1)は先に紹介した再帰処理である。したがって、再帰処理はリエントラントである。
2)が、純粋なリエントラントである。一方、3)は「スレッドセーフ」と言われる特性であり、
厳密にはリエントラントとは別の概念である。

再使用可能

プログラムの実行には、①まず記憶装置からプログラムコードを読み取りメモリに配置してから、②メモリに配置したプログラムコードを実行する、という2つのステップを踏む。
複数のソフトウェアが同じプログラムコードを使用したい時、別々にメモリに配置してそれぞれがプログラムを実行しているのは無駄である。
可能であるならば、一度メモリに配置したプログラムコードを、複数のソフトウェアが共有して使うのが望ましい。これができるプログラムを「再使用可能」なプログラムと呼ぶ。
この再使用可能なプログラムが、複数ソフトウェアから同時に呼ばれたときに、
同時に処理を実行できるならば、このプログラムはリエントラントでもある。
しかし、リエントラントではないプログラムでも、再使用可能にすることはできる。
このようなプログラムは特に「逐次再使用可能」であると言う。

再配置可能

再配置可能を説明するためには、まずはメモリアドレスについて知らなければなりません。
プログラムは機械語の命令をつなげたものです。しかし一直線につなげたのでは分岐処理ができません。
分岐処理というと、ifやらforやらswitchやらがありますが、機械語の命令に直すタイミングで、
おおよそジャンプ命令に置き換わります。
ジャンプ命令とは「○○に移動し、そこから命令を始めよ」という命令であり、
C言語で言えばあの悪名高いgotoのことです。
コーディングのマナー、あるいはルールとしてgoto命令を使うなということは色々なところで
言われていますが、実は機械語の世界ではgotoのオンパレードなのですね。
さて、gotoを使うとなると、ジャンプする先を指定しなければいけません。
これをどうやって指定するかという時に、メモリアドレスの話か出てきます。
プログラムは実行時にメモリ上に配置されますから、ジャンプ先として指定するのは
メモリのアドレスになります。この時、

「xx番メモリへ移動せよ」と命令するのが絶対アドレスによるジャンプ命令
「ここからnn先のメモリへ移動せよ」と命令するのが相対アドレスによるジャンプ命令

となります。
絶対アドレスによるジャンプ命令を使うとなると、このプログラムがメモリに配置される際に、
その場所は固定されていなければいけません。そうしないと、配置場所が変わるたびに、
ジャンプしたい先のメモリ位置が変わってしまうからです。
一方、相対アドレスによるジャンプ命令であれば、このプログラムはメモリのどこに配置さても
問題ありません。
再配置可能なプログラムの書き方の一つの方法は、相対アドレスによるジャンプ命令だけで
プログラムを作るという方法です。
他の手法としては、仮想アドレスでメモリ管理するというものもあり、実はこちらの方が主流です。

2018-01-28

リスク／チャンス対応策

応用情報技術者試験

リスク対応策

回避

リスク原因を取り除いたり、そのリスクがプロジェクトに影響しないように、プロジェクトの方を変更すること。
【例】

客先の要求を明確化し、不明瞭な要件をなくす
技術者間コミュニケーションを改善し、コミュニケーションエラーが発生しないようにする

転嫁（移転）

リスクを第三者に負ってもらうことで、リスク発生時の損失を第三者に補填させること*1。
なお、転嫁をする場合は基本的には、第三者に（主に金銭的な）対価を支払う必要があるため、この金銭的コストが新たなリスクになる（二次リスク）。
【例】

納入遅延に伴う違約金を補償してくれる保険に加入する
協力会社の技術者がスキル不足であった場合、別のスキルの高い技術者と交代できるよう契約する

軽減

リスク発生時の影響の大きさを低減させること。
【例】

簡潔な構造を採用し、リスクが発生した時に対処しやすいようにしておく
テスト回数を増やし、できるだけ不具合を洗い出せるようにしておく

受容

以上3つの対策を取らないことを「リスク受容」と言い、リスクが発生した時にそれを受け入れること。
このリスク受容には以下の2種類がある。

積極的リスク受容
消極的リスク受容

積極的リスク受容とは、リスク受容の事前準備をしておくことである。具体的には、代替計画（コンティンジェンシー計画）の準備や、予備予算の確保などである。
消極的リスク受容とは、つまり何も事前準備をせず、リスクが発生した時に対応策を考えることである。

上記4つのどれが最適かはケースバイケースである。リスクの発生確率、影響度合い、手持ちのリソーセス（人的・時間的・金銭的）に応じて、決めなければならない。場合によっては何もしない（消極的リスク受容）が最適であることもある。
また、リスク内容が既知なのか未知なのかも関係する。すなわち、既知のリスクであれば、それを回避したり軽減することができるが、未知のリスクに対しては基本的には転嫁と受容しか対策することができない。転嫁する場合でも、保険や契約内容にはスコープがある程度存在するはずなので、本当の未知のリスクへの対策はせいぜい予備リソーセス確保による積極的リスク受容くらいしかない。

チャンス対応策

活用

チャンスの原因となるものを引き寄せたり、チャンスの影響がプロジェクトに波及するようにすること。
【例】

能力の高い人材・機材などを導入する
流行りの技術を導入（インターネットやビッグデータ）したり、成長著しい市場に参画する*2

第三者と協力することで、チャンス発生確率を高めたり、新たなチャンスを引き寄せたりすること。
【例】

他社との協業

強化

チャンス発生時の影響を高めること。

受容

チャンス受容とは、何もせず、チャンスが到来した時にそれを受け入れることである。

表にまとめると以下のようになる。

	リスク	チャンス
発生確率	回避	活用
第三者	転嫁（移転）	共有
影響	軽減	強化

*1:余談であるが、「リスク転嫁」と「責任転嫁」は別物である。例えば、リスクがあるモジュールの責任部署を他部署ににすることは、責任転嫁することにより自部署が責められるリスクを転嫁しているだけであり、プロジェクトのリスクは全く転嫁されていない。どこの部署が責任を取ろうが、そのリスクは発生するのである。このときに、「他部署の方が本件に精通しているから」と言って、リスク軽減を装って責任を転嫁するのは、サラリーマンの常套手段である（ただの私見）。

*2:勿論、これが自社にとって経験の少ないものである場合、導入・参画することのリスクも発生する。流行言葉が大好きな上層部がいると、リスクがチャンスを圧倒する事態になるのは言わずもがなである。

2017-12-31

RISCとCISC（デジタル乗算器を具体例に）

応用情報技術者試験

ワイヤードロジック方式とマイクロプログラム方式

プロセッサの種類には、大別して

ワイヤードロジック方式
マイクロプログラム方式

の2種類があります。
ある演算を行うとき、
ワイヤードロジック方式ではハードで直接演算を行い、
マイクロプログラム方式ではより小さい演算に分解し、それぞれをハードで演算します。
「ワイヤード」とは「配線された、回路が組まれた」という意味ですから、
ワイヤードロジック方式の方では、ハードに専用の回路が用意されていて、
マイクロプログラム方式の方では、より小さな命令でプログラムする
と考えると、覚えやすいでしょう。

CISCとRISC

それゆえ、ある程度の大きな演算を行うとき、
ワイヤードロジック方式では、対応する命令があるのに対して、
マイクロプログラム方式では、対応する命令がないので、複数の命令で処理を行います。
前者をCISC(Complex Instruction Set Computer)、後者をRISC(Reduced Instruction Set Computer)と呼びます。

Complex: 複雑な
Reduced: 縮小した
Instruction: （プログラム用語としての）命令

という意味ですから、
CISCの方が複雑な演算の命令を持っていて、
RISCの方はそれを持っていない
と考えると、覚えやすいかも知れません。

デジタル乗算器

具体例として、デジタル乗算器について考えてみます。
「デジタル乗算器」とは、2つの数値を入力として、その乗算結果を出力する演算器のことです。
2進数の場合、この演算は足し算を複数組み合わせるだけで実装することができます。
（イメージとしては掛け算の筆算の感じです）
そしてこれは、足し算を行う回路（全加算回路）を複数組み合わせることで
ハード的に構成することもできます。

従って、ワイヤードロジック方式のCISCプロセッサでは、乗算器はハードで用意されており、
マイクロプログラム方式のRISCプロセッサでは、乗算器は加算命令を複数回使ってソフトで演算します。

https://www.yonago-k.ac.jp/denki/lab/nitta/lecture/E3_digital/note/note10.pdf
こちらの資料の1ページ目では、乗算の筆算が説明されています。

http://www.ai-l.jp/Res/LB7.Arithmetic.pdf
こちらの資料の19ページ以降では、乗算器の説明がされています。

2017-12-29

浮動小数点数に関係する誤差まとめ

応用情報技術者試験

打切り誤差

説明

PC上で数値を扱うということは、記憶装置（メモリ）に数値を記録させるということ
記憶装置は有限個しかないのだから、無限に続く数値（循環小数で表記される有理数や、無理数）を記録させようとすると、どうしても途中で桁を打ち切らなければならない
この「途中で桁を打ち切る」ことにより発生する誤差を打切り誤差と呼ぶ

例

1/3 = 3.3333333... → 3.3333333として記録される（有効桁数が8桁の場合）
円周率 = 3.14159265... → 3.1415926として記録される（有効桁数が8桁の場合）

丸め誤差

説明

無限に続く数値でなくでも、有効桁数に入りきらなければ、入らない分は削除されてしまう
- その時に、入らない部分を切り捨てるのか、切り上げるのか、四捨五入するのかは、演算装置が決める
この「入らない分を削除する」ことにより発生する誤差を丸め誤差と呼ぶ

例

2.0000001÷2 = 1.00000005 → 1.0000001として記録される（有効桁数が8桁で、9桁目以降は四捨五入する場合）
8.9999999 + 1.0000002 = 10.0000001 → 10.000000として記録される（有効桁数が8桁で、9桁目以降は四捨五入する場合）

情報落ち

説明

2つの数値同士を演算するとき、2値間の絶対値の大きさ（オーダー）が大きく離れている場合、演算結果の値には絶対値の大きい方の有効桁数が採用される
その時に、演算結果に丸め誤差が発生したために、演算結果が2値の内の絶対値が大きい方と全く同じになり、絶対値が小さい方の数字がなかったことにされてしまうことがある
この「絶対値の小さい方の数字がなかったことにされてしまう（＝その数値があったという情報が無くなってしまう）」ことにより発生する誤差を情報落ちと呼ぶ

例

1.0000001 + 0.00000001 = 1.00000011 → 1.0000001（有効桁数が8桁で、9桁目以降は四捨五入する場合）
- 指数表記を用いれば、1.0000000×10^1+1.0000000×10^-8 → 1.0000000×10^1

桁落ち

説明

丸め誤差を持つ2つの数値同士を演算するとき、2値が近い値の場合、演算結果のある桁以降の数字がすべて0になってしまうことがある
もし、演算した2つの数値の丸められる前の値に対して、同様の演算をした場合、この0になってしまったところは、実は0でなかった可能性がある（本当に0であった可能性もある）
そうすると、この0になってしまったところについては、本来の数字が分からないため、有効桁から除外され、結果、演算結果の有効桁数は、演算前の2値の有効桁数から減ってしまうことになる
この「2値が近い値であるために、有効桁数が減ってしまう」ことにより発生する誤差を桁落ちと呼ぶ

例

√14から10/3を減算するとき（丸める時は切り捨てとする）、
- 有効桁数が8桁だと、3.7416573 - 3.3333333 = 0.40832400となる
- 有効桁数が9桁だと、3.74165738 - 3.33333333 = 0.408324050となる
- 従って、有効桁数が8桁の時の最後の0は、有効桁数が9桁以上の時は5であり、この桁は有効ではない
- 結果、有効桁数が8桁の時の、演算結果の有効桁数は7桁であり、有効桁数が減っている

2017-12-10

3DCG手法の単語整理

応用情報技術者試験

アンチエイリアシング

英語では"anti-aliasing"。エイリアシング（aliasing）に対抗する（anti-）のでこう呼ばれる。
"alias"とは「別名」「偽名」という意味の名詞である*1が、
これが無線通信分野において、音声データをサンプリングした際に発生する
ノイズのことを指す用語として使われるようになった。
（つまり、サンプリング後のデータから取り出したい目的の音声データ以外の
「偽データ」ということ。）

これが画像分野にも応用され、「サンプリング（デジタル化）が起因のノイズが発生すること」を
広く「エイリアシング」と呼ばれるようになった。
ビットマップ画像データ等に見られる、線がギザギザになる現象は、
エイリアシングの一種である「ジャギー（jaggy）*2」であるが、
このジャギーを抑制する処理のことを、一般に「アンチエイリアシング」と呼んでいる。

モーフィング

英語では"morphing"となる。日本語版Wikipediaによれば、

変身・変化を意味する単語「メタモルフォルシス(metamorphosis)」の中間部分から命名されたという説と、
move(移動)+morphology(形態) の合成語であるとする説がある。

とあるが、英語版Wikipediaにはそのような表記はない。
研究社『英語語源辞典』によれば、

morph n. ｟1947 Hockett｠形態; 異形態. ◆(逆成)←MORPHEME: cf. ALLOMORPH.

とあるので、名詞としては1947年の時点で存在していたことになる。

シェーディング

影を意味する"shade"を動詞化した「陰を作る」という意味。Wikipediaが分かりやすい。

テクスチャマッピング

テクスチャとは元々「織物の質感・手触り（texture）」のこと*3。
Wikipediaによれば、テクスチャマッピングは、
元々、沢山のポリゴンから作られている3Dモデルに対して、見た目の質感を変えずに
ポリゴン数を削減するために発明された技法である。
これが次第に、質感を演出するために、モデル表面に画像を貼り付ける（mapping）することへと
意味が転化した。

ポリゴン

英語の"polygon"は「多角形」のこと*4。3DCG分野では、
立体を多角形の組み合わせでモデリングする技法、及びその多角形自体を指す。

メタボール

日本の3DCG研究の第一人者である大阪大学の大村皓一らが、この技術を「メタボール」と
呼んだことが始まり。技術自体の発明者はジム・ブリンであると言われている。
メタ（meta-）は「超」に相当する接頭辞なので、「メタボール」とは字面的には
「超ボール」ということである。

クリッピング

"clip"は「切り取る」という意味。
なお、日常生活で書類を留めるのに使っている「クリップ」も綴りは"clip"であるが、
先ほどの"clip"とは同綴異義語の関係である。

ライティング

光を点ける、光を当てるという意味の"lighting"から。

*2:英語で「とげとげ、ギザギザ」の意。

*3:織物は"textile"

*4:五角形は"pentagon"、六角形は"hexagon"。