符号理論
\( \def\vector#1{\boldsymbol{#1}} \)

基数変換

(since 2019年2月2日) Takami Torao
  • このエントリーをはてなブックマークに追加

概要

数の表現ですべての数値に一意の記号を割り当てようとすることは非現実的である。代わりに、古代から有限の記号の組み合わせで任意の数を表現する記数法 (numerical notation) が用いられてきた。現代で一般的に使用されている記数法は位取り記数法 (positional notation) である。この方法はゼロ記号を含む \(n\) 個の記号を並べて数を表し、記号の位置 (位) によって記号の値が右から順に \(n\) 倍ずつ異なるという原理1に基づいている。位取り記数法に基づく数値システムにで定義された基底の数 \(n\) を基数 (radix) と呼び、基数 \(n\) による数の表現を \(n\) 進数表現と呼ぶ。例えば 10 進数表現での数列 \(3,9,1\) は \(3\times 10^2+9\times 10^1+1\times 10^0\) を意味している (標準的な位取り記数法はすべての位に同じ基数を使用する)。

現代社会では数を 10 進数で表現している一方で、一般的なコンピュータは数を 2 進数で扱っている。このように基数の混合する数値システムでは、ある値を \(r_a\) 進数表現の数列 \(A\) から \(r_b\) 進数表現の数列 \(B\) に変換する操作が必要となる。

\(XYZ\) の数列が \(n\) 進数で表現された数であることを示すために \(XYZ_n\) を使うことが多いが、添え字と混在するケースでは \(XYZ_{(n)}\), \(XYZ|_{n}\) のような表記もある。

Table of Contents

  1. 概要
  2. 基数変換
    1. 整数と基数 \(r\) の数列の変換
    2. 小数と基数 \(r\) の数列の変換
    3. 基数の変換 [under construction]
  3. 参照
  • 110進数位取り記法はインドを起源としてアラビア数字とともに中世イスラムを経由してヨーロッパに伝わった。古代の文明はそれぞれで記数法を持っていたが、大きな数値は歴の作成以外に必要なかったため、位取り記数法は必ずしも必要とされていなかった。例えばローマ数字で 28 は XXVIII だが、これは大きな数を表すには不便である [2,3]。

基数変換

ある数値 \(X\) と、基数 \(r\) における \(X\) の数列表現 \((x_\infty \ldots x_2 x_1 x_0 . x_{-1} x_{-2}\ldots x_{-\infty})_{(r)}\) との関係は式 (\(\ref{conv_radix}\)) のように表すことができる。\[ \begin{equation} X = \ldots + x_2 r^2 + x_1 r^1 + x_0 r^0 + x_{-1} r^{-1} + x_{-2} r^{-2} + \ldots = \sum_{i=-\infty}^\infty x_i r^i \label{conv_radix} \end{equation} \] ここでこの記事では添え字 \(i\) の小さい数がより低い位を示していることに注意 (リトルエンディアン)。位取り記数法では次のような表現上の規則を適用する。

  1. \(i\) が負となる境界に小数点を配置し、それより右側は小数を表していることを示す。

  2. それ以上の高い位がすべてゼロ記号となる桁、およびそれ以下の低い位がすべてゼロ記号となる桁の表記を省略する: e.g., \(X=\ldots 0013.50200\ldots = 13.502\)

  3. \(X\) が負の場合にすべての \(x_i\) が 0 以下となるが、最左桁の左に単一のマイナス記号を付与することですべての \(x_i\) が 0 以下であることを表現する。ここで \(|X|\) に対する基数 \(r\) の数列を求めた結果にマイナス記号を付与しても同じ結果となることに注意: e.g., \(X=(-1)(-3).(-5)(0)(-2) = -13.502 = -|X|\)

数値 \(X\) と、基数 \(r\) での \(X\) の数列表現を相互に変換する基本的な手段は The Art of Computer Programming [1] に記載されている。この方法は 1) 整数部と小数部を分離して計算し、後に連結あるいは加算する、2) 絶対値に対して変換を行い、正負の符号は最後に元の値から付与する、という手順で行う。

整数と基数 \(r\) の数列の変換

