第二次作业

计算机数学

把Division Algorithm的证明补充完整。

证：

令$S=\{a-bk:k∈Z\ and\ a-bk≥0\}$
S非空，得有r∈S，且$r=a-qb$
设存在r1,q1使得$r1=a-q1b$

先证q的唯一性：

因为$r1=a-q1b$
由存在性得$0<r1<b$
所以有$a/b=q1+r1$
即$\lfloor a/b \rfloor$=q1
故有$q1=q$

后证r的唯一性：

$r1=a-qb=r$

说明Simple Division算法的正确性及该算法对n比特输入需要使用的时间是O(n^2)。

def divide(a,b):
    if a==0:
        return 0,0
    q,r=divide(a//2,b)
    q,r=2*q,2*r
    if a&1:    #a是奇数
        r=r+1
    if r>=b:
        r,q=r-b,q+1
    return q,r

证：

(1)

q为商，r为余数。递归算法，最底层$q=0,r=0$,之后向上返回。
若除数为奇数，则在递归计算a/2时是向下取整，故向上返回应是$(a+1)/2$
若$r>=b$；
由$a=qb+r$得$a=qb+r+b-b=(q+1)b+r-b$
所以得$r=r-b,q=q+1$

(2)