剰余演算と周期
割った余りで位置を表す方法と、周期をまたぐ計算を学びます。
説明
同じ長さで繰り返す位置を表すとき、割り算の余りが使えます。たとえば0〜6で曜日を表せば、7日後には元の番号に戻ります。余りが同じ整数同士を、同じ周期内の位置として扱えるためです。
このモジュールでは、7で割った余りを一覧にし、日数を進めた場合と戻した場合を計算します。次に加算・乗算での剰余の性質を確かめ、最後に周期を変えたときの位置の変化を扱います。ここでは割る数を正の整数とします。
10〜6へ戻る番号
0〜15を7で割った余りに変換します。
period = 7周期の長さ; [(n, n % period) for n in range(16)]整数と周期内の位置0〜6の後は再び0〜6となります。7、14という周期の境目で0へ戻ります。
2割った商と余りの関係
23を7で割った商と余りを求めます。
n = 23元の番号; quotient, remainder = divmod(n, period)商と余り; quotient, remainder, quotient * period + remainder元の番号への復元商3、余り2です。23=3×7+2となり、何周したかが商、現在の位置が余りです。
3同じ余りを持つ整数
余り2に対応する整数を、0〜29から集めます。
[n for n in range(30)0〜29の整数 if n % period == 2余り2の整数だけ]2、9、16、23です。隣同士の差はいずれも7で、同じ周期内の位置を表します。これらは7を法として合同であるといいます。
4現在の位置から日数を進める
月曜を0とする番号で、金曜を4とします。10日進めた後の曜日番号を計算します。
day = 4; elapsed = 10現在位置と経過日数; (day + elapsed) % period進めた後の位置結果は0で、月曜です。10日をそのまま加えてから余りを求めても、周期内の位置が得られます。
5経過日数を先に周期内へ収める
10日は1週間と3日です。経過日数の余りだけを加えても同じ位置になります。
(day + elapsed) % period全日数を加える, (day + (elapsed % period)) % period経過日数の余りを加えるどちらも0です。周期の整数倍だけ進む部分は位置を変えないため、先に取り除いて構いません。
6負の方向への移動
月曜の3日前の位置を求めます。Pythonでは正の7で割った余りは0〜6になります。
day = 0月曜の位置; day - 3, (day - 3) % period移動後の整数と曜日番号, divmod(-3, period)負数の商と余り−3を7で割ると商−1、余り4です。−3=(−1)×7+4なので、位置4の金曜になります。負数の剰余の定義は言語によって異なるため、他言語へ移す場合は仕様の確認が必要です。
7乗算でも余りを先に使える
20×13の結果を7で割った余りと、各数の余りを掛けた結果を比較します。
a, b = 20, 13二つの整数; (a * b) % period積の余り, ((a % period) * (b % period)) % period各余りの積から求めるどちらも1です。各数から7の整数倍を取り除いても、積の余りは変わりません。最後の積についても余りを取る必要があります。
8周期を変えると同じ番号の位置も変わる
番号23の位置を、周期7と周期8で求めます。
[(length, 23 % length周期とその中の位置) for length in (7, 8)二つの周期]周期7なら位置2、周期8なら位置7です。余りだけを見ても、何を周期にしているかが分からなければ、位置の意味を決められません。
まとめ
正の周期pで割った余りは、0〜p−1の位置を表します。同じ余りを持つ整数はpの整数倍だけ離れています。
周期内の位置は、加算や乗算の前に各値の余りを取っても計算できます。負数を扱う場合は言語の剰余の規則も確認します。
操作履歴と解説を振り返れます。
Python 3
period = 7; [(n, n % period) for n in range(16)][(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 0), (8, 1), (9, 2), (10, 3), (11, 4), (12, 5), (13, 6), (14, 0), (15, 1)]
n = 23; quotient, remainder = divmod(n, period); quotient, remainder, quotient * period + remainder(3, 2, 23)
[n for n in range(30) if n % period == 2][2, 9, 16, 23]
day = 4; elapsed = 10; (day + elapsed) % period0
(day + elapsed) % period, (day + (elapsed % period)) % period(0, 0)
day = 0; day - 3, (day - 3) % period, divmod(-3, period)(-3, 4, (-1, 4))
a, b = 20, 13; (a * b) % period, ((a % period) * (b % period)) % period(1, 1)
[(length, 23 % length) for length in (7, 8)][(7, 2), (8, 7)]
演習完了