计算机程序设计艺术
《计算机程序设计艺术》（），簡稱TAOCP，是美國電腦科學家高德纳（）编著的关于计算机程序设计之七卷本著作。作者並因此获得美国计算机协会1974年图灵奖。 概述 1962年，高德纳還是個研究生的時候就開始了程式設計的工作，在攻讀博士期間，艾迪生韋斯利公司（Addison-Wesley）的顧問Richard Varga找他出書，因課業繁忙，一時沒時間草稿。1963年高德納獲得加州理工學院數學博士學位，開始投入撰寫工作。1968年，當時31…
标签：#计算机算术算法
共 5 篇文章
平方求幂
在数学和程序设计中，平方求冪（）或快速冪是快速计算一个数（或更一般地说，一个半群的元素，如多項式或方阵）的大正整数乘幂的一般方法。这些算法可以非常通用，例如用在模算數或矩阵幂。对于通常使用加性表示法的半群，如密码学中使用的椭圆曲线，这种方法也称为double-and-add。 基本方法 该方法是基于观察到，对于正整数n，可知 : x^n = \begin{cases} x \, ( x^{2})^{\frac{n - 1}{2}}, &…
頌哈吉-施特拉森演算法
，選擇85為1的8次方根。為了說明方便，其中數字使用十進制表示，不用二進制表示。頌哈吉-施特拉森以此方式為基礎，再加上negacyclic convolutions]] 下西洋棋，1979年]] 頌哈吉-施特拉森演算法（）是漸近快速的大整数乘法算法。是由和沃爾克·施特拉森在1971年發明。若針對二個n位元的整數，其運行的，若以大O符号表示，是O(n \cdot \log n \cdot \log \log n)。演算法使用在有2n+1個…
卡拉楚巴算法
Karatsuba算法/乘法、卡拉楚巴乘法/算法（），是一种快速乘法算法，由1960年提出并于1962年发表。它将两个n位数字相乘所需的一位数乘法次数减少到了至多3 n^{\log_23}\approx 3 n^{1.585}（如果n是2的乘方，则正好为n^{\log_23}）。因此它比要n^2次个位数乘法的经典算法要快。例如，对于两个1024位的数相乘（n = 1024 = 2^{10}），卡拉楚巴算法需要3^{10} = 59049…
布斯乘法算法
布斯乘法算法（）是计算机中一种利用数的2的补码形式来计算乘法的算法。该算法由安德鲁·唐纳德·布思于1950年发明，当时他在伦敦大学柏贝克学院做晶体学研究。布斯曾使用过一种台式计算器，由于用这种计算器来做移位计算比加法快，他发明了该算法来加快计算速度。布斯算法在计算机体系结构学科中备受关注。 算法描述 对于N位乘数Y，布斯算法检查其2的补码形式的最后一位和一个隐含的低位，命名为y-1，初始值为0。对于yi, i = 0, 1, ..., …