跳到主要内容

東京大学 情報理工学系研究科 コンピュータ科学専攻 2016年8月実施 専門科目II 問題1

标签：

Author​

祭音Myyura (co-authored with GPT 5.6 SOL)

Description​

回答下列问题。

（1）用 cos⁡α,sin⁡α,cos⁡β,sin⁡β\cos\alpha,\sin\alpha,\cos\beta,\sin\beta 表示 cos⁡(α+β)\cos(\alpha+\beta) 和 sin⁡(α+β)\sin(\alpha+\beta)。

（2）设 0≤α<π/20\le\alpha<\pi/2，用 cos⁡α,sin⁡α\cos\alpha,\sin\alpha 表示 cos⁡(α/2)\cos(\alpha/2) 和 sin⁡(α/2)\sin(\alpha/2)。

（3）有限精度下，直接使用第（2）问公式在 α\alpha 接近 00 时是否会丢失有效数字？若会，改写公式以避免该问题。

（4）设

α=π2∑i=1Nbi2−i,bi∈{0,1},\alpha=\frac\pi2\sum_{i=1}^{N}b_i2^{-i},\qquad b_i\in\{0,1\},

并定义 αn=π2∑i=1nbi2−i\alpha_n=\frac\pi2\sum_{i=1}^{n}b_i2^{-i}。

  1. 用 cos⁡αn,sin⁡αn\cos\alpha_n,\sin\alpha_n 表示 cos⁡αn+1,sin⁡αn+1\cos\alpha_{n+1},\sin\alpha_{n+1}；
  2. 设计只使用四则运算和开平方计算 cos⁡α,sin⁡α\cos\alpha,\sin\alpha 的算法。

（5）定义 cosh⁡a=(ea+e−a)/2\cosh a=(e^a+e^{-a})/2、sinh⁡a=(ea−e−a)/2\sinh a=(e^a-e^{-a})/2。设 0≤x<10\le x<1 有有限位二进制表示，设计只使用四则运算和开平方计算 cosh⁡(xlog⁡e2)\cosh(x\log_e2)、sinh⁡(xlog⁡e2)\sinh(x\log_e2) 的算法。

Kai​

(1)​

cos⁡(α+β)=cos⁡αcos⁡β−sin⁡αsin⁡β,\cos(\alpha+\beta)=\cos\alpha\cos\beta-\sin\alpha\sin\beta,
sin⁡(α+β)=sin⁡αcos⁡β+cos⁡αsin⁡β.\sin(\alpha+\beta)=\sin\alpha\cos\beta+\cos\alpha\sin\beta.

(2)​

因 0≤α/2<π/40\le\alpha/2<\pi/4，两根均取正号：

cos⁡α2=1+cos⁡α2,sin⁡α2=1−cos⁡α2.\cos\frac\alpha2=\sqrt{\frac{1+\cos\alpha}{2}},\qquad \sin\frac\alpha2=\sqrt{\frac{1-\cos\alpha}{2}}.

(3)​

α≈0\alpha\approx0 时 cos⁡α≈1\cos\alpha\approx1，计算 1−cos⁡α1-\cos\alpha 会发生相近数相减，导致 sin⁡(α/2)\sin(\alpha/2) 丢失有效数字。利用

1−cos⁡α=sin⁡2α1+cos⁡α1-\cos\alpha=\frac{\sin^2\alpha}{1+\cos\alpha}

改写为

sin⁡α2=sin⁡α2(1+cos⁡α).\sin\frac\alpha2=\frac{\sin\alpha}{\sqrt{2(1+\cos\alpha)}}.

cos⁡(α/2)\cos(\alpha/2) 的原公式没有该消减问题。

(4)​

令

θn+1=π2n+2,αn+1=αn+bn+1θn+1.\theta_{n+1}=\frac{\pi}{2^{n+2}},\qquad \alpha_{n+1}=\alpha_n+b_{n+1}\theta_{n+1}.

记 Cn=cos⁡αn,Sn=sin⁡αn,c=cos⁡θn+1,s=sin⁡θn+1C_n=\cos\alpha_n,S_n=\sin\alpha_n,c=\cos\theta_{n+1},s=\sin\theta_{n+1}，则

(Cn+1,Sn+1)={(Cn,Sn),bn+1=0,(Cnc−Sns, Snc+Cns),bn+1=1.(C_{n+1},S_{n+1})= \begin{cases} (C_n,S_n),&b_{n+1}=0,\\ (C_nc-S_ns,\ S_nc+C_ns),&b_{n+1}=1. \end{cases}

算法从 (C0,S0)=(1,0)(C_0,S_0)=(1,0) 开始。先置

c1=s1=12c_1=s_1=\frac1{\sqrt2}

（对应 θ1=π/4\theta_1=\pi/4），并递推

ci+1=1+ci2,si+1=si2(1+ci).c_{i+1}=\sqrt{\frac{1+c_i}{2}},\qquad s_{i+1}=\frac{s_i}{\sqrt{2(1+c_i)}}.

按 i=1,…,Ni=1,\ldots,N 依次用上面的加法公式：若 bi=1b_i=1，就把 (C,S)(C,S) 更新为 (Cci−Ssi,Sci+Csi)(Cc_i-Ss_i,Sc_i+Cs_i)；若 bi=0b_i=0 则不变。最终 (C,S)=(cos⁡α,sin⁡α)(C,S)=(\cos\alpha,\sin\alpha)。全过程只含四则运算与开平方。

(5)​

写成 x=∑i=1Nbi2−ix=\sum_{i=1}^{N}b_i2^{-i}。从 r0=2r_0=2 开始反复开平方，得到

ri=ri−1=22−i.r_i=\sqrt{r_{i-1}}=2^{2^{-i}}.

令 q=1q=1，对每个 bi=1b_i=1 乘上 rir_i，则

q=∏i=1Nribi=2x=exlog⁡e2.q=\prod_{i=1}^{N}r_i^{b_i}=2^x=e^{x\log_e2}.

因此

cosh⁡(xlog⁡e2)=q+q−12,sinh⁡(xlog⁡e2)=q−q−12.\cosh(x\log_e2)=\frac{q+q^{-1}}2,\qquad \sinh(x\log_e2)=\frac{q-q^{-1}}2.
本页目录