「 👇 AtCode の有志が書いた練習問題解いてたら、次のような細かな話しが載ってたぜ」
「 剰余の結果の正負は、割られる数の正負の符号に揃うだけなんじゃないの?」
5 % 3 = 2 // ?
-5 % 3 = -2 // ?
5 % -3 = 2 // ?
-5 % -3 = -2 // ?
📖 -5%3
5 % 3 = 2 // ?
-5 % 3 = 1 // ?
5 % (-3) = -1 // ?
-5 % (-3) = -2 // ?
「 C++ で負の剰余をそう定義したことと、 Wolfram Alpha が負の剰余をそう定義したことで、
どのような都合の良さを取って、どのような都合の悪さを取らなかったのか 気になるぜ」
「 👆 これが、 ー5 を 3人ずつに分けたら ー2 余るという C++の主張だぜ」
「 👆 これが、 ー5 を 3人ずつに分けたら 1 余るという Wolfram Alpha の主張だぜ」
「 👆 もし 6枚のカマボコがあるとして ー5 すれば 1 余るだろ、という理屈だぜ」
「 6枚のカマボコがある、ということにするのは 無理攻めな気がするぜ」
「 👆 C++ の主張では、
8枚のカマボコを3人で分けたら 2余る。
5枚のカマボコを3人で分けたら 2余る。
ー5枚のカマボコを3人で分けたら ー2余るぜ」
「 👆 Wolfram Alpha の主張を理解するために、らせん状に重ねたカマボコを考えてみようぜ?」
「 👆 C++の主張としては、3で割ろうが、ー3で割ろうが、余りは変わらん ということだぜ」
「 👆 Wolfram Alpha の方は 3で割るか、-3で割るかで 結果が違ってくるぜ」
「 Wolfram Alpha の方は何をやってるか分からん」
より正確に言うと、C++の剰余演算子は(A / B) * B + (A % B)とAが等しくなるように定義されており、結果的にAの正負と一致します。
「 みんなで食べたカマボコと、余り を足せば、元のカマボコに戻るだろ、という式だぜ。
具体的な数を入れて 計算してみようぜ?」
「 👆 図で描けば こうだな。
割り算が小数点切捨てになってるのが コンピューターの独特な所だぜ」
A = 5
B = 3
( A / B ) * B + ( A % B )
= ( 5 / 3 ) * 3 + ( 5 % 3 )
= ( 1 ) * 3 + ( 2 )
= 4 + ( 2 )
= 5
A = -5
B = 3
( A / B ) * B + ( A % B )
= ( -5 / 3 ) * 3 + ( -5 % 3 )
= ( -1 ) * 3 + ( -2 ) # -5 % 3 は定義から -2
= -3 + ( -2 )
= -5
A = 5
B = -3
( A / B ) * B + ( A % B )
= ( 5 / -3 ) * -3 + ( 5 % -3 )
= ( -1 ) * -3 + ( 2 ) # -5 % 3 は定義から 2
= 3 + ( 2 )
= 5
A = -5
B = -3
( A / B ) * B + ( A % B )
= ( -5 / -3 ) * -3 + ( -5 % -3 )
= ( 1 ) * -3 + ( -2 ) # -5 % -3 は定義から -2
= -3 + ( -2 )
= -5
「 Wolfram Alpha の方も 見ておきましょう!」
A = -5
B = 3
( A / B ) * B + ( A % B )
= ( -5 / 3 ) * 3 + ( -5 % 3 )
= ( -1 ) * 3 + ( 1 ) # -5 % 3 は定義から 1
= -3 + ( 1 )
= -2
「 👆 なんてこった。 負の剰余には、2種類ぐらい 良い方法があるらしいぜ。
ユークリッド除法 と、 ドナルド・クヌースの切り下げ除算」
mod(a, n) = a - n * floor(a / n)
A = -5
B = 3
A - B * floor( A / B )
= -5 - 3 * floor( -5 / 3 )
= -5 - 3 * -2 # 負の無限大の方へ切り下げる
= -5 + 6
= 1
A = 5
B = -3
A - B * floor( A / B )
= 5 - -3 * floor( 5 / -3 )
= 5 - -3 * -2 # 負の無限大の方へ切り下げる
= 5 - 6
= -1
「 Wolfram Alpha は ドナルド・クヌースの切り下げ除算を使っているのかだぜ?
らすいち も見てみようぜ!」
A = -5
B = -3
A - B * floor( A / B )
= -5 - -3 * floor( -5 / -3 )
= -5 - -3 * 1 # 負の無限大の方へ切り下げる
= -5 - -3
= -2
「 あー、 C++ の方法だと 計算の途中で 自己言及 があるが、
ドナルド・クヌースの方は 自己言及 がないんで、 好きな人は好きな定義だな」
Crieitは誰でも投稿できるサービスです。 是非記事の投稿をお願いします。どんな軽い内容でも投稿できます。
また、「こんな記事が読みたいけど見つからない!」という方は是非記事投稿リクエストボードへ!
こじんまりと作業ログやメモ、進捗を書き残しておきたい方はボード機能をご利用ください。
ボードとは?
コメント