++C++; // 未確認飛行 C ブログ

http://ufcpp.net/

多項式計算

leave a comment »

そうそう、さっきの話の余談。

64x7-112x5+56x3-7x

という式をプログラム化しなさいというような問題も出したときの話。

まあ、べたに

まずは素直に。

var y = 64 * x * x * x * x * x * x * x – 112 * x * x * x * x * x + 56 * x * x * x – 7 * x;

そもそもこれを自力で書ける人がそんなにいなかったり。

できない人は、「* x」の数を間違えてるとかそういう話ではなくて、「64x」と書いちゃうとか「* が多い/少ない」とか、「どこから出てきたのか、x以外の文字を書く」とかが8割くらい。

残りの2割はいわゆる「白紙回答」。何もしない。「わかりません」と言える人はまだ平気な方で、こちらから「大丈夫?」って聞いても応答なしなことすらあり。

長いコードを書きたくないです

と言って「べき乗関数はないんですか?」と聞いてくる人は5%くらいかなぁ。

そういう人には、まあ、「一応、Math.Powってのがあるんだけども、演算量的に、整数べきに使うものじゃないよ。」とか教えつつ、以下のようなコードが出てきます。

var y = 64 * Math.Pow(x, 7) – 112 * Math.Pow(x, 5) + 56 * Math.Pow(x, 3) – 7 * x;

確かにすっきりはするし、「* x」の数を間違えたりはしないのだけども… 数十倍遅くなるからなぁ…

この手のコードの定石

ごくまれに、以下のようなコードを書いてくれる人あり。

var y = (((64 * x * x – 112) * x * x + 56) * x * x – 7) * x;

「一般的に、多項式を計算するときはカッコでくくって掛け算を減らす」という定石を知ってる人。元のべた書きよりも数割高速なはず。こういう定石も教えておいた方がいいなぁと思った瞬間。

まあ、自分なら一時変数作っちゃいますが。

var x2 = x * x;
var x3 = x * x2;
var x5 = x3 * x2;
var x7 = x5 * x2;
var y = 64 * x7 – 112 * x5 + 56 * x3 – 7 * x;

この式の場合は奇数次の項しかないので、「* x * x」じゃなくて「* x2」するのもポイント(このくらいなら大抵はコンパイラが最適化してくれますが)。

広告

Written by ufcpp

2012年7月8日 @ 15:48

カテゴリー: 未分類

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中

%d人のブロガーが「いいね」をつけました。