概要

情報技術の基礎として理解しておきたい離散数学のうち、基数変換、補数表現、小数表現、数値誤差、集合演算を整理する。

離散数学は、計算機が数値や論理をどのように扱うかを理解するための土台となる。
特に、\(2\) 進数、補数、浮動小数点数の誤差は、計算問題だけでなくプログラムの挙動を理解するうえでも重要となる。

この記事の構成

• 基数変換
  基数変換とは、ある基数で表された数を、別の基数の表現へ変換すること。
• 補数表現（負の数の表現）
  補数表現（負の数の表現）の仕組みと要点を具体例から整理。
• 小数表現
  固定小数点数表現：小数点の位置を固定して数値を表す方式。
• 基数変換の誤差
  基数変換の誤差の仕組みと要点を具体例から整理。
• 数値演算の誤差
  丸め誤差：指定された桁数で数値を扱うために、四捨五入、切捨て、切上げなどで下位の桁を削ることによって生じる誤差。
• 集合
  要素が集合に属するかどうかを命題として見ると、集合演算と論理演算の対応を整理しやすい。

基数変換

基数変換とは、ある基数で表された数を、別の基数の表現へ変換することを指す。
基数は、桁上がりする基準となる数で、\(2\) 進数なら \(2\)、\(10\) 進数なら \(10\)、\(16\) 進数なら \(16\) となる。

• 例 \(1\) : 整数の基数変換 \(10\) → \(2\)

  \((25)_{10}\) の基数を \(2\) に変換。
  整数部の変換では、変換元の数を変換先の基数で割り、余りを下から上へ読む。

  \(25 \div 2 = 12 \) 余り \( 1 \)
  \(12 \div 2 = 6 \) 余り \( 0 \)
  \(6 \div 2 = 3 \) 余り \( 0 \)
  \(3 \div 2 = 1 \) 余り \( 1 \)
  \(1 \div 2 = 0 \) 余り \( 1 \)
  → 最後の剰余から順に並べて \((11001)_{2}\)

• 例 \(2\) : 整数の基数変換 \(10\) → \(16\)

  \((555)_{10}\) の基数を \(16\) に変換。
  \(16\) 進数では、\(10\) から \(15\) までを \(A\) から \(F\) で表す。

  \(555 \div 16 = 34 \) 余り \( 11(B) \)
  \(34 \div 16 = 2 \) 余り \( 2 \)
  \(2 \div 16 = 0 \) 余り \( 2 \)
  → 最後の剰余から順に並べて \((22B)_{16}\)

• 例 \(3\) : 小数の基数変換 \(10\) → \(2\)

  \((0.75)_{10}\) の基数を \(2\) に変換。
  小数部の変換では、小数部分に変換先の基数を掛け、得られた整数部を上から順に読む。

  \(0.75 \times 2 = 1.50\) → 整数部 \(1\)
  \(0.50 \times 2 = 1.00\) → 整数部 \(1\)
  → 得られた整数部を上から順に並べて \((0.11)_{2}\)

• 例 \(4\) : 小数を含む基数変換 \(2\) → \(10\)

  \((110.01)_{2}\) の基数を \(10\) に変換。
  各桁に基数のべき乗を掛け、その総和を求める。

  \[ {\small (110.01)_{2} = 1 \times 2^{2} + 1 \times 2^{1} + 0 \times 2^{0} + 0 \times 2^{-1} + 1 \times 2^{-2} } \]
  \[ {\small = 4 + 2 + 0 + 0 + 0.25 = (6.25)_{10} } \]

補数表現（負の数の表現）

• 補数表現
  ここでは、固定した桁数における \(r\) の補数（基数の補数） を扱う。
  \(n\) 桁の \(r\) 進数で \(0 \leq x < r^n\) のとき、\(x\) の \(r\) の補数は \((-x) \bmod r^n\) で表される。

  \(0 < x < r^n\) の場合は、次の式で求められる。\(x = 0\) の場合は \(0\) とする。

  \[ {\small r^{n} - x } \]

  • 例 \(1\) : \(2\) 桁の \(10\) 進数 \((55)_{10}\) の \(10\) の補数。

    \[ {\small 10^{2} - 55 = 45 } \]

  • 例 \(2\) : \(8\) 桁の \(2\) 進数 \((00001101)_{2}\) の \(2\) の補数。

    \(2\) 進数では、全ビットを反転したものが \(1\) の補数で、さらに \(1\) を加えると \(2\) の補数になる。

    \[ {\small 00001101 \rightarrow 11110010 \rightarrow 11110011 } \]

