0と1しかわからないCPUにとって除算は乗算よりも重たい処理です（といってもこれが問題になるシーンがあるのかは知りません）。そんな中、8ビット整数を10で除算したい場合には205で乗算して11ビット右シフトすればよいという方法を知って驚きました。
11ビット右シフトというのは2048で割るのと同じです。従って、205で乗算して11ビット右シフトすることは 205÷2048 で約 0.10009766 で乗算、言い換えると約 9.9902439 で除算するのと同じです。8ビット整数の範囲 0 から 255 まで試したところ、10で除算するのと完全に一致しました。
そこで、任意の整数での除算を乗算とシフト演算に変換する方法を探索しました。単に順番に試していくだけです。試したコードは以下です。Rustです。
fn main() {
use std::cmp;
for bit_count in [4, 8, 16] {
const MAX_DIVISOR: i32 = 20;
for divisor in 1 .. cmp::min(1 << bit_count, MAX_DIVISOR + 1) {
match search_magic_number(bit_count, divisor) {
Some((a, s)) => println!("bit_count={}: x / {} ≒ (x * {}) >> {}", bit_count, divisor, a, s),
None => panic!("bit_count={}: x / {}", bit_count, divisor),
}
}
if (1 << bit_count) > MAX_DIVISOR + 1 {
println!("...");
}
println!("");
}
}
fn search_magic_number(bit_count: i32, divisor: i32) -> Option<(i32, i32)> {
for s in 0 .. (bit_count * 2 + 1) {
let a = ((1 << s) - 1) / divisor + 1;
let mut flag = true;
for dividend in 1 .. (1 << bit_count) {
let answer1 = dividend / divisor;
let answer2 = (((dividend as i64) * (a as i64)) >> s) as i32;
if answer1 != answer2 {
flag = false;
break;
}
}
if flag {
return Some((a, s));
}
}
return None;
}
4ビット整数の場合、8ビット整数の場合、16ビット整数の場合で、除数を1から順番に試しています。実行すると以下のとおりになりました。
bit_count=4: x / 1 ≒ (x * 1) >> 0
bit_count=4: x / 2 ≒ (x * 1) >> 1
bit_count=4: x / 3 ≒ (x * 11) >> 5
bit_count=4: x / 4 ≒ (x * 1) >> 2
bit_count=4: x / 5 ≒ (x * 13) >> 6
bit_count=4: x / 6 ≒ (x * 11) >> 6
bit_count=4: x / 7 ≒ (x * 19) >> 7
bit_count=4: x / 8 ≒ (x * 1) >> 3
bit_count=4: x / 9 ≒ (x * 15) >> 7
bit_count=4: x / 10 ≒ (x * 7) >> 6
bit_count=4: x / 11 ≒ (x * 3) >> 5
bit_count=4: x / 12 ≒ (x * 11) >> 7
bit_count=4: x / 13 ≒ (x * 5) >> 6
bit_count=4: x / 14 ≒ (x * 19) >> 8
bit_count=4: x / 15 ≒ (x * 9) >> 7
bit_count=8: x / 1 ≒ (x * 1) >> 0
bit_count=8: x / 2 ≒ (x * 1) >> 1
bit_count=8: x / 3 ≒ (x * 171) >> 9
bit_count=8: x / 4 ≒ (x * 1) >> 2
bit_count=8: x / 5 ≒ (x * 205) >> 10
bit_count=8: x / 6 ≒ (x * 171) >> 10
bit_count=8: x / 7 ≒ (x * 293) >> 11
bit_count=8: x / 8 ≒ (x * 1) >> 3
bit_count=8: x / 9 ≒ (x * 57) >> 9
bit_count=8: x / 10 ≒ (x * 205) >> 11
bit_count=8: x / 11 ≒ (x * 373) >> 12
bit_count=8: x / 12 ≒ (x * 171) >> 11
bit_count=8: x / 13 ≒ (x * 79) >> 10
bit_count=8: x / 14 ≒ (x * 293) >> 12
bit_count=8: x / 15 ≒ (x * 137) >> 11
bit_count=8: x / 16 ≒ (x * 1) >> 4
bit_count=8: x / 17 ≒ (x * 241) >> 12
bit_count=8: x / 18 ≒ (x * 57) >> 10
bit_count=8: x / 19 ≒ (x * 27) >> 9
bit_count=8: x / 20 ≒ (x * 205) >> 12
...
bit_count=16: x / 1 ≒ (x * 1) >> 0
bit_count=16: x / 2 ≒ (x * 1) >> 1
bit_count=16: x / 3 ≒ (x * 43691) >> 17
bit_count=16: x / 4 ≒ (x * 1) >> 2
bit_count=16: x / 5 ≒ (x * 52429) >> 18
bit_count=16: x / 6 ≒ (x * 43691) >> 18
bit_count=16: x / 7 ≒ (x * 74899) >> 19
bit_count=16: x / 8 ≒ (x * 1) >> 3
bit_count=16: x / 9 ≒ (x * 58255) >> 19
bit_count=16: x / 10 ≒ (x * 52429) >> 19
bit_count=16: x / 11 ≒ (x * 47663) >> 19
bit_count=16: x / 12 ≒ (x * 43691) >> 19
bit_count=16: x / 13 ≒ (x * 20165) >> 18
bit_count=16: x / 14 ≒ (x * 74899) >> 20
bit_count=16: x / 15 ≒ (x * 34953) >> 19
bit_count=16: x / 16 ≒ (x * 1) >> 4
bit_count=16: x / 17 ≒ (x * 61681) >> 20
bit_count=16: x / 18 ≒ (x * 58255) >> 20
bit_count=16: x / 19 ≒ (x * 55189) >> 20
bit_count=16: x / 20 ≒ (x * 52429) >> 20
...
16ビット整数を10で除算するには52429を掛けて19ビット右シフトすればよいようです。約 9.99996185 で割るのと同じで、これが16ビット整数の範囲では10で割るのと完全に一致します。
除数が定数の場合は除算を乗算に変換できることがわかりました。定数でなくてもビット数が小さくてすべてのパターンをテーブルに収められる場合は、テーブルを引くことでも乗算に変換できそうです。
いまどきのコンパイラはこれぐらいの最適化をしているのでしょうか。それとも除算が重たいといってもそれほどでもないものなのか。と思っていたら、こんな記事がありました。コンパイラはこのような最適化をしているらしいです。
この知識が役立つ場面はないかもしれません。この記事は私の個人的な連載記事であるセルオートマトンによるCPU作成の中のひとつでした。