最近在看scip，不得不说，这本书的确是经典之作，每天抽出时间看一会上面所讲的东西，对我这样编程算法基础薄弱的人，也是受益匪浅。所以想把上面的一些好的算法用自己熟悉的javascript重新写一遍，加深记忆。
两个整数a和b的最大公约数（GCD）定义为能除尽这两个数的那个最大的整数。在SCIP中提到了一种基于欧几里得算法的对数增加阶的实现。该算法的思想是：如果r是a除以b的余数，那么可以有结论r和b的公约数等于a和b的公约数。基于该理论，有如下实现
function GCD(a,b){ let gcd = 0; if(b === 0){ gcd = b; } else{ let r = a%b; GCD(b,r); } return gcd; }增长阶是log(n)底数是1.6180。
素数检测是数学中一个经久不衰的话题，同样，本文也只讨论素数检测的对数级复杂度的算法。 关于这个算法，需要介绍一下这个算法的核心理论：
费马小定理推论：对于一个整数n，取另外一个整数a满足a< n，计算a^n%n是否等于n，如果结果不是a，那肯定不是素数，相反，那么n是素数的概率就很大。
费马小定理的检测实际上是属于概率算法的领域，一般情况我们选取越多的a去检测n是否符合条件，通过的越多，那么n是素数的概率也会增加，也会使得检测出错的概率减小。当然，对于概率算法，无论怎么增加a的数量，也会有一些能够骗过费马检测的数。数学上把它们称为卡尔麦克数，现在数学家们已经找到所有10 ^ 16以内的卡尔麦克数，最大的一个是9585921133193329。对于这种情况，我们可以通过建立一个表来排除这些数，使得错误概率再次减小。 下面是算法的过程：
**************算法核心*************** function fermatTest(n) {//随机生成a判断是否满足费马检测 function tryIt(a) { return (expmod(a, n, n) === a) ? true : false; } return tryIt(parseInt(Math.random() * (n - 1) + 2, 10) + 1); } function fasePrime(n, times) { //最终检测，输入数值和检测次数 if (times === 0) { return true; } if (fermatTest(n)) { fasePrime(n, (times - 1)); } else { return false; } } **************main*************** function expmod(base, exp, n) { //表示一个数的a的冥对n取模的过程 if (exp === 0) { return 1; } if (isEven(exp)) { return reminder(square(expmod(base, (n / 2), n)), n); } else { return reminder(base * (expmod(base, (exp - 1), n)), n); } } function isEven(n) { //判断是否是偶数 return n % 2 === 0 ? true : false; } function reminder(a, b) { return a % b; } function square(n) { return n * n; }算法的思想是对于给定次数，生成小于n的随机数a，通过费马小定理判断素数。通常运用多次随机选择a进行判断，该算法错误概率能减小到所需要的任何程度。
该算法又称乘法的“俄罗斯农名的方法”，它的历史悠久，使用它的实例可以在莱茵德纸草书中找到，这也是现存最悠久的两份数学文献之一。通过该算法，计算斐波那契数只需要对数的步数。 算法核心理论：对于两个状态变量a，b,定义变换规则,a<– a + b和b<– a，将这种变换称为T变换。通过观察发现，从1和0开始将T反复应用n次，可以产生一对数Fib(n+1)和Fib(n)，其中FIb表示斐波那契数列第n项。
var fibonacci = function(n) { return caculate(1,0,0,1,n); } function caculate(a,b,p,q,count){ if(count == 0){ return b; } if(count %2 == 0){ return caculate(a,b,(p*p+q*q),(2*p*q+q*q),(count/2)) } else{ return caculate((b*q+a*q+a*p),(b*p+a*q),p,q,(count -1)) } }