23/9/2023

Godel Prize这是一项颁给研究的计算机方面的奖项

前序

我们表示数字用十进制，计算机用二进制。

在b进制的情况下，表示N>0需要log_b(N+1)位;在1进制的情况下，表示N>0需要log_a(N+1)位;运用换底公式，发现二者只差一个常数，所以乍一看进制不影响复杂度；但是有些特殊情况下，比如1进制表示时，就变化了。

经典logN问题：

基本算数(Basics Arithmetic)

！！！这节课以数位n为输入

加法

加法的一个基本属性：任意3个单符号数相加，和最多只有2位。(与大于等于2的进制无关)

例子：

  • 需要多少时间呢？

    这两个数右边对齐，然后每一位上下相加，可能有进位；所以最多是n+1位长的计算，最后的一位需要时间c_0,其他位需要c_1时间，所以总耗时 c_0+c_1*n，运行时间上界O(n).

  • 能否做的更好

    不可以；因为加法一定要首先读进来，这已经需要n操作时间了，所以不可能再优化了；

    这里插一句为什么要以位数n来研究：书上说的太复杂了，简单点说，就是我们可能需要计算上千位的数字的加法，但是硬件方面我们只有32，64位，所以我们研究位来侧面反映出硬件的水平。

乘法

分析：n个长度为2n-1个数相加，复杂度是O(n^2)。特殊情况：在二进制情况下，二进制情况下*2需要常数项时间（不考虑数据结构）。

Multiplication by Al Khwarizmi算法

之后去掉第一个是偶数的行，把第二列加起来，就是结果.复杂度还是O(n^2)2

**Multiplication a la Franc¸is算法 **

复杂度：不断对y砍一半，砍一半一直到1，对y的位数来说递归了n次，每次会有除2，常数项时间；奇偶测试，判断最后一位数值常数项时间；乘2，常数项时间；可能有加法x+2z，要n，所以复杂度是O(n^2)。

能否改进？当然可以，加法可以看成n个倍数相加，两位加法是线性的，所以可以改进（第二章讲）。

除法

复杂度：O(n^2)，递归n次，每次里面是n所以是n^2.

Modular Arithmetic

基本性质：

也就是说可以在任何运算阶段将中间的计算结果简化为其模N操作的余数。

mod加法：O(n) mod 乘法：O(n^2)

mod指数：

循环了n次，每次都是做乘法O(n^2)，所以最后O(n^3)

最大公约数：gcd(x,y)

证明：只需要证明gcd(x,y)=gcd(x-y,y),之后不断重复这个过程即可证明。

复杂度分析：先补充一个定理 If a ≥ b ≥ 0*, then* a mod *b < a/*2image-20240923112143744 所以一共循环n次，每次取模（除法）n^2,所以最后是O(n^3)。

下面这个问题是怎么检验给出的数是两个数的最大公约数：(Extended Euclid algorithm)

小于等于，显然成立；大于等于，x可以整除gcd，y也可以，所以d也可以；所以只能相等。

就是d是x，y的公约数并且d可以被x，y整数线性表示，那么d就是最大公约数

怎么求出a和b呢？（下面给出的是x,y和a,b调换角色的程序,因为课件上和书上符号不一样

模的除法

模的逆

是这样一个说法：对于模N来说a的逆是x。也就是说ax模N是1.

怎么判断有没有逆？

Proof： ax mod N 可以表示成 ax+kN 根据 扩展Euclid算法 ，ax mod N = gcd(a,N)，所以如果gcd(a,N) > 1, 那么一定没有逆；如果gcd(a,N) = 1,那么一定有逆，所以存在整数x,y，使得ax+Ny = 1，此时x就是逆元。

除法定理

a 与 N 互素 <=> a有一个模N的乘法逆元，并且如果逆元存在，那么可以在O(n^3)时间内通过扩展Euclid算法算出来。

所以也就是说：模N运算时并不是可以除以任何数，只可以除以与N互素的数；运算时就是乘以除法的逆元来实现。