展开全部
第一种方法是求倒数,根据牛顿迭代法,设序列{Xn},递推公式为X(n+1)=2X(n)-aX(n)²,a为常数且为正,则当X0∈(0,1]时有lim<n→∞>(Xn)=1/a,且精度随着迭代次数指数增长。故方法一为根据递推公式求除数的倒数(因为被除数大于1,倒数一定小于1,可以用定点数表示),然后乘以被除数即得到原来的商。迭代次数为logN,每次迭代中需要进行一次移位和两次大整数乘法,定点数乘法还要额外加一次移位,总时间复杂度为O(logN * (N + NlogN + NlogN)) = O(Nlog²N);
第二种方法是第一种方法的改进版,设被除数为a,除数为b,则写成分式为a/b,分式具有分子分母同时乘以非零数值不变的性质,首先将分子分母乘以一常数X,使得bX∈(0,1],然后将分子分母同时乘以(2-分母),不断进行迭代直至分母足够接近1,此时分子即是所求的商。与方法一相比,方法二不需要估算X0,每次迭代仍然需要两次乘法两次移位,因此时间复杂度仍然是 O(Nlog²N)。部分AMD处理器的浮点除法采用此方法进行;
第三种方法即是常用的试商法。分为按位试商和按双字试商两种。按位试商只要逐一移位比较即可,时间复杂度O(N²)。按双字试商则由于试商存在误差,必须在试商之后用试商乘以除数与被除数作比较,由于是双字乘以大整数时间为线性,总体时间复杂度为O(N+(N-1)+(N-2)+(N-3)+...+1)=O(N(N+1)/2)=O(N²)。总之试商法的时间复杂度是O(N²)。
那么问题来了,方法一和方法二的共同特点是,每次迭代都必须进行两次至少N位的乘法,因此浪费了大量时间。实测即使是数万位数的除法(尤其是被除数远远长于除数的情况下,为了降低定点数误差就必须将被除数和除数左移位相当长的距离)方法二的时间依然是方法三的时间的数十倍甚至上百倍。而且方法三可以同时获得商和余数,方法一和方法二都做不到。
第二种方法是第一种方法的改进版,设被除数为a,除数为b,则写成分式为a/b,分式具有分子分母同时乘以非零数值不变的性质,首先将分子分母乘以一常数X,使得bX∈(0,1],然后将分子分母同时乘以(2-分母),不断进行迭代直至分母足够接近1,此时分子即是所求的商。与方法一相比,方法二不需要估算X0,每次迭代仍然需要两次乘法两次移位,因此时间复杂度仍然是 O(Nlog²N)。部分AMD处理器的浮点除法采用此方法进行;
第三种方法即是常用的试商法。分为按位试商和按双字试商两种。按位试商只要逐一移位比较即可,时间复杂度O(N²)。按双字试商则由于试商存在误差,必须在试商之后用试商乘以除数与被除数作比较,由于是双字乘以大整数时间为线性,总体时间复杂度为O(N+(N-1)+(N-2)+(N-3)+...+1)=O(N(N+1)/2)=O(N²)。总之试商法的时间复杂度是O(N²)。
那么问题来了,方法一和方法二的共同特点是,每次迭代都必须进行两次至少N位的乘法,因此浪费了大量时间。实测即使是数万位数的除法(尤其是被除数远远长于除数的情况下,为了降低定点数误差就必须将被除数和除数左移位相当长的距离)方法二的时间依然是方法三的时间的数十倍甚至上百倍。而且方法三可以同时获得商和余数,方法一和方法二都做不到。
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询