ある正の整数 \(A \ge 0\) と、基数 \(r\) での \(A\) の数列表現 \((a_\infty\ldots a_2 a_1 a_0)_{(r)}\) (つまり \(r\) 進数表現) との関係は式 (\(\ref{radix_rel}\)) のように表すことができる。\[ \begin{equation} A = \ldots + a_2 r^2 + a_1 r^1 + a_0 r^0 = \sum_{i=0}^\infty a_i r^i \label{radix_rel} \end{equation} \] 式 (\(\ref{radix_rel}\)) より、整数 \(A\) が与えられたとき、対応する基数 \(r\) の表現 \((\ldots a_2 a_1 a_0)_{(r)}\) は式 (\(\ref{taocp_a1}\)) ように求めることができる。\[ \begin{equation} \left\{ \begin{array}{rcl} a_0 & = & A \bmod r \\ a_1 & = & \lfloor A / r \rfloor \bmod r \\ a_2 & = & \lfloor \lfloor A / r \rfloor / r \rfloor \bmod r \\ \vdots \end{array} \right. \label{taocp_a1} \end{equation} \] この計算は \(\lfloor \ldots \lfloor\lfloor A/r \rfloor /r \rfloor \ldots / r \rfloor \bmod r\) が 0 となったときに打ち切ることができる (それ以降がすべて \(a_i=0\) となることは自明である)。

同様に、基数 \(r\) の表現 \((a_m \ldots a_2 a_1 a_0)_{(r)}\) が与えられたとき、対応する整数 \(A\) は式 (\(\ref{taocp_a2}\)) のように求めることができる。\[ \begin{equation} A = ((\ldots(a_m r + a_{m-1})r + \ldots)b + a_1)b + a_0 \label{taocp_a2} \end{equation} \]

小数と基数 \(r\) の数列の変換

ある小数 \(0 \lt B \lt 1\) と、基数 \(r\) でのその数列表現 \((0.b_{-1}b_{-2}\ldots b_{-\infty})_{(r)}\) との関係は式 (\(\ref{fconv})\) のように表すことができる。\[ \begin{equation} B = b_{-1} r^{-1} + b_{-2} r^{-2} + \ldots = \sum_{i=-1}^{-\infty} b_i r^i \label{fconv} \end{equation} \] 式 (\(\ref{fconv}\)) より、小数 \(0 \lt B \lt 1\) が与えられたとき、対応する基数 \(r\) の表現 \((0.b_{-1} b_{-2} b_{-3} \ldots)_{(r)}\) は式 (\(\ref{taocp_b1}\)) のように求めることができる。\[ \begin{equation} \left\{ \begin{array}{rcl} b_{-1} & = & \lfloor Br \rfloor \\ b_{-2} & = & \lfloor \{Br\}r \rfloor \\ b_{-3} & = & \lfloor \{\{Br\}r\}r \rfloor \\ \vdots \end{array} \right. \label{taocp_b1} \end{equation} \] ここで \(\{x\}=x \bmod 1=x -\lfloor x \rfloor\) (つまり \(x\) の小数部) とする。この計算は \(\{\ldots\{Br\}\ldots r\}=0\) となったときに打ち切ることができるが、多くの場合、小数の基数変換は無限小数となることから、現実的にはある程度の桁で切り捨てや丸めを行う必要がある。

同様に、基数 \(r\) の表現 \((0.b_{-1}b_{-2}\ldots b_{-m})_{(r)}\) が与えられたとき、対応する小数 \(B\) は式 (\(\ref{taocp_b2}\)) のように求めることができる。\[ \begin{equation} B = \left((\ldots (b_{-m}/r + b_{-m+1})/r + \ldots + b_{-2})/r + b_{-1}\right) / r \label{taocp_b2} \end{equation} \]

基数の変換

基数 \(r_x\) で表されたある数値 \(A\) の数列 \((\ldots x_1 x_0)_{(r_x)}\) を基数 \(r_y\) の数列 \((\ldots y_1 y_0)_{(r_y)}\) に変換する操作について考える。

表現上の数列 \(\vector{X}\) と \(\vector{Y}\) は本来的な数値を介して以下のように表すことができる。\[ N = \sum_{i=0}^{n_a-1} a_i r_a^i = \sum_{i=0}^{n_b-1} b_i r_b^i \]

一般的に基数変換は \(\vector{A}\) から \(N\) を求め \(\vector{B}\) に変換する。

def convert(a:Array[Int], r_a:Int, r_b:Int):Array[Int] = {
  val n = a.foldRight(BigInt(0)) { case (a_i, sigma) => sigma * r_a + a_i }
  var remaining = n
  val b = Buffer[Int]()
  while(remaining != 0){
    b.append((remaining % r_b).toInt)
    remaining /= r_b
  }
  b.toArray
}

\(r_a\), \(r_b\) が 2 のべき乗であればシフト演算とビット演算を使用して

\(\vector{A}\) を基数 \(r_b\) で表すために十分かつ最も小さい桁数 \(n_b\) を求める。まず、\(r\), \(n\) が決定している場合に取り得る最大値 \(N_{\rm max}\) は基数 \(r\) の桁数 \(n\) によるべき乗より 1 つ小さい値であることから、それぞれの最大値は以下のように表される。\[ \left\{ \begin{array}{lcl} N_{{\rm max} \ a} & = & r_a^{n_a} - 1 \\ N_{{\rm max} \ b} & = & r_b^{n_b} - 1 \end{array} \right. \] 基数 \(r_b\) の表現において桁数 \(n_b\) を用いて \(N_{{\rm max}\ a}\) を表すことができるためには: \[ N_{{\rm max}\ a} \le N_{{\rm max}\ b}\\ r_a^{n_a} - 1 \le r_b^{n_b} - 1 \\ n_b \ge \frac{\log r_a}{\log r_b} n_a \] \(n_b\) は上記の条件を満たす最も小さい整数であるため以下の式で求めることができる。\[ n_b = \left\lceil \frac{\log r_a}{\log r_b} n_a \right\rceil \] しかし、実際のプログラミングでの ceil() は浮動小数点演算の誤差に非常に敏感であり、log() も誤差の大きな演算である。例えば: \(r_a=3\), \(n_a=5\) での最大値 \(N_{{\rm max}\ a} = [2,2,2,2,2]\) に対して \(r_b=243\) では \(\vector{B}=[242]\), \(n_b=1\) だが、演算の誤差により 2 となる。

scala> math.log(3) * 5 / math.log(243)
res31: Double = 1.0000000000000002

特に \(r_a\), \(r_b\) が 2 のべき乗で決定しているのであれば対数を使用せずに計算した方が良い。

参照

  1. Donald E.Knuth, The Art of Computer Programming Volume 2 Seminumerical Algorithms, KADOKAWA (2015)
  2. 青本和彦, et al. 岩波数学入門辞典. 岩波書店 2005.
  3. 小数について（その１）－小数の起源や記法等はどうなっているのか－