1. $n-bit$乘法的原理与实现

小学的时候就学过乘法的竖式计算，二进制乘法步骤如下：

1
2
3
4
5
6
7
8
9

              1 1 0 1    (13)
            × 1 0 1 1    (11)
------------------------
              1 1 0 1    (1101×1)
            1 1 0 1      (1101×1, shift left once)
          0 0 0 0        (1101×0, shift left twice)
      + 1 1 0 1          (1101×1, shift left thrice)
------------------------
      1 0 0 0 1 1 1 1    (143)

1. 浅谈基数(base)和$\log$

这章主要研究的对象是数字，首要的问题是，如何表示数字？众所周知，目前我们日常使用的都是十进制表示法（可能因为有十个手指头吧），计算机内部使用的都是二进制表示法。这里的“十”、“二”就是基数(base)。

假设现在用$b(b\geq 2)$-进制表示法。第一个问题，表示一个正整数$N\geq 0$需要至少多少位？我们知道，$k$位数字最大是$b^k-1$，那么可以推导出我们至少需要$\lceil \log_b (N+1) \rceil$位。

1. Fibonacci数列

Fibonacci是15世纪意大利著名的数学家，虽然大多数人不太清楚他的具体贡献，却都对Fibonacci数列耳熟能详：

$$
0,1,1,2,3,5,8,13,21,34
$$

我们设Fibonacci数列的第$n$项的值为$F_n$，则数列的每一项可以由以下递推式生成：

$$
\begin{equation}
F_n=
\begin{cases}
F_{n-1}+F_{n-2}, & n>1 \\ 1, & n=1 \\ 0, & n=0
\end{cases}
\end{equation}
$$

1. 渐进表示法

使用basic computer steps来描述算法耗时确实已经是一个很好的简化了，它排除了处理器、缓存策略等差异造成的影响。我们可以在此基础上继续简化。

假设$T(n)=3n^2+6n+2$，我们干脆直接省略掉表达式中的低阶项($6n+2$)。可以想象，当$n$非常大时，这些低阶项对总体的影响可以忽略不计了。再进一步，$n^2$前面的系数3也直接省略吧(Thanks to Moore Law)，我们直接说：该算法花费的时间为$O(n^3)$ （big oh of $n^3$）

Abstract: 算法笔记、资源、代码。