情報数学1 第3-1章 多進法の原理と変換算法 香川大学工学部 富永浩之 [email protected] 概 要 ■ 自然数の記数法 位取記数法、多進法と多進法 ■ 多進法の原理 切捨 切上 四捨五入 ガウス記号 ■ 多進数への変換 多進数への変換 ■ 多進数からの変換とホーナー法 多進数からの変換 ■ 多進法の例題 ホーナー法 第01節 [1] 自然数の記数法 ● 自然数の記数法 何らかの体系的な規則に従った記号列により、 数を表記する方法を総称して記数法[algorism]という。 ● 位取記数法 空位0で、数字の位置である桁[digit]を区別する。 有限個の数字で幾らでも大きな数を表記できる。 ● 多進法 rずつ束にすることを段階的に繰り返し、 0~r-1 のr種の数字を使って自然数を表す方法を、 rを基数[radix]とする多進法または単にr進法という。 第01節 [2] 数の歴史 ● 古代 ○ インド ○ バビロニア ○ ローマ ○ 中国 0の発見、10進数、数字0~9の使用 60進数、楔形文字の数字 木の棒の刻み目、ローマ数字の起源 3999まで、計算に不向き 漢数字、位ごとに別の漢字、算盤の使用 ● 中世 ○ アラビア ○ ヨーロッパ インドのアラビア数字の普及 アラビア商人は東西文化の懸け橋 アラビア商人からイタリア商人へ フィボナッチ「算盤の書」 筆算の解説書 第02節 [1] 十進法系と二進法系 ● 十進法系 ● 二進法系 ● 三進法系 人間の手指の本数から 電気信号のON/OF 正零負の場合分けから(等号、天秤) 10 2 8 16 10 2 8 16 0 0 0 0 8 1000 10 1 1 1 1 9 1001 2 10 2 2 10 3 11 3 3 4 100 4 5 101 6 7 10 2 8 16 10 2 8 16 8 16 10000 20 10 24 11000 30 18 11 9 17 10001 21 11 25 11001 31 19 1010 12 A 18 10010 22 12 26 11010 32 1A 11 1011 13 B 19 10011 23 13 27 11011 33 1B 4 12 1100 14 C 20 10100 24 14 28 11100 34 1C 5 5 13 1101 15 D 21 10101 25 15 29 11101 35 1D 110 6 6 14 1110 16 E 22 10110 26 16 30 11110 36 1E 111 7 7 15 1111 17 F 23 10111 27 17 31 11111 37 2進法 ‥ 0と1の数字(ビット列) 8進法 ‥ 0~7の数字 2進法の3桁ごとに1つの数字 16進法 ‥ 0~9, A~Fの数字 2進法の4桁ごとに1つの数字 1F 第03節 [1] 多進数への変換 ● 多進数の基底表現と整除表現 ○ 基底表現 46 = 1201[3] = 1×33+2×32+0×31+1×30 多進数の直接的表現 ○ 整除表現 46 = 1201[3] = ((1×3+ 2)×3+0)×3+1 効率的な変換算法のための式 ● 基底表現と整除表現の計算回数 ○ 基底表現 ○ 整除表現 乗算 p(p-1)/2回 乗算 p-1回 加算 p-1回 加算 p-1回 ● 基底表現の原理 除法の定理の連続的な適用 46÷3=15‥1 15÷3=5‥0 第03節 [2] 多進数への変換 ● 多進数への変換の算法 [0] 10進数を整商の初期値として右上に書く。基数 を左端に書く。 [1] 整商が基数 以上の間、[2][3]の処理を繰り返す。 [2] 基数 による剰余を下段に書く。 [3] 基数 による整商を左に書く。 [4] 整商が基数 未満になったら、各剰余を 進法での各桁の数字に直す。 [5] 各桁での数字を左から順に並べると多進数を得る。 3 0 1 5 15 46 1 2 0 整商の列 1 ⇒ 1201[3] 16 剰余の列 2 47 764 2 15 12 2 2 0 1 2 4 9 19 38 77 1 0 0 1 1 0 1 155 1 ⇒ 10011011[2] F C ⇒ 2FC[3] 第04節 [1] 多進数からの変換 ● 多進数からの変換の算法 [0] 多進数の各桁の数字を並べる。 [1] A→10, B→11 のように、桁の数字を数値に直しておく。 [2] 最上位桁の数値 をそのまま初期値とし、最下段に書く。 [3] 左下のそれまでの途中結果に、基数 を乗算し、次の桁の数値の下に書く。 [4] 桁の数値と乗算した値を加算し、最下段に書く。 [5] 最下位桁の値を加算した結果が、求める10進数である。 1 3 1 1 2 1 2 2 2 各桁 0 2 3 15 51 153 基数と乗算 5 17 51 155 加算 1 0 2 10 12 0 0 1 1 1 2 4 8 18 38 76 154 2 4 9 19 38 77 155 A B 11 数字を数値に 24 408 2 34 419 第07節 [1] ホーナー法による整式の求値 ● 整式の基底表現と整除表現 ○ 基底表現 f(X) = 2×X3-3×X2+0×X1+4×X0 ○ 整除表現 f(X) = ((2×X+ 3)×X+0)×X+4 f(X) = 3X5 -7X4 +6X3 -7X2 +0X -3 f(2)=((((3×2-7)×2)+6)×2-7)×2+0)×2-3 = +1 +3 +2 +6 +3 組立除法 -7 +6 -7 0 -3 降冪順の係数 -2 +8 +2 +4 代入値の乗算 -1 +4 +1 +2 +1 係数との加算 整式への値代入を整除表現で効率的に求める 分配律の連続適用で乗算回数を大幅に減らす 西洋ではホーナーが発見 東洋(中国)ではそれ以前(九章算術)から既知 第07節 [2] ホーナー法の応用 係数や代入値が一般の実数や複素数でも使える (効力を発揮) f ( X ) X 5 2 X 4 3X 3 2 X 2 3X 2 f (1 2 ) 7 3 2 +1 -1+√2 +1 +2 -3 -2 +3 +2 -1+√2 +1 +2-2√2 -4+2√2 +5-3√2 +1+√2 -2 -2√2 -1+2√2 +7-3√2 f ( X ) X 5 2 X 4 2 X 3 7 X 2 3X 8 f (2 i) 7 2i +1 -2-i +1 -2i +1 +2 -2 -7 +3 -8 -2 -i -1 +2i +8 -i -3 +i +1 -2i -i -3 +2i +1 -i +i -7 -2i 第05節 [1] 多進法の原理 ● 多進法の原理 𝚲=𝒂𝒑−𝟏 𝒂𝒑−𝟐 ‥𝒂𝟏 𝒂𝟎 𝒓 ; 𝟎 ≤ 𝒂𝒌 ≤ 𝒓 − 𝟏, 𝒂𝒑−𝟏 ≠ 𝟎 ・ 自然数 M に対し、2以上の基数 r による 多進数表記 Λ の各桁 𝑎𝑘 は一意に決まる ・ 除数 r による整除演算の繰返しで、下位桁から計算できる 𝒑−𝟏 𝑴 = 𝒂𝒑−𝟏 𝒓𝒑−𝟏 + 𝒂𝒑−𝟐 𝒓𝒑−𝟐 + ‥ + 𝒂𝟏 𝒓 + 𝒂𝟎 = 𝑴 = (‥(𝒂𝒑−𝟏 𝒓 + 𝒂𝒑−𝟐 )𝒓 + ‥ + 𝒂𝟏 )𝒓 + 𝒂𝟎 𝒂𝒌 𝒓𝒌 𝒌=𝟎 ・ 多進数表記 Λ が表す自然数は、基底表現を計算して得られる ・ 実際の計算では、整除表現で求める方が効率的である 第06節 [1] 多進法の応用問題 ● 着目点 ・ 桁数による大きさの見積り (p 桁の r 進数 A の10 進数での値 T は、 rp≦T≦ rp-1 -1 の範囲にある) ・ 剰余の性質(加法・乗法・累乗との分配律) ・ 各桁の数字 ak は基数 r を越えない自然数 0≦ ak <r ・ 基数 r が未知数のとき、 m 桁の r 進数は、 r に関する m-1 次の整式とみることができる ・ ある数を r1 , r2 進法で表した値を A1 , A2 とすると、 r1<r2 ならば、 A1の桁数≧ A2 の桁数 第06節 [2] 多進法の応用問題 【例題1】 365[10] は、何進法で表すと 555 になるか。 題意は、 365[10]=555[r] と表わされる。 基底表現より、二次方程式 5r2+5r+5=365 が立つ。 整理すると、 (r-8)(r+9)=0 となる。これを解くと、 r=8,-9 となる。 ここで、多進数の数字として 5 が現れているから、基数は 6 以上である。 すなわち、 r≧6 であるから、 r=8 となる。よって、8進法である。 別解として、多進数の性質を用いて、基数の候補を絞っていく。 この方法の場合、最後に、十分条件として、実際に題意を満たすことを示す必要がある。 まず、数字に 5 が使われているから r≧6 である。 また、 555[r]=365[10]<555[10] より r≦9 となる。 さらに両辺を 5 で割って、 73[10]=111[r] を得る。 さらに両辺から 1 を引いて、 72[10]=110[r] を得る。 よって、 r は 72 の約数である。すなわち、 6, 8, 9 のいずれかである。 また、 100[r]=r2<110[r]=72, 200[r]=2r2>111[r]=73 より、 r=8 と求められる。 実際、 365[10]=555[8] が成立し、題意を満たす。 第06節 [3] 多進法の応用問題 【例題2】 80[10] を何進法で表すと各桁が同じ数字の2つ以上の並びになるか。 4 3=64≦80<52=125 より、 80が r 進表記で 3 桁以上になるのは、 r≦4 のときである。 80[10]=1100[4]=2222[3]=1010000[2] より、 r=3 は題意に適する。 80が r 進表記で数字 a が 2 桁並ぶ数となるとすると 80=a(r+1) である。 ただし 、 1≦a≦r-1 である。 したがって、 a と r+1 は 80 の約数であり、 a は 80-a の約数である。 すなわち、 r の候補は 79, 39, 19, 15, 9, 7 であり、 80[10]=11[79]=22[39]=44[19]=55[15]=88[9] なお、 r=7 のときは、 a=10>r-1 より不適。 以上をまとめると、 r=3, 9, 15, 19, 39, 79 となる。 第06節 [4] 多進法の応用問題 【例題3】 u 進法で表すと 47 となり、v 進法で表すと 74 になるような、 u と v の組を求めよ。 題意から、 47[u]=74[v] より 4u+7=7v+4 で、 一次不定方程式 4u-7v=-3 を立てる。 4u-7v=4(u-2v)+v w=u-2v とおいて 4w+v=-3 これから、具体解 w=0, v=-3 さらに、 u=w+2v=-6 これから、整数パラメタ t を用いて、 一般解 <u,v>=<-6+7t, -3+4t> が得られる。 ここで、多進法の桁の数字より 8≦v<u でなければならない。 よって、 8≦-3+4t<-6+7t より t≧3 を得る。 ここで、 t-3 を改めてパラメタ t と置き直して、 解 <u,v>=<15+7t, 9+4t> ; t≧0 を得る。 第06節 [5] 多進法の応用問題 【例題4】 1108 を r 進法で表すと 31a2 となるとき、a と r を求めよ。 r 進数の表記の条件から、大小関係を用いての範囲を絞り込む。 題意より、 3000[r]=3r3<1108<4000[r]=4r3 が成立するから、 247<r3<369+1/3 となる。 73=343 より、 r=7 となる。 下図のホーナー法より (1108-2)÷7=158=31a[7] で a=158%7=4 7 0 3 22 3 1 158 1108 a 2 別解として、多進数の性質から求める。 1108=31a2[r] の両辺から2を引くと、 1106=31a0[r] となる。 したがって、基数 r は、 1106=2×7×79 の約数である。 r 進数が 10 進数より大きくなっているから、 r≦9 であり、 r=7 と決まる。 より、 158=31a[7] となる。 158=7×22+4 より、 a=4 と求まる。 実際、 1108=3142[7] が成立し、題意を満たす。 第08節 [1] 多進数における数字の使用回数 【例題1】 0から63までの64個の自然数を2進数で表したとき、 0と1の数字がそれぞれ何個必要となるか。 【例題2】 0から99までの100個の自然数をr進数で表したとき、 全体として何個の数字が必要になるか。 r=2~10の場合の解法を整理し(あるいは一般的に解き)、 結果を表にまとめよ。
© Copyright 2024 ExpyDoc