• 補数表現するメリット
  補数を使うと、減算を加算として扱える。
  コンピュータ内部では、引き算専用の仕組みを用意するより、補数を使って加算として扱う方が都合がよい。

  • 例 \(1\) : \((25)_{10} - (13)_{10}\) を \(2\) 桁の \(10\) 進数で考える。

    \[ {\small 25 - 13 = 25 + (-13) } \]

    \(-13\) を \(2\) 桁の \(10\) 進数の補数で表すと、\(100 - 13 = 87\) となる。

    \[ {\small 25 + 87 = 112 } \]

    \(2\) 桁の範囲で見るため、上位の桁上がりを捨てると \(12\) となる。

  • 例 \(2\) : \((25)_{10} - (14)_{10}\) を \(8\) ビットの \(2\) 進数で考える。

    \[ {\small 25 = (00011001)_{2} } \]
    \[ {\small 14 = (00001110)_{2} } \]

    \(14\) の \(2\) の補数は \((11110010)_{2}\) となる。

    \[ {\small (00011001)_{2} + (11110010)_{2} = (100001011)_{2} } \]

    \(8\) ビットの範囲で見るため、桁あふれした先頭の \(1\) を捨てる。

    \[ {\small (00001011)_{2} = (11)_{10} } \]

小数表現

• 固定小数点数表現
  小数点の位置を固定して数値を表す方式。
  表せる範囲は限られるが、考え方は直感的で分かりやすい。

• 浮動小数点数表現
  数値を仮数部と指数部に分けて表す方式。
  固定小数点数より広い範囲の数値を扱える。

  例えば、\(5.2 \times 10^{-4}\) の場合、\(5.2\) が仮数部、\(-4\) が指数部にあたる。

• 小数表現の正規化
  正規化とは、仮数部と指数部の形を一定のルールにそろえることを指す。
  代表的には、仮数部を \(1 \leq |m| < r\) にそろえる形式と、\(1/r \leq |m| < 1\) にそろえる形式がある。どの形を正規化とするかは、問題文の条件や浮動小数点形式によって異なる。

  • 例 \(1\) : \((0.00052)_{10}\) を正規化する。

    \[ {\small (0.00052)_{10} = 5.2 \times 10^{-4} } \]

    この場合、\(5.2\) が仮数部、\(-4\) が指数部となる。

    \[ {\small (0.00052)_{10} = 0.52 \times 10^{-3} } \]

    このような表し方もできるため、このテーマでは「仮数部をどの範囲に収めるか」という条件を確認する必要がある。

  • 例 \(2\) : \((0.011)_{2}\) を正規化する。

    \[ {\small (0.011)_{2} = (1.1)_{2} \times 2^{-2} } \]
    \[ {\small (0.011)_{2} = (0.11)_{2} \times 2^{-1} } \]

    どちらも値は同じだが、正規化の形式は条件によって変わる。

基数変換の誤差

• 小数の基数変換による誤差
  \(10\) 進数では有限小数として表せる値でも、\(2\) 進数では循環小数になる場合がある。
  コンピュータは多くの場合、浮動小数点数を \(2\) 進数で扱うため、期待した計算結果とわずかにずれることがある。

  • 例 : \((0.4)_{10}\) の基数を \(2\) に変換。

    \[ {\small (0.4)_{10} = (0.01100110011001100110\ldots)_{2} } \]
    \[ {\small = (0.\overline{0110})_{2} } \]

    \(0.4\) は \(2\) 進数では有限桁で表せないため、途中で丸めると誤差が発生。

数値演算の誤差

• 丸め誤差
  指定された桁数で数値を扱うために、四捨五入、切捨て、切上げなどで下位の桁を削ることによって生じる誤差。

