すらどからやってきました。消滅前に転載します。
手順
割られる数をnとおきます
最下位ビットを別途取っておきます(n0 = n & 1)
nを1ビット右シフト(n >>= 1)
残りを4ビットごとに区切って和を取ります
n = ((0xf0f0f0f0 & n) >> 4) + (0x0f0f0f0f & n);
n = (n >> 16) + n;
n = (n >> 8) + n;
n &= 0xf;
残りが0-15になるのですが5で割った剰余を求めます
表引きでもよし (tmpres = 0x0432104321043210 >> (n << 2))
if (((n >> 2) & 3) > (n & 3)) {
tmpres = 5 + (n & 3) - ((n >> 2) & 3);
} else {
tmpres = (n & 3) - ((n >> 2) & 3);
}
上記でfloor(n/2)を5で割ったあまりが求まるので、10で割ったあまりにするには
2倍してn0を足します (return (tmpres << 1) | n0)
解説
これ、$5$が$2^2+1$であるというところに鍵があったりします。
$x \equiv 1 \pmod {yz} のとき x \equiv 1 \pmod y、$
$x \equiv 1 \pmod {x-1}、$
$x \equiv 1 \pmod y ならば x^2 \equiv 1 \pmod y$
なので
$2^{2k} \equiv 1 \pmod {2^{2k} - 1}、$
$2^{2k} \equiv 1 \pmod {2^k + 1}、ゆえに$
$2^4 (=16) \equiv 1 \pmod {2^2 + 1} (=5))、さらに$
$(2^4)^2 \equiv 1 \pmod 5$
ということで4ビットごとに区切って足していけば剰余が求まるというわけです。
もひとつ
$x \equiv -1 \pmod {x+1}$
すなわち$4 \equiv -1 \pmod 5$なのが最後のif 文の表現であります。
剰余が出るだけで商は出ないので無能
10で割った商は?
定数での割り算の場合、定番として逆数を掛けます。除算は現代の計算機であっても重いのです。
\sum_{k=1}^{\infty}\frac{1}{n^k} = \frac{1}{n-1}
ということと、16進小数の各桁が $\frac{1}{16^n}$ を表現することから、
0.\dot{1}(16進数) = \sum^{\infty}_{k=1}\frac{1}{16^k} = \frac{1}{15}
したがって$0.\dot{\mathrm c}(16進数) = \frac{4}{5}$との積を取り右3ビットシフト(＝8で割る)してfloorを取れば10で割った商が得られます。
実用上は無限小数との積は取れない! のですが、ここは打ち切りではなく切り上げを使います。
16進小数$m$桁($4m$ビット)で切り上げたとき、真の定数$0.\dot{\mathrm c}(16進数)$と$0.\mathrm c...\mathrm d$の差は$0.0...0\dot{3}$、すなわち
\sum_{k=m+1}^{\infty}\frac{3}{16^k}=\frac{3}{15}\times\frac{1}{16^{m}}
ですから、これに被除数の最大の値$16^{m}-1$をかけても1には満たないことを確認して切り捨てでOKとなります。
これを使うと、$n$ビット$\times n$ビット$= 2n$ビットの結果を得られる積命令があるような現代的なプロセッサならば、
- 0xc...dを掛けて右へ$n+3$ビットシフトで商を得て
- 商に10を掛けて(これも乗算器が速そう)
- 元の数から引くことで剰余を得る
がもっとも高速ということになります。
別の場合
$n \times n = 2n$ビットの結果が得られない積しかない場合 (昔のプロセッサは $n \times n = n$、下位のビットしか得られないものがありました)という場合に、ポータブルに10で割った商を求めるには? を考えておりますが、2倍長演算をやる以外にいい手が今のところありません。考慮中ー