按类别列出问题

Questions in category: 算法 (Algorithm)

计算数学 >> 算法

1. 三角函数的计算

Posted by on 2022-07-03 17:41:15 last update 2022-07-03 17:41:15 | Answers (0) | 收藏

1956年, Volder 为计算三角函数和双曲函数(包括指数函数和对数函数)开发了一类算法.

1959年他描述了一种用于计算三角函数的坐标旋转数字计算机(COordinate Rotation DIgital Computer, CORDIC)，乘法，除法以及二进制和混合基数系统之间的转换.

References:

http://ece-research.unm.edu/pollard/classes/walther.pdf

2. 使用牛顿法计算自然数平方根的整数部分

Posted by haifeng on 2021-10-05 16:16:57 last update 2021-10-07 10:39:45 | Answers (0) | 收藏

有很多情形需要计算一个自然数的平方根, 或者其整数部分.

对于正整数 $N$, 求 $n\in\mathbb{N}$, 使得 $n^2\leqslant N < (n+1)^2$.

Exer: 如果从 1 开始一个一个去试, 则算法复杂度是多少?

for(int i=1; i*i < = N; i++)

这里采用经典的 Newton 法(也称为 Newton-Raphson 法)计算自然数的平方根的整数部分.

References:

[1] 迈克尔威尔森巴赫 (Michael Welschenbach) 著密码学 -- C/C++ 语言实现, 机械工业出版社

[2]

3. [算法]将一个数每次翻倍增长, 直至给定N

Posted by haifeng on 2021-04-18 08:07:07 last update 2021-04-18 08:07:07 | Answers (0) | 收藏

#给定 N

mc=8;
m=mc;//此时m=16
while mc<N:
mc+=m
#print(mc)
if mc*2>N: m=N-mc
else: m=mc

------------------------------

mc: 8, 16, 32, 64, 100

4. 计算 $\ln(x)$ 的算法

Posted by haifeng on 2020-05-18 10:03:59 last update 2022-07-04 13:35:34 | Answers (0) | 收藏

$\ln(x)=\log_e(x)$, 有时也写成 $\log(x)$.

判断以下哪种算法最高效.

算法一:

对于 $x\in(0,2]$, 令 $t=x-1$, 则 $t\in(-1,1]$,

\[
\begin{split}
\ln(1+t)&=\sum_{n=1}^{+\infty}\frac{(-1)^{n-1}}{n}t^n\\
&=t-\frac{1}{2}t^2+\frac{1}{3}t^3-\frac{1}{4}t^4+\frac{1}{5}t^5-\frac{1}{6}t^6+\cdots
\end{split}
\]

$\ln 2$ 还有另一个极限等式(参见问题1183)

\[
\lim_{n\rightarrow\infty}(\frac{1}{n+1}+\cdots+\frac{1}{2n})=\ln 2
\]

对于 $x > 2$, 可将 $x$ 表示为 $x=a\cdot 2^m$. 这里 $a\in(0,2)$. 于是

\[
\ln x=\ln a+m\ln 2
\]

当然这种算法并不是太好的.

例: 计算 $\ln(65)$.

由于 $65=\frac{65}{64}\cdot 2^6$, 故

\[
\ln(65)=\ln\frac{65}{64}+2\ln 2.
\]

利用 Calculator 计算

>> 65/64
in> 65/64

out> 1.015625

------------------------

>> ln(2)
in> ln(2)
out> 0.69314717

------------------------

因此,

\[
\begin{split}
\ln(65)&=\ln(1.015625)+6\cdot\ln(2)\\
&=\ln(1+.015625)+6\times 0.69314717\\
&=0.01550419+ 4.15888302\\
&=4.17438721
\end{split}
\]

>> sum((-1)^(n-1)*0.015625^n/n, n, 1,100)
in> sum((0-1)^(n-1)*0.015625^n/n,n,1,100)

out> 0.01550419

500位精度

>> ln(2)
in> ln(2)
out>

0.69314718055994530941723212145817656807550013436025525412068000949339362196969471560586332699641868754200148102057068573368552023575813055703267075163507596193072757082837143519030703862389167347112335011536449795523912047517268157493206515552473413952588295045300709532636664265410423915781495204374043038550080194417064167151864471283996817178454695702627163106454615025720740248163777338963855069526066834113727387372292895649354702576265209885969320196505855476470330679365443254763274495125040623

精确到1000位

>> setprecision(1000)
in> setprecision(1000)
Now the precision is: 1000

------------------------

>> ln(2)
in> ln(2)
out> 0.6931471805599453094172321214581765680755001343602552541206800094933936219696947156058633269964186875420014810205706857336855202357581305570326707516350759619307275708283714351903070386238916734711233501153644979552391204751726815749320651555247341395258829504530070953263666426541042391578149520437404303855008019441706416715186447128399681717845469570262716310645461502572074024816377733896385506952606683411372738737229289564935470257626520988596932019650585547647033067936544325476327449512504060694381471046899465062201677204245245296126879465461931651746813926725041038025462596568691441928716082938031727143677826548775664850856740776484514644399404614226031930967354025744460703080960850474866385231381816767514386674766478908814371419854942315199735488037516586127535291661000710535582498794147295092931138971559982056543928717000721808576102523688921324497138932037843935308877482597017155910708823683627589842589185353024363421436706118923678919237231467232172053401649256872747782344535340

References:

https://math.stackexchange.com/questions/61209/what-algorithm-is-used-by-computers-to-calculate-logarithms