LoginSignup
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@keu5(☕)

ブースのアルゴリズムをC++で実装してみた

Posted at

ブースのアルゴリズム実装した記事が見つからない上にChatGPTに聞いても的外れなコードしか出来上がらないので自分で作ってみました．

ブースのアルゴリズムとは？

符号付き二進数の乗算を効率的に行う手法です．加算器作ったならもちろん乗算器も作りたくなるよね？でも加算を何度もする乗算は計算に時間がかかってしまうので，ブースのアルゴリズムが編み出されました．

アルゴリズムの概要

アルゴリズムは以下の通りです．

  1. 被乗数と乗数を二の補数表現で用意します．(今回は4bit分用意してみます)
  2. 被乗数については，符号を変えたものも用意しておきます．(もちろん補数表現を使用しますが，わかりやすいように以降は「-被乗数」とします)
  3. $A$を「被乗数 + 00000」,$S$を「-被乗数 + 00000」とします．
  4. $P_0$を「0000 + 乗数 + 0」とします．
  5. 漸化的に$P_n$を求めていきます．4bit同士の演算の場合，$P_4$まで求めます．
    • $P_{n}$の末尾2bitが「00」あるいは「11」の場合，$P_{n}$を算術右シフトしたものを$P_n$とする
    • 末尾が「01」の場合，$P_{n}$に$A$を加算したうえで右シフトしたものを$P_{n+1}$とする
    • 末尾が「10」の場合，$P_{n}$に$S$を加算したうえで右シフトしたものを$P_{n+1}$とする
  6. $P_4$の上位8桁が解となります．

詳しくはシフト演算とは？論理シフトと算術シフトの違いを調べよう！を参考にすると良いです．

C++による実装

別にCでも書けるんですけど，練習したいのでC++で書きます．

ライブラリのインポートや定数など

#include <iostream>
#include <vector>

constexpr int BIT_SIZE = 4;
constexpr int TABLE_SIZE = 2 * BIT_SIZE + 1;

using namespace std;

BoothAlgorithmクラスの構築

必要な変数は

  1. 被乗数
  2. -被乗数
  3. $P_0$

で，必要な関数は，

  1. 整数を二進数に変換する関数
  2. 算術右シフトさせる関数
  3. 二進数加算させる関数
  4. $P_{n+1}$を求める関数
  5. 配列を表示させる関数
  6. 再帰的に$P$を求める関数

です．

メンバ変数

まずは必要なメンバ変数を用意します．先ほどと同様に$A$は被乗数，$S$は-被乗数，$P_0$を乗数とします．

class BoothAlgorithm {
  public:
  private:
   vector<int> A, S, P_0, Result;

整数を二進数に変換する関数to_binary

binary[bit_size - 1 - i] = (x >> i) & 1;とすることで，10進数の値を2進数にしたときにi桁目の値を対応する配列に格納していきます．

    vector<int> to_binary(int x, int bit_size) {
      vector<int> binary(bit_size, 0);

      for (int i = 0; i < bit_size; i++) {
          binary[bit_size - 1 - i] = (x >> i) & 1;
      }

      return binary;
    }

算術シフトさせる関数right_shift

算術シフトですので最上位ビットの処理に気をつけます．

    void right_shift(vector<int>& vec) {
      for (int i = vec.size() - 1; i > 0; --i) {
        vec[i] = vec[i - 1];
      }
      vec[0] = vec[0] == 1 ? 1 : 0;
    }

二進数加算させる関数add_vectors

単純に要素ごとに加算させると，10進数として計算してしまうため，二進数としての繰り上がりを考慮する必要があります．

    vector<int> add_vectors(const vector<int>& vec1, const vector<int>& vec2) {
      vector<int> result(vec1.size());
      int carry = 0;

      for (size_t i = vec1.size(); i-- > 0;) {
        int sum = vec1[i] + vec2[i] + carry;
        result[i] = sum % 2;
        carry = sum / 2;
      }

      return result;
    }

$P_{n+1}$を求める関数conditional_shift

