Questions in category: 算法 (Algorithm)
计算数学 >> 算法

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

Posted by haifeng on 2020-05-18 10:03:59 last update 2020-05-18 10:26:48 | 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
\]

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

 

 


References:

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

 

2. 正整数乘法的 Karatsuba 算法

Posted by haifeng on 2019-04-28 08:41:57 last update 2019-04-28 09:15:17 | Answers (0) | 收藏


我们以十位数乘以十位数为例. 这里 $ab$ 是十位数, 即 $10a+b$, $a,b\in\{0,1,2,\ldots,9\}$.

\[
ab\times cd=(10a+b)(10c+d)=100ac+10(ad+bc)+bd.
\]

这是通常的算法, 需要 4 次乘法.

 

 

注意到

\[
(a+b)(c+d)=(ac+bd)+(ad+bc),
\]

因此,

\[
ad+bc=(a+b)(c+d)-(ac+bd)
\]

于是

\[
ab\times cd=100ac+10(ad+bc)+bd=100ac+10[(a+b)(c+d)-(ac+bd)]+bd.
\]

这里, 我们只需 $ac$, $bd$, $(a+b)(c+d)$ 三次乘法.

 

对于大的整数, 采用分治策略, 归结为小整数的乘法和加法运算.

3. 单处理器作业调度问题

Posted by haifeng on 2018-06-07 09:18:13 last update 2018-06-07 09:21:21 | Answers (0) | 收藏


现在有 $N$ 个作业 $j_1,j_2,\ldots,j_N$, 已知对应的运行时间分别为 $t_1,t_2,\ldots,t_N$. 而处理器只有一个.

目标是使作业平均完成的时间最小化.

要求: 这里我们非抢占调度(nonpreemptive scheduling), 即 一旦开始一个作业, 就必须把该作业运行完.

 

 


References:

Mark Allen Weiss, Data Structures and Algorithm Analysis in C++, (Third Edition).

张怀勇 等译, 《数据结构与算法分析 C++ 描述》(第三版) [Chapter 10. Page. 297]

 

https://study.com/academy/lesson/preemptive-vs-non-preemptive-process-scheduling.html