第14日目 - binary exponentiation - シンタックスハイライト

ドンピシャなタイトルなので買ってしまった．

Rustでわかるメモリ管理しくみを知る／アプリを作る／ライブラリを読む

Software Design 2021年9月号｜技術評論社

Rustのメモリ安全性から実際どんな恩恵が受けられるのか，という視点をほとんど欠いているので，HTTPサーバ作りによるデモはいずれなぞってみたい．

しばらく前に買ったこれも技術評論社なのか．

Rustで実装！作って学ぶRDBMSのしくみ

WEB+DB PRESS Vol.122｜技術評論社

一通りドキュメント読んだらやってみる．

Binary Exponentiation

        let s1 = sin[i / 2].unwrap();
        let c1 = cos[i / 2].unwrap();
        let s2 = sin[(i + 1) / 2].unwrap();
        let c2 = cos[(i + 1) / 2].unwrap();
        sin[i] = Some(s1 * c2 + c1 * s2);
        cos[i] = Some(c1 * c2 - s1 * s2);

この部分がいわゆるbinary exponentiation（高速べき乗）とは違うことに気付いた．本来はこうだろう：

\[\begin{align} \sin(m) &= \left\{ \begin{array}{cc} 2\sin(m/2)\cos(m/2) & m\mbox{ is even},\\ \sin 1\cos(m-1)+\cos 1\sin(m-1) & m\mbox{ is odd} \end{array} \right.\\ \cos(m) &= \left\{ \begin{array}{cc} \cos^2(m/2)-\sin^2(m/2) & m\mbox{ is even},\\ \cos 1\cos(m-1)-\sin 1\sin(m-1) & m\mbox{ is odd} \end{array} \right. \end{align}\]

で，これを実装すると \(i=3645\) でパニクってしまった．

誤差の拡大の比較