  • $P_{n}$の末尾2bitが「00」あるいは「11」の場合，$P_{n}$を算術右シフトしたものを$P_n$とする
  • 末尾が「01」の場合，$P_{n}$に$A$を加算したうえで右シフトしたものを$P_{n+1}$とする
  • 末尾が「10」の場合，$P_{n}$に$S$を加算したうえで右シフトしたものを$P_{n+1}$とする

という条件をもとにシフトさせる関数を作ります．

    vector<int> conditional_shift(const vector<int>& A, const vector<int>& S, const vector<int>& P) {
      vector<int> result = P;

      if (P[TABLE_SIZE - 2] == P[TABLE_SIZE - 1]) {
        right_shift(result);
      } else if (P[TABLE_SIZE - 2] == 0) {
        result = add_vectors(result, A);

        right_shift(result);
      } else {
        result = add_vectors(result, S);

        right_shift(result);
      }

      return result;
    }

配列を表示させる関数

あるとわかりやすいね

    void print_array(const vector<int>& arr) {
      for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
      }
      cout << endl;
    }

再帰的に$P$を求める関数

先ほど作ったconditional_shift()を使って$P_1\sim P_4$まで再帰的に計算させます．

    vector<int> booth_algorithm(vector<int>& A, vector<int>& S, vector<int>& P, int count = BIT_SIZE) {
      if (count > 0) {
        P = conditional_shift(A, S, P);

        cout << "P_" << BIT_SIZE - count + 1 << ": ";
        print_array(P);

        return booth_algorithm(A, S, P, count - 1);
      } else {
        vector<int> Result(TABLE_SIZE - 1, 0);

        for (int i = 0; i < TABLE_SIZE - 1; i++) {
          Result[i] = P[i];
        }

        return Result;
      }
    }

コンストラクタなど

コンストラクタでは，整数x, yを受け取り，2進数に変換しつつ適切な形式に変換して，各メンバ変数に代入していきます．また実行のために関数runを用意します．

  public:
    BoothAlgorithm(int x, int y) {
      A.resize(TABLE_SIZE, 0);
      S.resize(TABLE_SIZE, 0);
      P_0.resize(TABLE_SIZE, 0);
      Result.resize(TABLE_SIZE - 1, 0);

      vector<int> binary_x = to_binary(x, BIT_SIZE);
      vector<int> binary_minus_x = to_binary(-x, BIT_SIZE);
      vector<int> binary_y = to_binary(y, BIT_SIZE);

      for (int i = 0; i < BIT_SIZE; i++) {
        A[i] = binary_x[i];
        S[i] = binary_minus_x[i];
        P_0[i + BIT_SIZE] = binary_y[i];
      }
    }

    void run() {
      cout << "P_0: ";
      print_array(P_0);

      Result = booth_algorithm(A, S, P_0);

      cout << "Result: ";
      print_array(Result);
    }

main関数

あとはmain関数を書けば完成です．

int main() {
  int x, y;
  cin >> x >> y;

  BoothAlgorithm booth(x, y);
  booth.run();

  return 0;
}

実際に実行してみる

❯ cpp booth.cpp
-6 5
P_0: 0 0 0 0 0 1 0 1 0 
P_1: 0 0 1 1 0 0 1 0 1 
P_2: 1 1 1 0 1 0 0 1 0 
P_3: 0 0 1 0 0 1 0 0 1 
P_4: 1 1 1 0 0 0 1 0 0 
Result: 1 1 1 0 0 0 1 0 

❯ cpp booth.cpp
5 -6
P_0: 0 0 0 0 1 0 1 0 0 
P_1: 0 0 0 0 0 1 0 1 0 
P_2: 1 1 0 1 1 0 1 0 1 
P_3: 0 0 0 1 0 1 0 1 0 
P_4: 1 1 1 0 0 0 1 0 1 
Result: 1 1 1 0 0 0 1 0 

