わえなび ワード&エクセル問題集

当サイトはWordとExcelの実力を鍛える最高水準の特訓問題集です。リンクを張るのは自由です。みんなで勉強しましょう!

LOG関数で2を底とする対数(二進対数)とO(logN)の意味を知ることは情報処理の基本である【Excel】

対数のlogを勉強するときにまず最初に習得するのは常用対数です(参考:【LOG・LOG10関数】Excelで10の累乗と常用対数が使えたら数値の桁数が計算できます)。

常用対数を習得したら次に習得するのが2の累乗と2を底とする対数です。学生の時に、2,4,8,16,32・・・と2の累乗を覚えた人もいるのではないでしょうか?

大人であれば、2を10回かけたら1024(=約1000)になることを知っておいても損はないでしょう。携帯電話の「ギガ」はもともと2を30回かけると約10億=1ギガの情報量になるところからきています。2の累乗と2を底とする対数を理解することは情報処理を理解する第一歩と言っても過言ではありません。

そこで、今回は、Excelで2の累乗と2を底とする対数を求める方法とその応用について解説します(2進数については深入りしません)。

目次

1.まずはExcelで2の累乗の性質を考えてみよう

(1)両手で1000まで数える

問題

10本の指を用いて1000まで数えるにはどうすれば良いか述べなさい。なお、10本の指の代わりに10枚のカードやコイン等を用いてもよい(以下、同じ)。 

f:id:waenavi:20210116193452j:plain

 

解説

小学生なら両手で10まで数えられますが、指が器用に動く大人は1000まで数えられるというのは有名な話です。

f:id:waenavi:20210116193523j:plain

 

1本の指について「曲がっている」「伸びている」の2つの状態があるとすれば、2本の指で4通りの状態を表すことができます。

f:id:waenavi:20210116193555j:plain

 

これは100円玉と10円玉で表すことのできる金額と同じです。110円、100円、10円、0円の4通りです。

f:id:waenavi:20210116193638j:plain

 

一般にON/OFF、YES/NO、ある/無い、赤白など1つの項目について2つの相反する状態がある(2つしか選択肢がない)場合、2つの項目で4つの状態を表すことができます。

f:id:waenavi:20210116193707j:plain

 

これを3つに増やすとさらに倍の8通り、4つに増やすとさらに倍の16通りとなります。これを続けていくと10個の場合は2を10回掛けて1024通りとなります。

f:id:waenavi:20210116193752j:plain

 

(2)指に数字を書いてみる

問題

次の図のように右の指から順に2の累乗を書いたとする。0から1023までの数を表現できることをExcelで確認しなさい。なお、この記事において2の累乗は2の整数乗のことをいうこととする(以下、同じ)。

f:id:waenavi:20210116193833j:plain

 

解説

指を全て曲げると数字が見えないので0と考えます。

f:id:waenavi:20210116193906j:plain

 

指を伸ばすと数字が見えるので、その数字を合計します。例えば、左手の親指(512)+右手の小指(16)+薬指(8)+中指(4)の場合は540という数を表しているものと考えます。

f:id:waenavi:20210116193929j:plain

 

Excelに2の累乗を入力します。

f:id:waenavi:20210116194009j:plain

 

ここでセルA4に次の数式を入力します。

  • =MOD(INT((ROW()-4)/2^(10-COLUMN())),2)

f:id:waenavi:20210116194105j:plain

 

そして、セルJ1027までコピーします。この数式は指を開いた場合を「1」、指を曲げている場合を「0」と表示する計算式であり、1024通りすべてのパターンを表示することができます。

f:id:waenavi:20210116194502j:plain

 

さきほどの左手の親指(512)+右手の小指(16)+薬指(8)+中指(4)は、544行目に表示されています。

f:id:waenavi:20210116194717j:plain

 

指の数字の合計を求めるには3行目と各行をそれぞれ掛けてその合計を求めます。SUMPRODUCT関数を使います。3行目の数値を掛けることによって指を開いている場合は指に書いてある数字、曲げている場合は0となります。

  • =SUMPRODUCT($A$3:$J$3,A4:J4)

f:id:waenavi:20210116194902j:plain

 

合計を求めると0から始まる連番になります。最後は1023となります。これで10本の指を用いて0から1023までの数を表現できることを示すことができました。

f:id:waenavi:20210116194936j:plain

 

このように、10項目に対して1から512までの2の累乗の数を割り当てると、それらの有無を切り替えることによって0から1023までの数をもれなく表現することができます。512は29、1023は210-1です。

f:id:waenavi:20210116201753j:plain

 

