計算を簡単に!プログラムでホーナー法 ~Horner’s method~

導入

皆さん数学はお好きですか?
私はめっちゃ好きでもなく嫌いでもありません笑

高校は理系でしたが、数Ⅲは難しかったです。

今は、SEなので計算はComputerにおまかせですが、高校のときは手計算が苦手でした。

それから時が経って、色んな難しい計算を簡単な計算に変える魔法を知りました!

人間に取っては簡単!というと抽象度高めなので、具体性を上げるために、計算量を減らすと言っておきます。(O()オーダとかいう奴ね笑、今回難しいことは考えないお!)

今日、紹介するのはホーナー法です。

そもそもホーナー法ってなに?ってゆう方が多いと思うので紹介すると

ホーナー法とは??

多項式(~+~部分が沢山ある奴, A+BのA,Bが項っすね笑)の計算方法の工夫の仕方です。

具体例

// fはfunction(関数)の略、関数って意味わからないよねー
// 関数とは、A->B AいれたらB絶対でてくるみたいなイメージ。ライプニッツって奴が勝手に作った言葉だお!
// 両替機に千円いれたら100円10枚でるよねーみたいなかんじだお!
// (x)は、プログラムでいう引数と言われる奴。inputのこと
// LeTeXとか使うのめんどいからこんな感じで書いてるお!
f(x)=3*x*x*x+2*x*x+x+4

↑これだと、
* 掛け算(*の数):6回
* 足し算(+の数):3回

なんかいっぱいで出るそう!計算間違えそうよね?
とくに難易度は掛け算>足し算だよね?
実は、掛け算は足し算をいーぱいやることでも表せるお!
2*3=2+2+2 ←これわかるよねー?

だから掛け算の回数を減らしたいんよね!

よし!変形しようぜ!さっきの式!

関数(多項式)の変形

なんかxで括っていこうぜー

f(x)=(3*x*x+2*x+1)*x+4
  • 掛け算:4回
  • 足し算:3回
f(x)=((3*x+2)*x+1)*x+4
f(x)=(((3*x)+2)*x+1)*x+4
  • 掛け算:3回
  • 足し算:3回

わーお!掛け算の回数が回数が減りました!
こんな感じでxがかかってるものからどんどん括り出していくんだよ!
そうすると計算が簡単になるよ!

プログラミング言語での実装

今回はコンパイルとかめんどいから手軽なBrowserでも動くjavascriptで実装してみます!

// 係数の配列
// x^0として4も入れてみた笑笑
var coArray = [4,1,2,3];

// xの値(ここはとりま任意できめるよ!)
var x = 6;

// 結果格納用
var result = coArray[coArray.length - 1];

// 足し算の回数分回しくぅー
for (var i = coArray.length-1; i > 0; i--) {
    result = x * result + coArray[i - 1];
    console.log("result:\t" + result);
}

どないでした??そんなに難しくなかったでしょ??
私はこれで計算を楽にしたいのでありますお!

あと、上のプログラム動作確認してないからちゃんと動くかわからんよ笑笑笑

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です