エンジョイC014回目ホーナーの法則４（2020-06-28）

ほえほえ＠スプシマン @hoehoe1234

６／２８（日）エンジョイCコース午前中は大雨。塾に行くのも大変でした。ツイートはホワイトボードに書いたものだけUPしてますが実際には与太話、ズームによるレビュー、書籍を使った説明などがあります。zoomを有料コースにしたのでオンラインも活用できないかな？などと考え中です。

ほえほえ＠スプシマン @hoehoe1234

新規参加者と復習をかねてmakeコマンドの簡単な説明。塾で使う程度であれば暗黙のターゲットで十分でしょう。オライリーから書籍が無料公開されてます。ありがたいことです。 pic.twitter.com/0cyq5PzF7w

拡大

ほえほえ＠スプシマン @hoehoe1234

ホーナーの法則最終決算。n=100の場合、分解すると2^6(64)+2^5(32)+2^2=100となり各要素が必ず2の累乗の系統になることを利用します。(nは必ず1,2,4,8,16,32,64....の足し算で表せるということ。２進数なので当然なのですが）。興味深いことにx^100はx^64*x^32*x^4で表せます。 pic.twitter.com/INf16bgCth

拡大

ほえほえ＠スプシマン @hoehoe1234

x^100の100を表す部分がx^(64+32+4)であらわせるということですね。これを中学で学んだ展開をするとx^64*x^32*x^4になります。すなわち、ビットが立っているときに内部の累積値yをその時点でのx（2の倍数で増えていく）をかければよいことになります。一見当たり前ですがよくできています。

ほえほえ＠スプシマン @hoehoe1234

これはひろポンさんがUPしてくれたソースコードを解析していっています。数学の式とコードの対応がとても巧妙ですね。悩んだときは式にもどると意図がわかりやすくなります。 pic.twitter.com/LDJbWfVvtv

拡大

ほえほえ＠スプシマン @hoehoe1234

ソースコードは驚くほど巧妙です。最初に1をみつけるまでxの2の累乗を繰り返します。見つかったときの最下位ビットはかならず1です。このケースではその時点でx^4となっています。さらにこの１が反映されているので１ビットずらします。詳しくは白本をみてください。 pic.twitter.com/BcvApdEWVL

拡大

ほえほえ＠スプシマン @hoehoe1234

ホワイトボードでは１ビットずつのシフトごとのビットイメージと行われる操作（単にx*xを実行するのかy*xを実行するのか）を手順通りに追っていきます。手順をおって流れをイメージしてその後にことばにします。前後のループで「シフトの位置が違う」のも巧妙です。

ほえほえ＠スプシマン @hoehoe1234

n=100以外の数字、n=101でもやってみました。きちんとうごきますね。この場合は最初のループは実行されません。任意のnが2^a乗(a=0,1,2,...)で表せるので必ずnを2の累乗の和で表せることが視覚的に確認できます。左に重要なことかいてますね。これはまさにテキスト処理に似ています。 pic.twitter.com/EB3r7yYF9P

拡大

ほえほえ＠スプシマン @hoehoe1234

今回はビットイメージですがこれが"1100100"というテキストだったらどうでしょうか？ビットとみるとちょっと尻込みしてもこのテキストを右にずらしながら計算するとなると「なるほど」となるのではないでしょうか？やはりプログラミングの王道（の１つ）はテキスト処理ですね。

ほえほえ＠スプシマン @hoehoe1234

ちょっと小さい数のn=15で計算してみました。15は1111と表せますね。これは足し算で表すと8+4+2+1になっています。やはり2の累乗の和で表せますね。ソースコードをおって実際にどう動くのかを確認しました。