「＋1」だけで四則演算をするには？：いまから始めるアルゴリズム（1）（2/2 ページ）
プログラミングの基礎となる考え方、アルゴリズムを理解しているだろうか？ ITエンジニアに贈る、アルゴリズム入門。
巨大な数同士の掛け算は？
もう1つの例として、大きな数値の取り扱い方について考えてみたいと思います。
人間は理論上、どんな大きな値でも計算することができます。ただし暗算の名人でなければ、紙と鉛筆を使うでしょう。紙に書ききれないぐらい大きな値だとしても、もう1枚紙を持ってきて継ぎ足せば、計算することができますね。
しかし、コンピュータが1つの変数で扱える数値の大きさは、32ビットや64ビットで表現できるものまでです。そういった1つの変数で扱えない大きな数字を扱うことになった場合、コンピュータにどう処理させますか？
*** 一部省略されたコンテンツがあります。PC版でご覧ください。 ***
それを考えるために、皆さんが実際に計算をするとき、どうやっているか思い出してみましょう。2けた同士の掛け算を解く方法を考えてみます。「53×72」を計算する場合、多くの人は紙に書いて計算するでしょう。1けた同士の掛け算を複数回実施し、出てきた積の足し算を行うことで答えが得られます（図2）。3けた同士の掛け算、4けた同士の掛け算も、時間はかかりますが同様に行えます。
コンピュータが1つの変数で扱えない大きな数字を扱う場合も、同じように考えます。1つの数字としては扱えなくても、上位何けた、下位何けたに分割し、複数の変数の組み合わせとすれば扱うことができます。下位×下位、下位×上位、上位×下位、上位×上位を計算し、足し合わせればいいのです（足し算時の繰り上がりには注意してください）。
以下は、このアルゴリズムをC言語とJavaで表したものです。
*** 一部省略されたコンテンツがあります。PC版でご覧ください。 ***
現在よく使われているPCは32ビットで動作するものがほとんどですが、今後64ビットになれば整数型で扱える数値の範囲が広がります。いま考えたような方法を使わなくても大きな値が計算できるようになることには、大きな意味があります。
4回の掛け算が1回でできるようになれば、性能は4倍になりますよね。逆に変数の型を間違えれば、本来の性能の4分の1しか発揮できないということにもなりかねません（実際にはコンパイラで最適化される場合もありますので、一概にはいえませんが）。
変数を宣言するときに小さ過ぎる値を使ってしまうと、あとあと計算で困ることがあるかもしれません。無駄な処理を省き、長く使ってもパフォーマンスが落ちにくい設計を心掛けましょう。
今回は、コンピュータで加減乗除、1つの変数では扱えないような大きなけたの掛け算をする場合の考え方を紹介しました。次回は数値や文字列の並べ替えや検索の仕方、それぞれの方法による処理速度の違いについて考えてみたいと思います。
筆者紹介
鹿野恵祐
1978年夏、東京生まれ。東京電機大学理工学部経営工学科卒業後、システムインテグレータにてシステム設計・構築を担当。「長期にわたって使えるシステム」を模索する日々。最近は、コンピュータ以外にも視野を広げようといろいろチャレンジ中。西武ライオンズファン歴24年。好物は鶏の空揚げ。
Copyright © ITmedia, Inc. All Rights Reserved.