C++でDFA（決定性有限オートマトン）を使った除算と剰余の求め方

DFAによる除算とは

決定性有限オートマトン（DFA：Deterministic Finite Automaton）は、ある数が別の数 k で割り切れるかどうかを判定するために利用できます。このアルゴリズムの優れた点は、割り切れない場合にその余り（剰余）まで求められることです。

DFAベースの除算では、状態数 k 個の遷移表（DFAテーブル）を構築します。数値は2進表現として扱うため、各状態からの遷移で入力となるのは 0 と 1 のみです。

遷移表の作成：createTransTable関数

createTransTable(int k, int transTable[][2]) 関数は、遷移表 transTable を作成し、各状態の遷移先を格納します。引数には、除数となる数 k と、2列の配列 transTable[][2] を渡します。関数内では、ビット 0 に対する次の状態を保持する trans_0 と、ビット 1 に対する次の状態を保持する trans_1 の2つの変数を宣言します。

void createTransTable(int k, int transTable[][2]{
    int trans_0, trans_1;

内部のforループは、state が k 未満である間繰り返されます。trans_0 が k より小さければ transTable[state][0] に trans_0 を代入し、そうでなければ trans_0 から k を減算した値を代入します。trans_1 についても同様に、k より小さければそのまま、そうでなければ k を引いた値を transTable[state][1] に格納します。

for (int state = 0; state < k; state++){
    trans_0 = state << 1;
    transTable[state][0] = (trans_0 < k) ? trans_0 : trans_0 - k;
    trans_1 = (state << 1) + 1;
    transTable[state][1] = (trans_1 < k) ? trans_1 : trans_1 - k;
}

この処理は「現在の余り state × 2 ＋ 入力ビット」を計算し、k 以上になったら k を引くことで mod k を取る操作に相当します。

割り切れるかの判定：checkDivisible関数

checkDivisible(int num, int &state, int transTable[][2]) 関数は、被除数 num、参照渡しされる状態変数 state、遷移表 transTable[][2] を受け取ります。num が 0 でない場合、ビット単位の右シフト（>> 1）を再帰的に適用して数を1桁ずつ処理し、num が 0 になるまで繰り返します。右シフトは数を2で割る操作に相当します。その後、transTable[state][num&1] の値を state 変数に代入していきます。

void checkDivisible(int num, int &state, int transTable[][2]){
    if (num != 0){
        checkDivisible(num >> 1, state, transTable);
        state = transTable[state][num&1];
    }
}

再帰呼び出しによって最上位ビットから順に処理されるため、筆算と同じく左から右へ桁をたどる処理が実現されています。

判定結果の取得：isDivisible関数

isDivisible(int num, int k) 関数は、被除数 num と除数 k を受け取ります。まず2列 × k 行の遷移表 transTable[k][2] を宣言し、createTransTable(k, transTable) で遷移表を作成した後、checkDivisible(num, state, transTable) を呼び出して state 変数を更新します。最後に返される state の値が、num を k で割った余りに相当します。

int isDivisible (int num, int k){
    int transTable[k][2];
    createTransTable(k, transTable);
    int state = 0;
    checkDivisible(num, state, transTable);
    return state;
}

実装例

DFAベースの除算を実装したコード全体は以下の通りです。

#include <bits/stdc++.h>
using namespace std;
void createTransTable(int k, int transTable[][2]){
    int trans_0, trans_1;
    for (int state = 0; state < k; state++){
        trans_0 = state << 1;
        transTable[state][0] = (trans_0 < k) ? trans_0 : trans_0 - k;
        trans_1 = (state << 1) + 1;
        transTable[state][1] = (trans_1 < k) ? trans_1 : trans_1 - k;
    }
}
void checkDivisible(int num, int &state, int transTable[][2]){
    if (num != 0){
        checkDivisible(num >> 1, state, transTable);
        state = transTable[state][num&1];
    }
}
int isDivisible (int num, int k){
    int transTable[k][2];
    createTransTable(k, transTable);
    int state = 0;
    checkDivisible(num, state, transTable);
    return state;
}
int main(){
    int num = 67;
    int k = 5;
    int remainder = isDivisible (num, k);
    if (remainder == 0)
        cout << num << " is divisible by " << k;
    else
        cout << num << " is not divisible by " << k << " and lefts remainder " << remainder;
    return 0;
}

実行結果

上記のコードを実行すると、以下の出力が得られます。

67 is not divisible by 5 and lefts remainder 2

この例では、67 を 5 で割ると余り 2 が残るため、「割り切れず余りは2」という結果が出力されます。このようにDFAを使った手法では、割り切れるかどうかの判定と剰余の計算を同時に行えるのが大きな特徴です。