nekoponの日記： 10で割った剰余

割られる数を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²+1であるというところに鍵があったりします。

• x ≡ 1 (mod yz) のとき x ≡ 1 (mod y)
• x ≡ 1 (mod (x-1))
• x ≡ 1 (mod y) ならば x² ≡ 1 (mod y)

なので
2^2k ≡ 1 (mod (2^2k) - 1)
2^2k ≡ 1 (mod (2^k + 1))、ゆえに
2⁴ (=16) ≡ 1 (mod 2² + 1 (=5))、さらに
2^{4 x 2} ≡ 1 (mod 5)
ということで4ビットごとに区切って足していけば剰余が求まるというわけです。

もひとつ

• x ≡ -1 (mod x+1)

すなわち4 ≡ -1 (mod 5)なのが最後の if 文の表現であります。

剰余が出るだけで商は出ないので無能

1か所間違ってたのでこっそり修正～

[nekopon (1483)]

ということですんません

ちゃんと検証してませんが

[minet (45149)]

乗算命令が遅くないCPUなら、愚直に商を求めてからその10倍の数を引いちゃうって手もあり？

1. 割られる数をnとおく。
2. nを10で割って切り捨ててから8倍にした整数n1を得る。
   素直に書けば
   n1 = n * 0xcccccccd >> 35 << 3;
   だが、
   乗算の結果の上位32ビットだけ使うことを考慮して
   n1 = n * 0xcccccccd >> 32 & 0xfffffff8;
   こう書いてもいいかも？
3. n1にn1の4分の1を足す。
   n1 += n1 >> 2
   すなわち、商の8倍+2倍=10倍の数が得られた。
4. nからn1を引く。
   result = n - n1;
   すなわち、元の数から商の10倍の数が引かれたので、剰余が得られた。

Re:ちゃんと検証してませんが

[taka2 (14791)]

2桁までだし、Z80のコードですが、yasuoka氏のZ80のコード [srad.jp]だと、10で割った商と余りを求めるのに
最初は「10で割る(商)」→「10倍して引く(余り)」という流れで計算してましたが、
最終的には、
・まず10で割った余りを求める
・元の数から余りを引いて、10の倍数にする
・10で割って商を求める
って流れで計算してますね。
最後の10で割るとこは、「余りを引けば、得られる値は全て10の倍数になる。10=8+2をうまく使えば、商の計算は基本的にビット操作に落とせる」んだそうですが、Z80のコードみても、なぜそれで商になるのか私にはさっぱりわからない…

Re:ちゃんと検証してませんが

[nekopon (1483)]

わたしにもわからない…(DAAが強力だからですが)
yasuoka先生のコードはfloor(n/8)の8倍をBCDで得て(ADD A/DAA 3回はコレ)、n mod 8を足してもう一回BCDに補正するという座組です。10進補正命令があるからの技だと言わざるを得ません。
// 255/10から商=25、あまり=5が欲しいので足りませんでした

Re:ちゃんと検証してませんが

[nekopon (1483)]

商を求める計算自体は floor(n * (ceil(2^k/10) / 2^k)) という計算で、ceilで切り上げる分が小さいほど良い近似になります。k = 7 でも n < 2⁷ であれば正しい値が得られるわけで、乗算が速くて上位ビットが得られる計算機であればコイツが一番マシになりますね

Re:

[Anonymous Coward]

GCCで最適化オプションを付けたらこんな感じのコードになった。

int64_t rax = (int32_t)((int64_t)x * 0x66666667 >> 34) - (x >> 31);
int32_t edx = rax * 5; // lea edx, [rax+rax*4]
return x - (edx + edx);

やはり10で割って10倍して元の数から引くという方針のようだ

Re:ちゃんと検証してませんが

[nekopon (1483)]

64bitでも同じようなコードを発生します(mulqがあるからですが)。

Re:

[Anonymous Coward]

今どき乗算が遅いCPUはないので、こういうのはハードウェアロジックを作るときに使えるかなと思いました。

ここ20年くらいは遅くてもいい(小さな)乗算器(Z80でやったあの筆算方式)を手書きできる
設計者も少ない気がしますが、さすがに除算はHDLで合成できないのでやりたくないはずです。
ふつうに合成される乗算器はもっと速い後段の加算器のキャリーアップがないアルゴリズムを使うので、
加算器よりそれほど遅くありません。数倍いかない。でかいけど。

三本線等号

[Anonymous Coward]

求めているものは、≡ U+2261 IDENTICAL TO ？

Re:三本線等号

[nekopon (1483)]

これこれ! (IMEで出てこなかったのです。これまたすんません)

Re:

[Anonymous Coward]

ごうどう
で変換できると思うっす

Re:三本線等号

[nekopon (1483)]

感謝…! 圧倒的感謝…! (直しました)