nekoponの日記： 10で割った剰余 12
日記 by
nekopon
割られる数を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が22+1であるというところに鍵があったりします。
- x ≡ 1 (mod yz) のとき x ≡ 1 (mod y)
- x ≡ 1 (mod (x-1))
- x ≡ 1 (mod y) ならば x2 ≡ 1 (mod y)
なので
22k ≡ 1 (mod (22k) - 1)
22k ≡ 1 (mod (2k + 1))、ゆえに
24 (=16) ≡ 1 (mod 22 + 1 (=5))、さらに
24 x 2 ≡ 1 (mod 5)
ということで4ビットごとに区切って足していけば剰余が求まるというわけです。
もひとつ
- x ≡ -1 (mod x+1)
すなわち4 ≡ -1 (mod 5)なのが最後の if 文の表現であります。
剰余が出るだけで商は出ないので無能
