このブログは、株式会社フィックスターズのエンジニアが、あらゆるテーマについて自由に書いているブログです。
こんにちは、メモリ事業部の 眞鍋 です。
突然ですが
0.99999999999999….
という数が 「1」 と同じである、
ということは皆さんご存知のことかと思います。
それでは
….99999999999999
という数は何でしょうか?
先程の数を地に向かって「9」が連なる数だと思うと、
今度の数は天に向かって「9」が連なる数であります。
この
….99999999999999
のことを 「∞」 である、と考える方が多いかと思います。
しかし別の視点にたつと 「-1」 だと思える世界があります!
もしやコンピューター関係ない?と読むのをとめず、
最後には 除算に対して面白いテクニックにつながりますので、
少々ご辛抱ください。
まずは この数 が -1 だと思える 3つの証拠を提示します。
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」ですので
と思えるような気がしてきました。
「(-1) × (-1) = 1」 のことを思い出すと、
この数 ….99999999999999 は -1 のような役割をもっているような気がしてきます!
続いて
を考えてみましょう。これは繰り上がりがずっとおこりつづけて、
まさしく ….0000000000000000 = 0 になります!
この性質はまさに 「-1」 ならではのような気がします。
すなわち (-1) + 1 = 0 を表現しています。
もっといい加減そうなことをしてみましょう。
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
となります。
ここまでくるとなんだか
ここまでの話は「数学の理論」をつかえばきちんと説明がつくのですが、
感覚で理解するとこのような内容になります。
もっと精密に知りたい方は
例えば 「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)
だけではあまり役に立たないため、
次回は私の記事は、このヘンテコ演算テクニックを、もう少し実用的にしたものを紹介したいと思います!
keisuke.kimura in Livox Mid-360をROS1/ROS2で動かしてみた
Sorry for the delay in replying. I have done SLAM (FAST_LIO) with Livox MID360, but for various reasons I have not be...
Miya in ウエハースケールエンジン向けSimulated Annealingを複数タイルによる並列化で実装しました
作成されたプロファイラがとても良さそうです :) ぜひ詳細を書いていただきたいです!...
Deivaprakash in Livox Mid-360をROS1/ROS2で動かしてみた
Hey guys myself deiva from India currently i am working in this Livox MID360 and eager to knwo whether you have done the...
岩崎システム設計 岩崎 満 in Alveo U50で10G Ethernetを試してみる
仕事の都合で、検索を行い、御社サイトにたどりつきました。 内容は大変参考になりま...
Prabuddhi Wariyapperuma in Livox Mid-360をROS1/ROS2で動かしてみた
This issue was sorted....