2007年12月30日星期日

(Javascript) 阶乘改进算法

最近对数学再返无穷兴趣,在一个数学方面极好的博客上读得关于阶乘计算的好文,就把其中一个较易实现的改进算法发布如下(Javascript实现):

/**
 * 求阶乘的改进算法。
 * 循环求积次数减少一半,但是求平方时增加开销,在IE6,Firefox2,Safari3下测试求170的阶乘
 * (大于170的阶乘结果为Infinity,没有实际意义)均比简单求积方法少不到10毫秒。
 * 求小于50的阶乘的效率表现有时不如直接使用简单的累乘方法。
 * @param {Number, Integer} n 求阶乘的目标整数。
 * @see <a href=" http://www.matrix67.com/blog/article.asp?id=442">计算阶乘的另一些有趣的算法</a>,
 *  <a href=" http://www.luschny.de/math/factorial/index.html">巨牛,20多种阶乘算法的代码</a>
 */
Math.factorial_II = function(n){
     if (n===0){return 1;}
     if (!n.isPositiveInteger()){throw new Error("param error.")}
     var m=(n.isOdd()?(n+1):n)/2; // middle number.
     var r = n.isOdd()?m:m*n; //result;
     for (var i=1; i<m; i++){
         //r*=(Math.pow(m,2) - Math.pow(i,2)); // Math.pow方法求平方比两个数直接相乘的效率低很多。
         r*=(m*m - i*i);
     }
     return r;
};

/**
 * 判断当前数值对象是否是整数。
 * @return {Boolean} true,如果数值是整数,否则返回false。
 */
Number.prototype.isInteger = function(){
    return /^[+-]?\d+$/.test(this);
};

/**
 * 判断数值是否是为负数。
 * @return {Boolean} true,如果数值是负数,否则返回false。
 */
Number.prototype.isNegative = function(){
    return this<0;
};

/**
 * 判断数值是否为负整数。
 * @return {Boolean} true,如果数值为负整数,否则返回false。
 */
Number.prototype.isNegativeInteger = function(){
    return this.isNegative() && this.isInteger();
};

/**
 * 判断当前数字的值是否为奇数(定义:不能被2整除的(整)数,如1,3和5)。
 * 关于零(0)是否属于偶数,目前似乎尚无定论,这里不予理会,作为偶数处理。
 * @return {Boolean} true,如果当前值是奇数,否则,返回false。
 */
Number.prototype.isOdd = function(){
    /* Javascript整除(取模)运算:
     * 被除数为正整数时,结果为0或1;
     *       为负整数时,结果为0或-1;
     *       为0时,结果为0;
     *       为小数时,结果为正或负小数。
     */
    return this.isInteger() && ((this%2)!==0);
};

 

没有评论:

发表评论