いっぱんに、N項目に対して1から2N-1までの2の累乗の数を割り当てて、その有無を切り替えることによって、0から2N-1までのすべての数をもれなく表現することができます。

f:id:waenavi:20210116195136j:plain

 

2.二進対数

(1)指数と対数の違いは何か

問題

さきほどの問題で、1から1023までの整数値はそれぞれ2を何乗した値か。

解説

例えば、2を3乗すると8になります。これは累乗を計算していますが、このときの3乗のことを「指数」と言います。

f:id:waenavi:20210116201841j:plain

 

しかし、いっぱんに指数関数的増加、指数関数的成長などと言うときの「増加」は、指数そのものではなく累乗をした結果の増加を指しており、2倍するごとにものすごく増えていくことを意味しています。

f:id:waenavi:20210116201901j:plain

 

これに対して、指数そのものを求める計算のことを「対数logarithm)」と言います。つまり、「指数を求める」と言うのと「対数を求める」と言うのは基本的に同じことを表しています。

f:id:waenavi:20210116201934j:plain

 

指数と対数では何が違うかと言うと、指数関数は指数が増えると累乗した結果がどうなるかを考えている(通常はものすごく増える)のに対して、対数関数は累乗した結果が増えると指数がどうなるかを考えています。指数と対数では逆の考え方をしています。

f:id:waenavi:20210116202213j:plain

 

そこで、累乗した結果が増えると指数がどうなるかをExcelで考えてみましょう。Excelで対数を求めるには、LOG関数を使います。LOG関数は、第1引数に累乗した後の値、第2引数に累乗する前の値を指定します。ちなみに、累乗した後の値のことを「真数(しんすう)」、累乗する前の値のことを「(てい)」と言います。

f:id:waenavi:20210116202254j:plain

 

2を何乗すれば良いかを求めるには、累乗する前の値(底)を2にします。2を底とする対数のことを「二進対数binary logarithm)」と言います。

  • =LOG(K12,2)

f:id:waenavi:20210116202407j:plain

 

これで8は、2を3乗した数であることが分かります。

f:id:waenavi:20210116202425j:plain

 

LOG関数で2を底とすると、それぞれ2を何乗した値かを求めることができます。累乗した後の値(真数)が大きくなると、対数も大きくなります。

f:id:waenavi:20210116202450j:plain

 

ちなみに、真数を0とするとエラーになります。それは、2を何回掛けても0にはならないからです。

f:id:waenavi:20210116202517j:plain

 

(2)小数について

問題

2を底とする対数(二進対数)を求めたとき、13の対数が約3.7になる理由を説明しなさい。

解説

2を底とする対数を求めると、ほとんどの数について小数になります。例えば、13の対数は約3.7となっています。

f:id:waenavi:20210116202613j:plain

 

これは、2の約3.7乗が13であることを表しているのですが、2を3.7回掛けたら13になるというのは意味がよく分かりませんね。

f:id:waenavi:20210116202649j:plain

 

3.7回は、3回と0.7回に分けて考えます。

f:id:waenavi:20210116202715j:plain

 

0.7乗は0.1乗を7回かけたものと考えることができます。

f:id:waenavi:20210116202741j:plain

 

そして、2の0.1乗に該当する数は10回かけたらちょうど2になりますから、2の10乗根(約1.072)と考えることができます。0.01乗は100乗根、0.001乗は1000乗根、0.0001乗は10000乗根です。

f:id:waenavi:20210116202812j:plain

 

このように、指数(対数)を小数で表すことは可能であり、小数を使うことによって、0より大きいすべての数について対数を求めることができます。

f:id:waenavi:20210116202833j:plain

 

(3)整数乗を抽出する

問題

対数が整数になっているものを抽出しなさい。

f:id:waenavi:20210116203358j:plain

 

解説

整数であることを判定するにはINT関数で小数部分を切り捨てればよいです。対数が整数になっているものがTRUEとなります。

  • =L5=INT(L5)

f:id:waenavi:20210116203337j:plain

 

オートフィルタを設定して、TRUEになっている行を抽出します(参考:【Excel】オートフィルタの設定と解除、条件にあう行を抽出する方法の総復習)。2の累乗(整数)だけ抽出すると100・・・になっています。つまり、指1本だけ開いている状態だと2の累乗になることが分かります。

f:id:waenavi:20210116203540j:plain

 

(4)指の本数と対数の関係

対数が3より小さい数に注目してみましょう。0から7までの数を3本の指で表現できることが分かります。

f:id:waenavi:20210116203618j:plain

 