• 桁落ち
  ほぼ等しい値同士を引き算したとき、有効桁数が大きく減ってしまうことで生じる誤差。

  • 例 : 各平方根を有効数字 \(7\) 桁に丸めて、\(\sqrt{999} - \sqrt{997}\) を計算。

    \[ {\small \sqrt{999} \fallingdotseq 31.60696125 } \]
    \[ {\small \sqrt{997} \fallingdotseq 31.57530680 } \]

    これらを丸めて計算すると、丸め誤差を含んだ値同士を引くことになる。

    \[ {\small 31.60696 - 31.57531 = 0.03165 } \]

    近い値同士の差を取るため、有効な桁が減り、桁落ちが発生。

• 情報落ち
  極端に大きい数値と小さい数値を加算したとき、小さい数値が有効桁数の範囲に収まらず、結果に反映されないことを指す。

  • 例 : 有効桁数 \(6\) 桁で \((256.789)_{10} + (0.00011)_{10}\) を計算。

    \[ {\small 256.789 + 0.00011 = 256.78911 } \]

    ただし、有効桁数 \(6\) 桁では \(256.789\) までしか保持できないため、\(0.00011\) の影響が消える。

• 打切り誤差
  無限級数や繰り返し計算を、有限回で打ち切ることによって発生する誤差。

• オーバーフロー
  演算結果の絶対値が、データ形式で表現できる最大の大きさを超えてしまう状態。

• アンダーフロー
  演算結果の絶対値が非常に小さくなり、正規化数として表現できる最小値を下回る状態。
  IEEE 754 では、直ちに \(0\) になるとは限らず、サブノーマル数（非正規化数）として表現される場合がある。

集合

要素が集合に属するかどうかを命題として見ると、集合演算と論理演算の対応を整理しやすい。
ここでは、集合記号と対応する論理条件を分けて示す。

• 和集合
  少なくともどちらか一方に含まれる要素の集合。
  集合記号：\(A \cup B\)
  \(x \in A \cup B\) は、\(x \in A\) または \(x \in B\)（OR）に対応。

• 積集合
  両方に共通して含まれる要素の集合。
  集合記号：\(A \cap B\)
  \(x \in A \cap B\) は、\(x \in A\) かつ \(x \in B\)（AND）に対応。

• 補集合
  全体集合 \(U\) のうち、集合 \(A\) に含まれない要素の集合。
  集合記号：\(A^c = U \setminus A\)
  \(x \in A^c\) は、\(x \in A\) ではないこと（NOT）に対応。

• 差集合
  集合 \(A\) から、集合 \(B\) に含まれる要素を取り除いた集合。
  集合記号：\(A \setminus B\)
  \(x \in A \setminus B\) は、\(x \in A\) かつ \(x \notin B\) に対応。

• 対称差集合
  どちらか一方にだけ含まれる要素の集合。
  集合記号：\(A \triangle B\)
  \(x \in A \triangle B\) は、\(x\) がどちらか一方だけに属すること（XOR）に対応。

まとめ

• 基数変換では、整数部は割り算の余り、小数部は掛け算の整数部を使う。
• 補数は、決められた基数と桁数の中で負数を表し、減算を加算として扱うために使われる。
• 固定小数点数は小数点の位置を固定し、浮動小数点数は仮数部と指数部に分けて表す。正規化では、その表現を一定の形式にそろえる。
• 丸め誤差は桁を削ることで生じ、桁落ちは近い値同士の減算で有効桁が減ることで生じる。
• 情報落ちは小さい値が演算結果へ反映されない現象、アンダーフローは値が表現可能な範囲の下限を下回る現象。
• 集合演算は論理演算と対応し、差集合は一方から要素を除き、対称差集合はどちらか一方だけに含まれる要素を集める。

参考文献

• 瀬戸 美月（\(2020\)）『徹底攻略 応用情報技術者教科書』株式会社インプレス
• Python公式チュートリアル - 浮動小数点演算、その問題と制限（日本語・数値誤差の公式解説）
• IEEE Standards Association - IEEE 754-2019（英語・浮動小数点数の規格原文）