講義資料
計算機数理科学特論
三井 斌友
（情報科学研究科）
[email protected]
http://www2.math.human.nagoya-u.ac.jp/~mitsui/
2004
年前期1
1
計算の歴史とコンピュータ本講の目的：“計算する機械 (computing machine)”としてのコンピュータを，計算法 (com- puting algorithm)の発展と照合させながら振り返り，将来を展望
参考書： 高橋秀俊，情報科学の歩み，岩波講座情報科学１，岩波書店，1983
1.1
計算の起源と発展• 人はなぜ“計算する”のだろうか？
• 古代文明と算術（算数，arithmetics）：岩波『数学辞典』第３版，1985
– エジプト – メソポタミア – 中国
• 数の四則演算と記数法
x+y, x−y, x×y, x/y for x, y ∈N, Q, R
実は記数法と密接に結びついている．漢数字やローマ数字で表現された数の四則演算 を考えてみよ．
例1: “壱萬四千八百参拾九に弐千五百七を加える”
例2: “MMMDCCLXIII からDCCCLXXVIII を引く”
これに対して，現代の10進数表現による
“14839 + 2507” や “3763−878” の表現と計算法の簡便さを思い浮かべよ．
算盤（そろばん，abacus） —最古の「計算道具」
• アルゴリズム algorithm
『岩波情報科学辞典』（長尾 真ほか編）, 1990による定義
“一般的な用語としては，問題を解くための計算法を意味する．この意味での使い方は かなり曖昧であって，数学的に厳密に定義することは困難である．アルゴリズムとプ ログラムはほぼ同じ意味で使われるが，プログラムが，あるプログラム言語で書かれ，
ただちに計算機で実行できるものを意味することが多いのに比べ，アルゴリズムのほ うは，どちらかといえば特定のプログラム言語までは意識しない計算手順や計算の方 法を意味することが多い．
論理学，数学基礎論，計算の理論などの分野においては，アルゴリズムという言葉は，
機械的に実行でき，有限時間内に必ず答を出して終了する計算規則という，かなり狭
2
く明確な概念を意味することが多い．このような意味でのアルゴリズムの概念を数学 的に定義する試みとしては，抽象プログラム機械，チューリング機械などいろいろな ものがある．”
算術計算も，長大・複雑になればアルゴリズムが必要 β 進数表現：二つの実数x1, x2 を基底 radixβ を使って
x1 = (sign1){d1×β−1+d2×β−2+· · ·+dn1 ×β−n1} ×βm1
= sign1
n
1
j=1
djβ−j
×βm1,
x2 = (sign2){e1×β−1+e2 ×β−2+· · ·+en2 ×β−n2} ×βm2
= sign2
n
2
j=0
ejβ−j
×βm2
条件（正規化条件 normalization ）
1≤d1, e1 ≤(β−1), 0≤dj, ej ≤(β−1) (j = 2, . . . , n1 orn2) を課せば，一意的に表現できる．
正規化浮動小数点数（コンピュータでの「実数」の表現）：（符号部）× （仮数部）×
（指数部）
β = 10 が日常的な十進法，
コンピュータの内部表現としてはβ = 2 （２進法）や β = 16（１６進法）が普通．
加減算: x1±x2 は本質的に同一．m1, m2 が等しくなるような調節をして，
n1
j=1
djβ−j +
n2
j=1
ejβ−j または
n1
j=1
djβ−j−
n2
j=1
ejβ−j が計算できればよい．
(i)j = 0, . . . , n(= max(n1, n2))について fj =dj +ej あるいはfj =dj−ej を計算 (ii) 正規化条件をみたすように調整（いわゆる桁上がりあるいは桁下がり）
乗算：
(sign1)
n1
j=1
djβ−j
×
(sign2)
n2
k=1
ekβ−k
= (sign1)(sign2)
n1+n2
l=0
fl β−l ここで
fl=
j+k=l
dj ek
ただし，桁上がりを考慮．
3
• 史上初のアルゴリズム？ユークリッド互除法 Euclidean algorithm
a, b∈N (a > b) のとき，gcd(a, b) （a, b の最大公約数greatest common divisor）を求 める方法
a≡r (modb) a を b で整除した剰余をr (0≤r < b) とする while b >0 do
begin a≡r (modb);
a:=b, b :=r end;
gcd =a;
1.2
計算する機械—
コンピュータ前史機械（手回し式計算機）による計算の着想と実現
• W. Schickard (1592 - 1636)
• B. Pascal (1623 - 1662)加減算の可能な計算機 (1642)
• G.W. Leibniz(1646 - 1716) 乗除算の可能な計算機 (1672)
• Algorithmをプログラムとして「読み込む」計算機
Ch. Babbage (1791 - 1871) の difference engine, analytical engine
• 最近まで使われていた手回し式計算機: タイガー計算器
4
