なんか最近割り算する回路を書いていろいろ知ったのでまとめていきます。
以下、割り算とは以下のものをさすことにします。
- 商と余りを両方求める
- 符号付きの場合、商はゼロへ丸め、余りは被除数と同じ符号とする
2は、数学的な定義とは異なります。C99で定義された除算の定義に一致します。
回路の説明というよりは、先週作った任意幅整数型lbl::uintN_t<N>とlbl::intN_t<N>（GitHub - lpha-z/lbl: header only fixed width integer library）を使ってC++でアルゴリズムを書き起こしたものの紹介です。
回復法(restoring division)
小学校で習うような、筆算で求める方法です。
「回復」の名は、いったん除数を引いてみて負になってしまうようであれば除数を足すことで元の状態に"戻す"、というところからきているようです。 ソフトウェア的に実装するならともかく、ハードウェアで実現するのであれば、引く前の値を持っておけばよいだけなので、この名前はやや違和感があります。
#include "lbl/xintN_t.hpp"
template<std::size_t N>
constexpr lbl::uintN_t<N> safe_abs( lbl::intN_t<N> x ) {
return x < 0 ? -x : x;
}
template<std::size_t N>
constexpr auto divider( const lbl::uintN_t<N> dividend, const lbl::uintN_t<N> divisor ) {
lbl::uintN_t<N> remainder = 0;
lbl::uintN_t<N> quotient = 0;
for( int i = N-1; i >= 0; --i ) {
quotient <<= 1;
remainder <<= 1;
remainder |= dividend & 1ull<<i ? 1 : 0;
const lbl::uintN_t<N+1> test_sub = static_cast<lbl::uintN_t<N+1>>(remainder) - static_cast<lbl::uintN_t<N+1>>(divisor);
const bool success = static_cast<lbl::intN_t<N+1>>(test_sub) >= 0;
quotient |= success ? 1 : 0;
remainder = success ? static_cast<lbl::uintN_t<N>>(test_sub) : remainder;
}
return std::pair {
quotient,
remainder
};
}
template<std::size_t N>
constexpr auto divider( const lbl::intN_t<N> dividend, const lbl::intN_t<N> divisor ) {
const bool quotient_sign = dividend < 0 ^ divisor < 0;
const bool remainder_sign = dividend < 0;
const auto [quotient, remainder] = divider_impl( safe_abs(dividend), safe_abs(divisor) );
return std::pair {
quotient_sign ? -static_cast<lbl::intN_t<N>>(quotient) : static_cast<lbl::intN_t<N>>(quotient),
remainder_sign ? -static_cast<lbl::intN_t<N>>(remainder) : static_cast<lbl::intN_t<N>>(remainder)
};
}
reminder |= dividend & 1ull<<i ? 1 : 0;の部分は、筆算で「次の桁をおろしてくる」部分に相当します。dividendは他の部分で使われないので破壊しても問題なく、dividend自体をシフトすることによって、ハードウェアは簡素化しますが、見やすさを優先しました。そのほか、最初の方はremainderの上位桁が使われていないことを利用すると、実はdividendと共存可能で、記憶素子をケチることができます。
要するに、引いてみても正だったら商として1を立て、そうでなければ0を立てる、というだけのアルゴリズムです。
引いてみて正かどうかを判定する部分は、オーバーフローしないように、結果を一桁多く求める必要があります（ボローが発生するかの確認が必要です）。reminderやdivisor自体はN桁のまま計算してよいのですが、C++ではうまく書けなかったのでこのような形になっています。
for文で書いてある部分は、ハードウェアでは普通、複数サイクルかけて計算を行うことになるでしょう。
for文を回る回数はN回であり、各ループ内で一回加算器*1を使っています。つまり、1クロックに加算器が一回しか使えないような状況*2では、割り算を終わらせるのにNクロックかかるということになります。
符号付きの除算を行う場合、符号がついていると面倒なことになりますが、被除数・除数ともに絶対値を取って計算をした後、最後の段階で符号を正しく付け直すと簡単になります。
絶対値を取ったり負号をつけたりするのにも加算器が必要なことを考えると、素直に作るとN+2クロックかかるはずです。少し工夫すると、最終サイクルでの符号調整はループの中に組み込めるので、ループの最後の回では処理を変えることにより、余分な2クロックのうち1クロックは除去可能です。
また、ループの最初の回で立つ商が1であるパターンは限られているので、そのパターンを書き下せば、加算器を使わずに商を立てることができます。それと並行して絶対値を取る処理を行えば、余分なもう1クロックを削ることができます。そこまでする必要があるかは疑問ですが……。
回復法で除算を行う場合、加算器の結果がマルチプレクサの入力になりますが、典型的なFPGA (Field programmable gate array)に実装する場合、このことが大きな弱点になります。 典型的なFGPAの論理セルでは、組み合わせ回路を実現する LUT (Look-up table) の直後にフルアダーが配置してあります。マルチプレクサはLUTで実現、加算器はフルアダーで実現することになりますが、順序が逆なため二つの論理セルを使わないと実現できないことになります。
