PSoC 4200 Prototyping Kit (6)

中国剰余定理自体の証明や、一般的な解法については省略し、今回の応用に関する解法のみを説明します。
その前に「合同式」について触れておきます。 以降、特にことわりのない限り変数や定数は整数であるとします。

a ≡ b (mod m)

と書いて「m を法 (modulus) として a と b は 合同」と読みます。
これは a を m で割った余りと b を m で割った余りとが等しいことを意味します。　つまり、m で割った余りとしての数値が同値ならば、割る前の b と a の「見た目」が違っていても (法 m のもとで) 同じとみなすということです。
今回の応用での計算方法の説明に移ります。
下のような「ディオファントス方程式」(Diophantine equation) を考えます。
(m₁, m₂ は係数、x, y は変数)

m₁·x + m₂·y = 1

「ディオファントス方程式」とは「整数係数の多元不定方程式」の総称で、この場合は「整数係数の 2 元　1 次方程式」です。 ディオファントス方程式が与えられたとき、整数解や有理数解を求めることを「ディオファントス問題」といいます。
任意の係数の場合には整数解が求まるとは限りませんが、m₁ と m₂ とが「互いに素」つまり、共通の約数を持たない場合には整数解が存在します。
その解は「拡張されたユークリッド互除法」(Extended Euclidean algorithm) によって求めることができますが、今回の場合は自明な解がすぐ見つかります。

m₁ = 2¹⁶ = 65536
m₂ = (m₁ - 1) = (2¹⁶ - 1) = 65535

ですから、

m₁·x + m₂·y = 1
m₁·x + (m₁-1)·y = 1
m₁·(x + y) - y = 1

となり、x = 1、y = -1 という解が導きだされます。
求めたい (32 ビットの) 数を n として、キャプチャする (16 ビットの) 数を a₁、a₂ とすると、合同式で、

n ≡ a₁ (mod m₁)
n ≡ a₂ (mod m₂)

と表せます。
もとのディオファントス方程式の両辺に a₁ を掛け、m₁ による剰余を取って合同式で表すと、

a₁·(m₁·x + m₂·y) = a₁
a₁·m₁·x + a₁·m₂·y = a₁


a₁·m₂·y ≡ a₁ (mod m₁)

となります。　なぜなら、左辺第 1 項の m₁ を含む因子は m₁ による除算で剰余はゼロとなり、右辺の a₁ はすでに m₁ で割った剰余となっているので変化しません。
同様に、もとのディオファントス方程式の両辺に a₂ を掛け、m₂ による剰余を取って合同式で表すと、

a₂·(m₁·x + m₂·y) = a₂
a₂·m₁·x + a₂·m₂·y = a₂


a₂·m₁·x ≡ a₂ (mod m₂)

となります。
もとの数 n を上の 2 つの合同式の左辺の和、

n = a₂·m₁·x + a₁·m₂·y

で表すと、n と a₁、a₂ との合同関係を満たしていることが容易に分かります。
今回の応用での x, y の値 x = 1、y = -1 を代入して具体的な形にすると、

n = a₂·m₁·(1) + a₁·m₂·(-1)
   = a₂·m₁ - a₁·m₂
   = a₂·m₁ - a₁·(m₁ - 1)
   = (a₂ - a₁)·m₁ + a₁

これが今回の応用の基本的な式です。
m₁ = 2¹⁶ ですから、m₁ による乗算は実際には 16 ビット左シフトするだけですみ、本当の乗算を行う必要はありません。
シフトによって空いた下位 16 ビットに 16 ビット数値である a₁ がスッポリとおさまる形となり、式の上では「加算」になっていますが、実際には OR (論理和) 演算でも正しい結果が得られます。
次回は、この基本式をさらに変形していきます。