第104回 変幻ピクセル(後編)

「確かに目で見ればすぐにわかるんですけれど、それをどうやったら計算できるんでしょうか……」とテトラちゃんが言った。
$ \newcommand{\BIGUL}[1]{\underline{\Large#1}} \newcommand{\SUM}{\displaystyle\sum} \newcommand{\BAR}[1]{\bar{#1}} $
登場人物紹介
:数学が好きな高校生(今回はインフルエンザでお休み)。
ユーリのいとこの中学生。のことを《お兄ちゃん》と呼ぶ。
テトラちゃんの後輩。好奇心旺盛な《元気少女》。
ミルカさん:数学が好きな高校生。のクラスメート。長い黒髪の《饒舌才媛》(今回はインフルエンザでお休み)。
リサ:自在にプログラミングを行う無口な女子。赤い髪の《コンピュータ少女》。
読者のみなさん、こんにちは。テトラです(ぺこり)。 いつもご愛読ありがとうございます。 本日は先輩がインフルエンザでお休みなので、 あたしが語り部となります。どうぞよろしくお願いいたします。

それでは前編のあらすじですが、 あたしとユーリちゃんは、いま双倉図書館のイベントに来ています。 コンピュータに詳しいリサちゃんに解説してもらいながら、 スキャナとフィルタとプリンタで楽しんでいるところです。

前編の最後ではリサちゃんが「応用問題」を出題してくれました。 後編はその場面からになります。

詳しくは前編(第103回)をお読みくださいねっ!
解説パネル(フィルタ)


  • スキャナとプリンタの間にはフィルタをはさむことができます。
  • フィルタは $16$ ビットの数を( $16$ 個)受信し、プログラムで処理をして、 $16$ ビットの数を( $16$ 個)送信します。
  • フィルタのプログラムによって絵を変形してみましょう。

双倉図書館《変幻ピクセル》イベント会場にて

リサ「応用問題」

解説パネル(問題)
次のように画像を変形するには、 どんなフィルタを作ればいいでしょうか。


左側は、フィルタがスキャナから受信する画像です。
右側は、フィルタがプリンタに送信する画像です。

ユーリ「わかったよ、簡単!」

テトラ「ユーリちゃん、早いですね……あ、あたしはまだ」

ユーリ「これはねー、左右を逆転すればいーんだよ! こんな感じだよね」

テトラ「それはそうなんですけど、フィルタが受信した《数》で行うにはどうするか、 が問題なんだと思いますよ。 どういう計算をすればこのような逆転ができるんでしょう」

ユーリ「それはねー……これから考える」

テトラ「あっ、そうです! こういうときこそ、ポリア先生の問いかけを使うべきですね。たとえば《似た問題を知っているか》」

ユーリ「知ってる! ほらさっき、右 $8$ 個と左 $8$ 個を交換したじゃん?(前編(第103回)参照) それと同じよーにすればいーんだよ」

テトラ「はい、あのときは $f \gg 8$ で $8$ ビットを右にざざざざっと動かしましたね……」

ユーリ「だったら、 $f \gg 15$ にすれば、左端の $f_{15}$ は一番右に来るね!」

テトラ「はい。同じように、 $f \ll 15$ にすれば、右端の $f_{0}$ は一番左に来ます。それはいいんですが……」

ユーリ「 $f \gg 13$ にすれば、 $f_{14}$ は右から二番目に動くよ……あ」

テトラ「それじゃ、だめですよね。 $f_{14}$ は確かに右から二番目になりますが、 $f_{15}$ と $f_{13}$ が残ってしまいます」

ユーリ「そっかー! 《 $f_{14}$ だけ取り出すこと》ができればいいのに」

リサ「論理積」

論理積(ビット単位) $$ \begin{align*} 0 \mathrel{\&} 0 &= 0 && \\ 0 \mathrel{\&} 1 &= 0 && \\ 1 \mathrel{\&} 0 &= 0 && \\ 1 \mathrel{\&} 1 &= 1 && \text{両方が $1$ のときだけ $1$ } \\ \end{align*} $$

テトラ「論理積は、両方が $1$ のときだけ $1$ ですね……わかりましたよ。これを使えば、 $f_{14}$ だけ取り出せます」

ユーリ「どーやるの?」

テトラ「$(0000 0000 0000 0010)_2$という数との論理積を作るんですよ! そうすれば右から二番目だけが残りますから!」

ユーリ「なーる!」

左右反転フィルタ

リサ「まとめたプログラム」

左右反転フィルタFILTER-REVERSE

テトラ「これは……何だかすさまじいですね」

リサ「ループにまとめたプログラム」

左右反転フィルタFILTER-REVERSE-LOOP(ループを使った)

テトラ「え、これは……」

リサ「同じフィルタ」

テトラ「FILTER-REVERSEとFILTER-REVERSE-LOOPは同じ……なんですか」

ユーリ「さっきとずいぶん違うみたい。FILTER-REVERSEだとシフトが $16$ 個もあったけど……」

リサ「 $\textit{RL7}$ からのインナーループで」

テトラ「シフトは $\textit{RL11}$ と $\textit{RL12}$ にありますね……」

ユーリ「 $(f \gg S) \mathrel{\&} R$ と $(f \ll S) \mathrel{\&} L$ のこと?」

テトラ「文字がたくさん出てきてよくわからないんですが、たとえば、 $j = 0$ のときはどうなるんでしょう」

FILTER-REVERSE-LOOPで、 $j = 0$ のとき
$$ \left\{\begin{array}{llll} L &= 1 \ll (15 - 0) &= ( 1000 0000 0000 0000)_2 \\ R &= 1 \ll 0 &= ( 0000 0000 0000 0001)_2 \\ S &= 15 \\ \end{array}\right. $$
$j = 0$ のときのシフトのようす
$$ \left\{\begin{array}{llll} (f \gg S) \mathrel{\&} R & = (f \gg 15) \mathrel{\&} ( 0000 0000 0000 0001)_2 \\ (f \ll S) \mathrel{\&} L & = (f \ll 15) \mathrel{\&} ( 1000 0000 0000 0000)_2 \\ \end{array}\right. $$

ユーリ「うわすごい! これで、右端と左端が取り出せてる!」

テトラ「ははあ……FILTER-REVERSE-LOOPの $\textit{RL7}$ からの繰り返し $8$ 回が効いているんですね」

ユーリ「リサさんすごい!」

リサ「《さん》は不要」

テトラ「鏡のように左右を逆にするだけのことなのに、複雑なプログラムになるんですね……」

リサ「トリック使用」

ユーリ「トリック?」

左右反転フィルタFILTER-REVERSE-TRICK(トリックを使った)

テトラ「え?」

ユーリ「え?」

リサ「 $M_1,M_2,M_4,M_8$ と $\textit{RT9}$ からがトリック」(咳)

テトラ「これは……何をやっているんでしょう」

ユーリ「あれ? FILTER-REVERSEにあった $g$ がなくなってる」

テトラ「 $f$ を、 $\textit{RT9}$ からの $4$ 行で書き換えているんだと思うんですが……」

ユーリ「テトラさん、図に描いて研究しよーよ!」

テトラ「そ、そうですね……」

あたしとユーリちゃんは、リサさんが《トリック》と呼んだFILTER-REVERSE-TRICKを解読するため、 二人で図を描いて……心の底から驚きました。
この続きは有料会員登録をすると
読むことができます。
cakes会員の方はここからログイン

1週間無料のお試し購読する

cakesは定額読み放題のコンテンツ配信サイトです。簡単なお手続きで、サイト内のすべての記事を読むことができます。cakesには他にも以下のような記事があります。

人気の連載

おすすめ記事

ケイクス

この連載について

初回を読む
数学ガールの秘密ノート

結城浩

数学青春物語「数学ガール」の中高生たちが数学トークをする楽しい読み物です。中学生や高校生の数学を題材に、 数学のおもしろさと学ぶよろこびを味わいましょう。本シリーズはすでに12巻も書籍化されている大人気連載です。 (毎週金曜日更新)

この連載の人気記事

関連記事

関連キーワード

コメント

shiano_blue できる気のしない宿題… 5年以上前 replyretweetfavorite

fall_twtr ひゃー!縁取り難しい!落ち着いたらじっくり見てみよう。 モジュール分割は基本。 5年以上前 replyretweetfavorite

wed7931 「僕」がいないからかもしれないけど、リサが「乱択アルゴリズム」よりもいきいきしてる感じがする。 5年以上前 replyretweetfavorite

l_sigma (FILTER-REVERSE-LOOPにj←j+1がない・・・) 5年以上前 replyretweetfavorite