今度は4より小さい数を考えます。0から15までの数を4本の指で表現できることが分かります。

f:id:waenavi:20210116203636j:plain

 

3本の指で表現できる8通りの数はすべて対数が3より小さいです。また、4本の指で表現できる16通りの数はすべて対数が4より小さいです。

f:id:waenavi:20210116203817j:plain

 

いっぱんに、N本の指で、0から2N-1までの2N通りの表現ができます。そして、N本の指で表現できる数の対数はNより小さくなります。

f:id:waenavi:20210116211605j:plain

 

3.ビットとバイト

問題

0から65535までの数(全部で65536通り)を、0と1だけを使って表現するのに何ビット必要か。また、1600万通りの状態を表現するのに何バイト必要か。 

解説

さきほどの問題で、指を伸ばした状態が1、指を曲げた状態が0です。

f:id:waenavi:20210116204034j:plain

 

このように2つの相反する状態を1と0で表現することを「2進数」と言います。例えば、1023は2進数で言えば1が10個で、10本の指で表現できる最大の数です。

f:id:waenavi:20210116204059j:plain

 

ここで、65535の対数を求めます。底は2です(以下、省略)。

  • =LOG(65535,2)

f:id:waenavi:20210116204152j:plain

 

16より少し小さい数になります。前述のように、対数が16より小さいということは、65535までの数は必ず16本の指で表現できるということです。2進数で言えば16桁あれば良いということになります。

f:id:waenavi:20210116204543j:plain

 

2進数の桁数のことを「ビットbit)」と言います。16桁であれば16ビットです。ちなみに、2の16乗は65536なので、それより1小さい65535は16ビットで表現できる最大の数と言えます。

f:id:waenavi:20210116204635j:plain

 

同様に1600万の対数を求めます。

  • =LOG(16000000,2)

f:id:waenavi:20210116204711j:plain

 

24より少し小さい数になりますから、24ビット(24本の指)で1600万通りの表現が可能であることが分かります。8ビットのことを「バイト」と言います。24ビットは3バイトです。

f:id:waenavi:20210116204753j:plain

 

4.対数を使って2倍にする回数を求める

(1)倍にする回数

問題

新聞紙の厚さを0.1mm(10000分の1メートル)として何回折ったら東京スカイツリーの高さを超えるか。

f:id:waenavi:20210116204828j:plain

 

解説

新聞紙を折り曲げると2倍の厚さになります。これを繰り返して634万倍を超えるのは何回目かを計算しようとしています。つまり、2を何回掛けたら634万になるかを求めようとしているので、対数を使うことになります。

f:id:waenavi:20210116204910j:plain

 

2を底とする対数を求めます。

  • =LOG(B2/B1,2)

f:id:waenavi:20210116204941j:plain

 

22.6なので切り上げをします(参考:【Excel関数】ROUNDUPとROUNDDOWN、切り上げ、切り捨て、四捨五入の練習問題)。新聞を23回折り曲げたらよいことに分かります。

  • =ROUNDUP(LOG(B2/B1,2),0)

f:id:waenavi:20210116205117j:plain

 

このほか、1秒間に個体数が2倍になる細菌や、音の長さが2倍になる音符のように、2倍にする回数を求めるには2を底とする対数(二進対数)を取ります。

f:id:waenavi:20210116205215j:plain

 

(2)半分にする回数

問題

夏の高校野球全国大会(甲子園)では地方大会を勝ち上がった50チームがトーナメント戦で対戦する。すべてのチームがほぼ同じ試合数で優勝できるものとするとき、最大で何試合対戦すれば優勝できるか。ただし、引き分け再試合等はカウントしない。

f:id:waenavi:20210116205252j:plain

 

解説

50チームがトーナメント1回戦を戦うと半分の25チームが敗退します。勝ち上がるごとにチーム数は半分になっていき、最終的に決勝戦で勝った1チームが優勝となります。試合をするごとにチーム数が半分になるのですから、50を何回半分にすれば1になるかを求めます。半分にする回数を求めるのと、2倍にする回数を求めるのは同じです。2を底とする対数です。

  • =LOG(B1,2)

f:id:waenavi:20210116205322j:plain

 

小数の場合は切り上げとなります。シード校は5試合勝てば優勝できますが、シードでないチームは6試合勝てば優勝できます。

  • =ROUNDUP(LOG(B1,2),0)

f:id:waenavi:20210116205409j:plain

 

5.探索と計算量

問題

30gのボールが100個あるとする。この中に31gのボールが1個だけ混ざっていることが分かっている場合、何回計量すればその1個を見つけることができるか。

