読書メモ:プログラマの数学(3)

剰余

剰余は周期性をみつける道具

  • 剰余を使って考えると周期性をみつけることができる。
  • 周期性を見つけると、大きな数の問題を扱いやすくなる。(一億日後は何曜日か?とか)
  • 10の100乗みたいに解く数がとても大きくなっても、同じように位をあげながらあまりを書き出していくと周期性を見つけることができる。
  • 「物事を詳しく調べよう」というときに、「こまかいところまで正確に把握しよう」ではなく、「的確な分類」の方が役に立つときもある。

周期性の見抜き方

  • あんまりにも大きな数を調べたい時・・・今調べる必要があるのはどの位の数なのか?を考える。
  • パリティチェックだとたくさんの並べ方があるけれど、奇数と偶数の2グループに分けて考える。(最後の1ビットがどちらに所属するかを示している。)

プログラマの数学

プログラマの数学