2の補数表現をちょっと違った見方をしてみる

こんにちは、メモリ事業部の 眞鍋 です。

突然ですが

0.99999999999999….

という数が 「1」 と同じである、

ということは皆さんご存知のことかと思います。

それでは

….99999999999999

という数は何でしょうか？

先程の数を地に向かって「9」が連なる数だと思うと、

今度の数は天に向かって「9」が連なる数であります。

この

….99999999999999

のことを 「∞」 である、と考える方が多いかと思います。

しかし別の視点にたつと 「-1」 だと思える世界があります！

もしやコンピューター関係ない？と読むのをとめず、

最後には 除算に対して面白いテクニックにつながりますので、

少々ご辛抱ください。

まずは この数 が -1 だと思える 3つの証拠を提示します。

….99999999999999  = -1 と思える証拠その1

（乗法的視点）

999….9 × 999….9 の性質をみてみましょう。

9 が 1 個の場合

9 × 9 = 8 1

9 が 2 個の場合

99 × 99 = 98 01

9 が 3 個の場合

999 × 999 = 998 001

9 が 4 個の場合

9999 × 9999 = 9998 0001

このように  00….01 と 「0」  の数がどんどん増えている様子がわかりますでしょうか！

9 が n 個のもの同士の掛け算の下位 n 桁は 「00…01」 となりますので

9 が無限に続くもの同士の掛け算は次の図の通り

「….0000000001」 になると感覚的に思えるのではないでしょうか。

すなわち「1」ですので

….99999999999999 × ….99999999999999 =  1   (!?)

と思えるような気がしてきました。

「(-1) × (-1) = 1」 のことを思い出すと、

この数  ….99999999999999 は -1 のような役割をもっているような気がしてきます！

….99999999999999  = -1 と思える証拠その2

（加法的視点）

続いて

….99999999999999 ＋ 1

を考えてみましょう。これは繰り上がりがずっとおこりつづけて、

まさしく ….0000000000000000 = 0 になります！

この性質はまさに 「-1」 ならではのような気がします。

すなわち (-1) + 1 = 0 を表現しています。

….99999999999999  = -1 と思える証拠その3

（幾何級数的視点）

もっといい加減そうなことをしてみましょう。

1/(1-x) = 1 + x + x^2 + x^3 + x^4 + ・・・  (|x|<1)

といういわゆる幾何級数に、収束条件 |x| < 1 を無視して

x = 10 を入れてみます。すると

1/(1-10) = 1 + 10 + 100 + 1000 + 10000 + ・・・

となります。すなわち、

-1/9 =  ….111111111111111111

という式が得られました。これを 9倍すると

-1 = ….99999999999999

となります。

証拠を3つあげてみた

ここまでくるとなんだか

…99999999999999 は -1 に見えてきましたよね！

ここまでの話は「数学の理論」をつかえばきちんと説明がつくのですが、

感覚で理解するとこのような内容になります。

もっと精密に知りたい方は

例えば 「p-adic Numbers: An Introduction」という本をご参考ください。

さて、ここまでお疲れ様でした。

ここからはコンピューターの整数型について考えたいと思います。

例として 32bit の整数型を考えましょう。もちろん他の bit 長でも同じ議論ができます。

整数型の表現方法を思い出してみる！

int32_t では -1 が  「1…11111」 と 1 が 32個つづく数で表現されていることを思い出します。

これは「2の補数表現」といわれる方式をとっているからでした。

これは先程の …99999999999999 と似ていませんでしょうか！

さっきの世界は 10進の世界、今回は 2進の世界。 9 と 1 の役割。 無限まで続くのと有限でとまる。

これくらいの差であります。

int32_t の世界で (-1) × (-1) をやっても 1 となるのは

別に一度符号型を 1 に揃えてから掛け算をしてその後に符号部をつけているわけではなく、

安直に uint32_t 同士の掛け算だと思い 1…11111 × 1…11111

を実行することで得られます。これは先程の 掛け算の例と似ています！

すなわちこの2の補数表現というのは、

何やら先程導入した考えと、非常に近い考えものと思える気がしてきます。

そこで次の最後に、 int32_t にも先程の「幾何級数」を適用してみましょう。

整数型でもう少し遊んで見る

次のようなシチュエーションはありませんでしょうか？

整数演算で x / (-15)  を計算したい！ (ただし x は 15 の倍数とする。)

除算命令は発行したくないから乗算くらいで高速化できないだろうか…。

ここで先程の幾何級数

1/(1-x) = 1 + x + x^2 + x^3 + x^4 + ・・・  (|x|<1)

に x = 16 を入れてみましょう。またまた |x|<1 の条件を無視する暴挙にでます。

そうすると

1/(1-16) = 1 + 16 + 16^2 + 16^3 + ・・・  16^7 + 16^8 + 16^9 + ・・・

となりますが int32_t の世界は 2^32 で割った余りの世界なので 16^8 = 2^32 = 0 であることを考えると

-1/15 = 1 + 16 + 16^2 + 16^3 + ・・・  16^7

となります。

int32_t には 分数の世界は存在しない？そんなことありません。

そう考えている方は頭が硬い方です。

実際、「 1 + 16 + 16^2 + 16^3 + ・・・  16^7」という数は 「-1/15」 の役割を達成します。

それを確認するべく、ここでつくった「-15」と、「-1/15」の掛け算は

きちんと「1」になりました。

他にも 15 や 30 との掛け算を行うと、それぞれ 「-1」・「-2」 となることも示せます。

除算が乗算になって 高速化の技 として使えそうですね！

ただし、幾何級数

1/(1-x) = 1 + x + x^2 + x^3 + x^4 + ・・・  (|x|<1)

だけではあまり役に立たないため、

次回は私の記事は、このヘンテコ演算テクニックを、もう少し実用的にしたものを紹介したいと思います！

まとめ

• 整数型 は 実は p-adic （p進数） という世界と関連が深いのではないか？ということを紹介した。
• 演算最適化にもテクニックにも繋がりそうなことが少しだけわかった。

関連書籍

• p-adic Numbers: An Introduction

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。