コンテンツへスキップ
Topos Uranos
日本語

位取り記数法

要約

この課では、各数字の値がそれの占める位置によって決まる位取り記数法を学ぶ。すべての自然数が任意の底 b≥2b \geq 2 においてただ一通りに書けることを、底で繰り返し割るという手順によって証明し、1010 進法と 22 進法、88 進法、1616 進法との間で、またそれら三つの間では二進数字をまとめることで、数を変換する方法を示す。和と積がどの底でも 1010 進法と同じ規則で計算されることを示し、倍数判定法がなぜ成り立つのかを説明してほかの底に拡張し、最後に記数法の歴史と、コンピュータにおける 22 進法の利用について述べる。

学習目標

  1. 位取り記数法を理解し、任意の底で書かれた数の値を計算すること。
  2. bb 進法による表示の存在と一意性を証明し、それを逐次の割り算によって求めること。
  3. 22 進法、88 進法、1010 進法、1616 進法の間で数を変換し、22 進法で足し算と掛け算をすること。
  4. b−1b - 1 と b+1b + 1 の倍数判定法（bb 進法における）を正当化し、1010 進法やほかの底で適用すること。

位取り記数法

20252025 と書くとき、四つの数字を足しているのではなく、各数字にその位置で決まる 1010 の累乗を掛けている。最初の 22 は二つの千を表し、二番目のものは二つの十を表す。数字 00 は百がないことを示し、その場所を占めることで、ほかの数字をそれぞれ本来の位置に保つ。

2025=2⋅103+0⋅102+2⋅10+52025 = 2 \cdot 10^3 + 0 \cdot 10^2 + 2 \cdot 10 + 5

この原理は位取り記数法と呼ばれ、数 1010 には依存しない。b≥2b \geq 2 が自然数であるとき、これを底といい、bb 進法の数字とは数 0,1,…,b−10, 1, \ldots, b - 1 のことである。数字の列 ak,ak−1,…,a1,a0a_k, a_{k-1}, \ldots, a_1, a_0（ただし ak≠0a_k \neq 0）は次の数を表す。

n=akbk+ak−1bk−1+⋯+a1b+a0n = a_k b^k + a_{k-1} b^{k-1} + \cdots + a_1 b + a_0

数字は左から右へ並べて書き、底は添字で示す。たとえば 341253412_5 は、55 進法で数字 33、44、11、22 によって書かれる数であり、「34123412（55 進法）」と読む。aia_i は位 ii を占めるといい、位は右から 00 を起点に数える。添字がなければ、数は 1010 進法で書かれている。22 進法には数字が二つ、00 と 11 しかなく、これをビットという。1616 進法では十六個の数字が必要であり、ふつうの十個の数字に文字 A、B、C、D、E、F を加え、これらはそれぞれ 1010、1111、1212、1313、1414、1515 を表す。

さて、bb 進法で書かれた数の値は、bb を共通因数として何度もくくり出すことで計算でき、累乗の計算を避けられる。これがホーナー法である。

補題ホーナー法

すべての kk とすべての数 a0,a1,…,aka_0, a_1, \ldots, a_k について、積 aibia_i b^i の和は、aka_k から始めて、kk 回、次の操作を繰り返すことで得られる。すなわち、bb を掛け、次の係数を足す操作である。

akbk+ak−1bk−1+⋯+a1b+a0=(⋯((akb+ak−1)b+ak−2)⋯ )b+a0a_k b^k + a_{k-1} b^{k-1} + \cdots + a_1 b + a_0 = (\cdots((a_k b + a_{k-1}) b + a_{k-2}) \cdots) b + a_0

証明は kk についての帰納法であり、分配法則しか使わない。この式は x=bx = b における多項式 akxk+⋯+a1x+a0a_k x^k + \cdots + a_1 x + a_0 の値であり、多項式の代数についての課で再び取り上げる。

証明

  1. a0=a0a_0 = a_0

    初段：k=0k = 0 のとき、両辺はともに a0a_0 となる。法則は何の操作も行わないからである。

  2. ckbk+⋯+c1b+c0=(⋯(ckb+ck−1)⋯ )b+c0\dato{h}{c_k b^k + \cdots + c_1 b + c_0 = (\cdots(c_k b + c_{k-1}) \cdots) b + c_0}

    帰納法の仮定：k+1k + 1 個の項からなり、係数は任意で、累乗 bkb^k までの和のすべてについて、法則が成り立つ。

  3. ak+1bk+1+⋯+a1b+a0=(ak+1bk+⋯+a2b+a1) b+a0a_{k+1} b^{k+1} + \cdots + a_1 b + a_0 = \resaltar{(a_{k+1} b^k + \cdots + a_2 b + a_1)} \, b + a_0

    bk+1b^{k+1} までの和を考える。分配法則により、最後の項を除くすべての項から bb を共通因数としてくくり出す。

  4. ak+1bk+1+⋯+a1b+a0=((⋯(ak+1b+ak)⋯ )b+a1) b+a0a_{k+1} b^{k+1} + \cdots + a_1 b + a_0 = \resaltar{((\cdots(a_{k+1} b + a_k) \cdots) b + a_1)} \, b + a_0

    括弧の中は、係数を ci=ai+1c_i = a_{i+1} とすれば帰納法の仮定の形をしている。法則によってそれを書き換え、bb を掛けて a0a_0 を足すと、k+1k + 1 についての法則が得られる。帰納法の原理により、すべての kk について成り立つ。

例5 進法で書かれた数の値

55 進法で 341253412_5 と書かれる数を二通りの方法で計算せよ。位の値を足し合わせる方法と、ホーナー法による方法である。

証明

  1. 34125=3⋅53+4⋅52+1⋅5+23412_5 = \resaltar{3} \cdot 5^3 + \resaltar{4} \cdot 5^2 + \resaltar{1} \cdot 5 + \resaltar{2}

    各数字に、その位置に対応する 55 の累乗を掛ける。すなわち 535^3、525^2、55、11 である。

  2. 3⋅125+4⋅25+1⋅5+2=375+100+5+2=4823 \cdot \resaltar{125} + 4 \cdot \resaltar{25} + 1 \cdot 5 + 2 = \resaltar{375} + \resaltar{100} + 5 + 2 = \dato{v}{482}

    累乗と積を計算し、足し合わせる。

  3. 34125=((3⋅5+4)⋅5+1)⋅5+23412_5 = \resaltar{((3 \cdot 5 + 4) \cdot 5 + 1)} \cdot 5 + 2

    ホーナー法では、最初の三つの項から 55 を共通因数としてくくり出し、次に括弧の中の最初の二つの項からくくり出す。

  4. 3⋅5+4=19,19⋅5+1=96,96⋅5+2=482\resaltar{3 \cdot 5 + 4} = 19, \quad \resaltar{19 \cdot 5 + 1} = 96, \quad \resaltar{96 \cdot 5 + 2} = \resaltar{482}

    内側から外側へ計算する。各結果に底を掛け、次の数字を足す。累乗を一つも使わずに同じ値が得られる。