投稿記事

2の累乗の概算法

投稿日時: 2020/12/12 システム管理者

https://elementy.ru/nauchno-populyarnaya_biblioteka/431670/Vsego_lish_stepeni_dvoyki

И. Акулич,«Квант» №2, 2012 に2の累乗の大きな数を求める問題があります.

(問題) 

$$S = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + ... + 2^{63}$$

$$S$$の値を計算しなさい.

$$2 S = 2^1 + 2^2 + 2^3 + 2^4 + ... + 2^{64}$$

$$2S-S=S=2^{64}-1$$

計算機を使えば,$$2^{64}-1=18446 744 073 709551615$$ と計算できるでしょう.
計算機が無くても,許容できる精度でおおよその答えを見つけることができます。原則として、日常生活では(そしてほとんどの自然科学では)2~3%の誤差が許容されます.
$$2^{64}$$をどのように概算したらよいかという問題です.

 $$2^4 = 16$$,$$2^{10} = 1024≒1000=10^3$$ だから,

$$2^{64}=2^4・(2^{10})^6≒16・(10^3)^6$$

しかし,この誤差はかなり大きい.結局,1024を1000に置き換えること続けて6回.
このため,1.024倍の誤差の6乗$$1.024^6$$の誤差になります.

1よりも何倍も小さい数xについては、次の近似式を使うと精度が高い.

$$(1 + x)^n ≒ 1 +n・x$$ これを使うと,

$$(1+0.024)^6≒1+6×0.024=1.144$$

従って,$$2^{64}≒16・10^{18}・1.144=18304・10^{18}$$ と補正します.その結果,

$$S≒2^{64}≒18,304,000,000,000,000,000,000$$となり(18304の後ろに0が18個),
これは正解と1%未満の誤差になります.

■注

1.数字を2のべき乗の和で表すのは,数字を2進数で表すときに必要になります.

たとえば,$$2^{10}+2^9+2^8+2^7+2^6+2^4+2^3+2^2=2042$$, 2進数で表記すると$$11111011100$$

2.この問題の最初の式は,次の一般式の$$m=64$$の場合になります.

$$2^m = (2^{m–1} + 2^{m–2} + ... + 2^0) + 1$$

3.次の性質も役に立ちます:

$$10^{10}=(2・5)^{10}=2^{10}・5^{10}$$

$$2^{10}>10^3$$, $$5^{10}<10^7$$