問題2.34 Hornerの方法についての補足 - ＊「ふっかつのじゅもんがちがいます。」withぬこ

SICP読書会でHornerの方法を実装する問題をやったあと、これが何の役に立つのか？という話をしたのだけど、いまいちな説明だったように思うので文章で補足してみる。
前提知識は、以下3つくらいのつもり。

何かのプログラミング言語を書けること
位取り記数法(≒n進数)が分かる程度の算数の知識
Θ記法

Hornerの方法とは何か

Hornerの方法とは、一元n次多項式を計算するときの簡単な(計算量の少ない)算法である。
$f(x)=a_{n}x^n+a_{n-1}x^{n-1}+...+a_2x^2+a_1x+a_0$
という多項式の値は次のように計算してもよいはずだ。
$=((( ... (a_{n}x+a_{n-1})x+a_{n-2})x+ ... )x+a_1)x+a_0$
これがHornerの方法である。
さて、計算量が少ないと言ったが、どの程度少ないのであろうか。
まず馬鹿正直に $f(x)$ を計算してみよう。
$f(x)$ を計算するのに、n回の足し算が必要である。
次に馬鹿正直にk次の項： $a_{k}x^k$ を計算するには(k+1)回の掛け算が必要だ。
従って、n次多項式 $f(x)$ を計算するには、
$P_{n}=n+(n-1)+(n-2)+...+2+1$ 回の掛け算が必要になる。
$=\sum_{i=1}^{n} i$
であるが、Σの計算は前提知識としていないので、Σの公式に頼らず計算する。 $P_{n}$ を逆順に書いても総和は変わらないので、
$\begin{array}{cccccccc}P_{n}=&n&+&(n-1)&+ ... +&2&+&1\\P_{n}=&1&+&2&+ ... +&(n-1)&+&n\end{array}$

各項を縦に足すと、
$2P_{n}=(n+1)+(n+1)+(n+1)+...+(n+1)$
$=n(n+1)$
$P_{n}=\frac{n(n+1)}{2}$
である。
以上により $f(x)$ の計算量オーダーは $O(n^2)$ となる*1。

一方、Hornerの方法を使う場合、自明にn回の掛け算とn回の足し算が必要なので、計算量オーダーは $O(n)$ となる。もちろんこれは $O(n^2)$ よりもかなり早い。

他方、馬鹿正直にk次の項でk+1回の掛け算を行わず、逐次平方してやることによりk次の項 $a_{k}x^k$ の計算オーダーを $O(log(k))$ で評価することもできる。
この場合、掛け算のオーダーは、
$\log(n)+\log(n-1)+...+\log(2)+\log(1)$
$=\log(n!)$
これの評価はちょっと悩むが、 $\forall n|3<n\rightarrow2^n<n!<n^n$ なので、
$\log(2^n)<\log(n!)<\log(n^n)$
$n\log(2)<\log(n!)<n\log(n)$
と大雑把に上限と下限を見積もってやることはできる。従って逐次平方する場合の計算オーダーは $O(\log(n!))$ であるが、これは $O(n)$ より大きく、 $O(n\log(n))$ よりは小さい。

何の役に立つか？

たとえば、ハッシュテーブルを実装するには文字列からハッシュ値を求める必要があり、ハッシュ値を求めるハッシュ関数として使うことができる。
これについては以前、Cでハッシュテーブルを作ってみたで書いたのでそちらを参照のこと。(これはつまり、長さnの文字列をx進数の多倍長整数とみなして、その値を求めるのに、n次多項式の値を求めるHornerの方法を使えるということである)
なお、文字列の情報を切り捨てないハッシュ関数は、文字列の長さをnとすれば少なくとも $O(n)$ のオーダーになると考えられるので、Hornerの方法によるハッシュ関数は計算オーダーとしては比較的素性がよいものと言える気がする。

*1:固定長の整数や浮動小数点数演算のように加算乗算のコストが一定な場合。以下同じ