❯ cpp booth.cpp
4 -3
P_0: 0 0 0 0 1 1 0 1 0 
P_1: 1 1 1 0 0 1 1 0 1 
P_2: 0 0 0 1 0 0 1 1 0 
P_3: 1 1 1 0 1 0 0 1 1 
P_4: 1 1 1 1 0 1 0 0 1 
Result: 1 1 1 1 0 1 0 0

実際に実行してみると上記のようになります．例えば，$5\times -6$という演算をブースのアルゴリズムで解いた場合，$P_4=(11100010)2=(-30){10}$のように，確かに正しく計算できています．

また，$-6\times 5$でも同じような結果となっており，乗法の交換律も成り立っています．

$4\times -3$も同様に正しく計算できています．

コードの全体像

最後にコードの全体像を貼っておきます．

#include <iostream>
#include <vector>

constexpr int BIT_SIZE = 4;
constexpr int TABLE_SIZE = 2 * BIT_SIZE + 1;

using namespace std;

class BoothAlgorithm {
  public:
    BoothAlgorithm(int x, int y) {
      A.resize(TABLE_SIZE, 0);
      S.resize(TABLE_SIZE, 0);
      P_0.resize(TABLE_SIZE, 0);
      Result.resize(TABLE_SIZE - 1, 0);

      vector<int> binary_x = to_binary(x, BIT_SIZE);
      vector<int> binary_minus_x = to_binary(-x, BIT_SIZE);
      vector<int> binary_y = to_binary(y, BIT_SIZE);

      for (int i = 0; i < BIT_SIZE; i++) {
        A[i] = binary_x[i];
        S[i] = binary_minus_x[i];
        P_0[i + BIT_SIZE] = binary_y[i];
      }
    }

    void run() {
      cout << "P_0: ";
      print_array(P_0);

      Result = booth_algorithm(A, S, P_0);

      cout << "Result: ";
      print_array(Result);
    }

  private:
    vector<int> A, S, P_0, Result;

    void right_shift(vector<int>& vec) {
      for (int i = vec.size() - 1; i > 0; --i) {
        vec[i] = vec[i - 1];
      }
      vec[0] = vec[0] == 1 ? 1 : 0;
    }

    vector<int> add_vectors(const vector<int>& vec1, const vector<int>& vec2) {
      vector<int> result(vec1.size());
      int carry = 0;

      for (size_t i = vec1.size(); i-- > 0;) {
        int sum = vec1[i] + vec2[i] + carry;
        result[i] = sum % 2;
        carry = sum / 2;
      }

      return result;
    }

    vector<int> to_binary(int x, int bit_size) {
      vector<int> binary(bit_size, 0);

      for (int i = 0; i < bit_size; i++) {
          binary[bit_size - 1 - i] = (x >> i) & 1;
      }

      return binary;
    }

    vector<int> conditional_shift(const vector<int>& A, const vector<int>& S, const vector<int>& P) {
      vector<int> result = P;

      if (P[TABLE_SIZE - 2] == P[TABLE_SIZE - 1]) {
        right_shift(result);
      } else if (P[TABLE_SIZE - 2] == 0) {
        result = add_vectors(result, A);

        right_shift(result);
      } else {
        result = add_vectors(result, S);

        right_shift(result);
      }

      return result;
    }

    void print_array(const vector<int>& arr) {
      for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
      }
      cout << endl;
    }

    vector<int> booth_algorithm(vector<int>& A, vector<int>& S, vector<int>& P, int count = BIT_SIZE) {
      if (count > 0) {
        P = conditional_shift(A, S, P);

        cout << "P_" << BIT_SIZE - count + 1 << ": ";
        print_array(P);

        return booth_algorithm(A, S, P, count - 1);
      } else {
        vector<int> Result(TABLE_SIZE - 1, 0);

        for (int i = 0; i < TABLE_SIZE - 1; i++) {
          Result[i] = P[i];
        }

        return Result;
      }
    }
};

int main() {
  int x, y;
  cin >> x >> y;

  BoothAlgorithm booth(x, y);
  booth.run();

  return 0;
}
1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?