はじめに
近年『n で割った余りの世界』というものが世の中のある重要な分野で大活躍している。その分野とは、情報通信の秘密をまもる暗号や通信路での誤りを訂正する技術の分野である。
これは『n で割った余りの世界』 - 長崎大学工学部情報システム工学科 平成 21 年度 AO 入試課題 数学の冒頭の一文である。
以前(2007年9月)、別ブログで「余りが使えるということは意外と知られていない」を書いたのですが、『どっちかというと「余りが使われていることは意外と知られていない」という方が私の感覚的には近いですね。』というコメントを頂きました。
今回は、初心者向けとして軽い感じで書いていきます。
余りとは
「余りとは何よ」と聞く人もいないと思うが、一応説明するとある数を割った時の残りである。例えば、10個のりんごがあったとして3人に同じ数だけ分けるとすると1つ残る、この1つが余りである。
普段生活している上では、「割った余り」を意識すること無いかもしれません。普通の電卓においても余りを求める「Mod」ボタンは存在していませんからね。
余りは、小学生の算数で習いましたね。
例 7÷3＝2 あまり 1 または 7÷3＝2･･･１
文部科学省の現行学習指導要領(シラバス)を見ると小学3年生の算数の段階で習っているようです。
※シラバス (Syllabus) とは、講義・授業の大まかな学習計画のこと
しかし、中学校の数学になった瞬間、「あまり」を一切使わなくなります。
参照：割り算で「余り」を使う計算が数学で全く使われない理由
そして、高校生になると剰余の定理にて「あまり」を「R」記号として出てきます。ここで負数の時の剰余を求める問題などが出てきます。(算数では負数を扱わないため)
余談ですが、割り算の答を”商”と呼ぶのはなぜですか？
余りの性質(正数のみ)
余り(剰余)とは、除算によって「割り切れない」部分を表します。
よって、商除数の値を絶対超えることはありません。
例えば、0から1ずつ加算されるカウント変数を用意し、「カウント値 Mod 4」 とした場合、下記のように余りは0～3を繰り返すようになります。
| カウント値 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 余り | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 |
このことは、一定間隔(～ごと)で何かをしたい場合に使うことが出来るのです。
一定間隔(～ごと)って表現がイマイチだなと思っていたときに、結城浩著「プログラマの数学」を読んでいたら、「剰余はグループ分けである」と書いてありました。納得！
カレンダーを作成する場合
「(日-1) Mod 7」とすることで0～6の値が返り、曜日の位置を揃えることが出来ます。
カレンダーの月ごと表示(表示位置は1日の曜日により位置の調整が必要)
X = (日-1)
行 = X / 7 (7で割る、週が求まる…小数切り捨て)
列 = X Mod 7 (7で剰余、曜日が求まる）
時刻を求める場合
150秒は何分何秒でしょう？
150÷60としてしまうと「2.5」という答えが出てきます。
そこでこの剰余を使います。
X = 150
分 = (X - X Mod 60) / 60 または X / 60(小数切り捨て)
秒 = X Mod 60
2分30秒が求まります。
トランプゲームを作成する場合
4つの種類がそれぞれ13枚の計52枚あります。この52枚をスペード、ハート、クローバ、ダイヤの順に０～５１と連番にしてプログラム上で管理します。
| 種類 | 番号 |
|---|---|
| スペード | 0～12 |
| ハート | 13～25 |
| クローバ | 26～38 |
| ダイヤ | 39～51 |
こうしたとき余りを使うと、0～12までの値のみを求めることができるようになります。例えば、15なら「ハートの2」というように。
| 変数 | 値 |
|---|---|
| Card | ０～51 |
| Mark | ０～3(スペード:0、ハート:1、クローバ:2、ダイヤ:3) |
| Tranp | 0～12 |
Mark = Card / 13 (13で割る、マーク番号が求まる…小数切り捨て)
Tranp = Card Mod 13 (13で剰余、トランプ番号が求まる）
0～51の連番とすることで、プログラム上の管理が簡単になり効率も上がるわけですね。なお、ジョーカーは52にすればいいでしょう。
レポートを作成する場合
仕事として、よくあるのはレポートのプログラムで、例えば５明細ごとに実線を引く、または交互に色を分ける(偶数奇数の判定)といった仕様があります。
明細の場合 カウント値 Mod 5 → (0,1,2,3,4) … 0の時に実線を引く
交互の場合 カウント値 Mod 2 → (0,1) … 1の時に色を変更する。
また、100件ごとに改ページさせるといった場合でも利用されます。
FizzBuzz問題を解く場合
プログラマー採用試験としてFizzBuzz問題のプログラムを書くことがあるようです。
IT会社面接官：「数字を列挙し、3の倍数ならfizz、5の倍数ならbuzz、15の倍数ならfizzbuzzを出力するプログラムを書いてください。」
FizzBuzz問題は剰余を使うことでシンプルに出来ます。
別案：%演算子を使わずとも算数の知識だけでFizzBuzzができる例
for i in range(1,101):
if i % 15 == 0:
print 'FizzBuzz'
elif i % 5 == 0:
print 'Buzz'
elif i % 3 == 0:
print 'Fizz'
else:
print i
これに対して下記のジョークをして話題になりました。
面接を受けている人：「では、まずTensorFlowをインポートします…」
Joel Grusさんの「Fizz Buzz in Tensorflow」です。人工知能によってFizzBuzz問題を解くという更に高度な提案をしたわけです。
私の方でもこのソースを動かしてみた記事「TensorFlowコトハジメ Fizz-Buzz問題」を書きました。
チェックデジットに使用する場合
チェックデジットとは 誤読を防止するための検査数字のことです。
マイナンバー、住民票コード、運転免許証番号など一般に数値コードがあるものには、本来の数値コードにチェックデジット用に1桁が追記されています。
例えば、マイナンバーの12桁(11桁 + 検査用数字1桁)で、運転免許証番号の12桁(10桁＋チェックデジット１桁＋再発行回数１桁）です。ちなみに再発行回数は10回再発行すると 0 に戻らず 1 から始まるそうです。
参照：１２桁の免許証番号の謎
マイナンバーは、モジュラス11 ウェイト2～7の方式で検査用数字を求めています。この際の剰余には「11」が使われます。
- 数値の各桁に、下の桁から２～７の係数（ウエイト）を掛けます。７の次はまた２に戻ります。
- 各桁の結果の合計を求めます。
- 合計を11で割り、余りを求めます（モジュラス）。
- この余りを 11 から引いたもの(11 - 余り)がチェックデジットです。余りが0または1の場合はチェックデジットも「0」になります。
先頭の11桁が「12345678901」の場合、計算結果により検査用数字は「8」となりますので、「123456789018」の12桁となります。
| 元の数字 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 係数 | × 6 | × 5 | × 4 | × 3 | × 2 | × 7 | × 6 | × 5 | × 4 | × 3 | × 2 |
| 元の数字×係数 | 6 | 10 | 12 | 12 | 10 | 42 | 42 | 40 | 36 | 0 | 2 |
| 項目 | 計算式 | 値 |
|---|---|---|
| 合計 | 6 + 10 + 12 + 12 + 10 + 42 + 42 + 40 + 36 + 0 + 2 = 212 | 212 |
| 余り | 212 ÷ 11 = 19 余り 3 | 3 |
| チェックデジット | 11 - 3 = 8 | 8 |
余りの性質(負数有り)
静岡Developers勉強会で2010年にHaskell勉強会を行った際に例題としてライフゲームがありました。
ライフゲームでは二次元のボードを用意し、1つのセルに対して周囲の八方向のセルをチェックする必要があります。
ボードの角をチェックする場合でも、一貫性を持たせるためにボードは上下、左右がつながっているようにすることで、周囲の八方向をチェック出来るようにしている。
そのボードの端をつなげる役割を果たす補助関数 wrap の中で剰余（Mod）を使用していたのですが、何故、それで出来るのか疑問に思ったわけです。
wrap :: Pos -> Pos
wrap (x,y) = (((x-1) `mod` width) + 1,(((y-1) `mod` height) + 1)
普段、私が使用しているVBやC#の言語仕様では、負数の場合 -1 mod 5 = -1 となるため、この式では成り立たないからです。
ところが、Haskellでは負数の場合 (-1) `mod` 5 = 4 となるため、反対側の位置を返すことが出来るわけです。
この負数の剰余について検索してみたところ、言語によって計算結果が違っています。
Modulo operation 言語ごとの一覧が書かれています。
http://en.wikipedia.org/wiki/Modulo_operation
■ C,VB,Java,JavaScript,VBA,Go (Dividend)
10 % 3 = 1
10 % -3 = 1
-10 % 3 = -1
-10 % -3 = -1
■ Perl,Ruby,Python,Lua,Haskell (Divisor)
10 % 3 = 1
10 % -3 = -2
-10 % 3 = 2
-10 % -3 = -1
※言語によっては両方に対応しているものもある。
参考
原始根
nが素数のとき、nには原始根が存在し、nを法とする数は全てこの原始根の冪乗で表せる。例えばn=5の場合、原始根は2である。2を5を法として累乗していくと、{2,4,3,1}となり、1~4までの数字全てが現れる。n=7の場合、原始根は3で{3,2,6,4,5,1}となり1~6全ての数字が現れる。
任意要素数の高速フーリエ変換
本記事をリンクして頂いたので見にいったのですが、書いてあることが理解できなかったので調べてみたら、原始根という面白い法則を知ることが出来ました。
整数論の分野になるようです。
例として2の累乗を5で割った余りを求めた時に、順番はバラバラですが1~4までの数字全てが現れます。他の素数でも同じパターンが出てきます。これを応用したのが先述したリンク先ですね。
$2^1 \bmod 5 = 2 \bmod 5 = 2$
$2^2 \bmod 5 = 4 \bmod 5 = 4$
$2^3 \bmod 5 = 8 \bmod 5 = 3$
$2^4 \bmod 5 = 16 \bmod 5 = 1$
参考
合同式
合同式とは，大雑把に言うと割り算の余りのみに注目した等式のことです。
* 合同式の意味とよく使う６つの性質
* マイクロソフトの数学部で講師をしてきた。合同式で暗号 - Youtube 鈴木貫太郎
終わりに
小学生のプログラミング教育は、「コンピューターが身近に活用されていることや、問題解決をするには必要な手順があることを気付かせる」ことであって、入力の仕方やプログラミング言語を覚えることではないとのこと。
余りが世の中では重要な役割を担っていることを教えてあげると、プログラム教育もより身近になるのではないかと思います。