f:id:waenavi:20210116205726j:plain

解説

(1)線形探索

同じ重さのボールが100個あるうちの1個だけ重さが異なる場合に、その1個を探すには1つずつ取り出して、1個の重さを量る方法が最も単純です。これは、100本のくじの中に当たりくじが1本だけ含まれていて、1本ずつくじを引くのと同じです。

f:id:waenavi:20210116205839j:plain

 

何回目に当たりが出るかにかかわらずX回目に当たりが出る確率はすべて1/100です。運が良ければ1回目でそのボールに当たるかもしれません。99回ボールを量ってすべて同じ重さであれば残りの1個で確定します。

ボールの重さを量る平均回数を計算すると49.49回となります(計算方法は省略)。しかし、よく考えたら、1回目に当たるのか100回目に当たるのか分からないけど、当たる確率は同じですから平均するとだいたい50回前後になることは計算しなくても分かると思います。

f:id:waenavi:20210116205540j:plain

 

ボールがn個ある場合、そこから特定の1個を探すのに必要な作業回数の平均は約n/2回、つまりボールの個数にほぼ比例します。

f:id:waenavi:20210116210026j:plain

 

このような地道な探し方のことを「線形探索」と言います。そして、nにほぼ比例する作業回数になることを、O記法(オーダー記法)を用いて「O(n)」と表現することがあります。例えば、データがn個あってその中から特定の1個を探すのに必要な計算回数がO(n)だとしたら、データが100倍になれば計算にかかる時間も100倍になってしまうわけです。探し方は単純ですが、大量のデータを処理するのに時間がかかってしまいます。

f:id:waenavi:20210116210053j:plain

 

(2)二分探索

今度は1個ずつではなく、何個かまとめて量ることを考えてみましょう。

100個のボールのうち半分の50個を量ったとします。もしちょうど30gx50=1500gであれば、これら50個については量る必要がなくなります。また、1501gであれば残りの50個を量る必要がなくなります。このように1回の計量で全体の半分の候補を消すことができます。同様に残った50個のうち半分の25個の計量をすれば候補が25個になります。

f:id:waenavi:20210116210153j:plain

 

どんどん半分にしていくと(割り切れない時は切り上げ)、13個、7個、4個、2個、1個となり、最大7回計量すれば良いことが分かります。これは前述のトーナメント戦をしているのと同じです。

半分にする回数を求めます。切り上げで7回となります。

  • =ROUNDUP(LOG(100,2),0)

f:id:waenavi:20210116210223j:plain

 

ボールがn個ある場合、そこから特定の1個を探すのに必要な作業回数の平均はボールの個数を半分にする回数(二進対数)、つまり約LOG(n,2)回になります。100個のボールを探索するのに7回で済みますから、ボールの個数が100倍になっても探す回数は7倍程度でおさまるということになります。

f:id:waenavi:20210116212033j:plain

 

このように2つのブロックに分けながら探す手法のことを「二分探索」と言います。そして、作業回数が対数になることを、O(log n)またはO(logN)と表現することがあります。データがn個あってその中から特定の1個を探すのに必要な計算回数がO(log n)であれば、データが100倍になっても計算量は7倍程度となります。線形探索O(n)と比べて効率が良いことが分かります。情報処理では、必要なデータを探す回数または計算量は非常に重要です。

f:id:waenavi:20210116210629j:plain

 

6.対数のグラフをかいてみよう

問題

xを1から30までの値として、散布図を用いてy=xとy=log2xのグラフをかきなさい。

f:id:waenavi:20210116210710j:plain

 

解説

A列に1から30までの整数を入力します。y=xであればA列の数値を参照するだけです。

  • =A2

f:id:waenavi:20210116210901j:plain

 

数学では、2を底とする対数LOG(x,2)のことを小さい数字を使ってlog2xと表します。

  • =LOG(A2,2)

f:id:waenavi:20210116210927j:plain

 

散布図(平滑線とマーカー)を挿入します(参考:【Excel散布図】2つの数量の関係を表すグラフを「折れ線」で作るのは間違いです)。これで完成です。yがxに比例するときは、xが増えるとyも同じように増えていきます。これに対して、対数の場合はxが増えてもyはそんなに増えません。

f:id:waenavi:20210116211322j:plain

 


解説は以上です。


 


Copyright(C)2018-2021 waenavi, All rights reserved. [www.waenavi.com 定礎 平成三十年八月]
Youtube | 公式サイト | twitter | 著作権 | 運営者情報 | お問い合わせ