fibonacci.php

来自「视频监控网络部分的协议ddns,的模块的实现代码,请大家大胆指正.」· PHP 代码 · 共 490 行 · 第 1/2 页

                $c = Math_IntegerOp::add($a, $b);
                $table[$pos->toString()] = $c->toString();
                $a = $b;
                $b = $c;
                $pos = Math_IntegerOp::add($pos, $one);
            }
            return $c;
        }
        
    }/*}}}*/

    /**
     * Returns a series of Fibonacci numbers using the given limits.
     * Method accepts two parameters, of which the second one is
     * optional. If two parameters are passed, the first one will be 
     * lower bound and the second one the upper bound. If only one
     * parameter is passed, it will be the upper bound, and the lower
     * bound will be 0 (zero).
     *
     * @param integer $idx1 the lower index for the series (if two parameters) were passed, or the upper index if only one was given.
     * @param optional integer $idx2 the upper index for the series
     * @return mixed on success, an array of integers where the keys correspond to the indexes of the corresponding Fibonacci numbers, or PEAR_Error othewise
     * @access public
     */
    function series($idx1, $idx2=null) {/*{{{*/
        if (is_integer($idx1) && $idx1 > 0) {
            if ($idx2 == null) {
                $lower_bound = 0;
                $upper_bound = $idx1;
            } elseif (is_integer($idx2)) {
                if ($idx2 < 0) {
                    return PEAR::raiseError("Upper limit $idx2 cannot be negative");
                } elseif ($idx2 < $idx1) {
                    return PEAR::raiseError("Upper limit cannot be smaller than lower limit");
                } else {
                    $lower_bound = $idx1;
                    $upper_bound = $idx2;
                }
            }
            $fibSeries = array();
            for ($i=$lower_bound; $i <= $upper_bound; $i++) {
                $fibSeries[$i] =& Math_Fibonacci::term($i);
            }
            return $fibSeries;
        } else {
            return PEAR::raiseError("The parameter $idx1 is not a valid integer");
        }
    }/*}}}*/

    /**
     * Determines if a particular integer is part of the Fibonacci series
     *
     * @param integer $num
     * @return mixed TRUE if it is a Fibonacci number, FALSE if not, PEAR_Error if the parameter was not an integer
     * @access public
     * @see Math_Fibonacci::term
     */ 
    function isFibonacci($num) {/*{{{*/
        if (!Math_IntegerOp::isMath_Integer($num)) {
            return PEAR::raiseError('Not a valid Math_Integer object'); 
        }
        $n = Math_Fibonacci::_estimateN($num);
        $intcalc =& Math_Fibonacci::term($n); 
        $cmp = Math_IntegerOp::compare($num, $intcalc);
        return ($cmp == 0);
    }/*}}}*/

    /**
     * Decomposes an integer into a sum of Fibonacci numbers
     * 
     * @param integer $num
     * @return mixed an array of Fibonacci numbers on success, PEAR_Error otherwise 
     * @access public
     */
    function decompose($num) {/*{{{*/
        if (!Math_IntegerOp::isMath_Integer($num)) {
            return PEAR::raiseError('Not a valid Math_Integer object'); 
        }
        $err = Math_Fibonacci::_recDecompose($num, &$sum);  
        if (PEAR::isError($err)) {
            return $err;
        }
        $check = new Math_Integer(0);
        foreach($sum as $fib) {
            if (PEAR::isError($fib)) {
                return $fib;
            } else {
                $check = Math_IntegerOp::add($check, $fib);
            }
        }
        $int =& new Math_Integer($num);
        if (Math_IntegerOp::compare($num,$check) == 0) {
            return $sum;
        } else {
            $numstr = $num->toString();
            $sumsrt = $check->toString;
            return PEAR::raiseError("Number and sum do not match: $numstr != $sumstr");
        }
    }/*}}}*/

    /**
     * Finds the Fibonacci number closest to an given integer
     *
     * @param integer $num
     * @return mixed a Fibonacci number (integer) on success, PEAR_Error otherwise
     * @access public
     */
    function closestTo($num) {/*{{{*/
        if (!Math_IntegerOp::isMath_Integer($num)) {
            return PEAR::raiseError("Invalid parameter: not a Math_Integer object");
        }
        $n = Math_Fibonacci::_estimateN($num);
        $fib1 =& Math_Fibonacci::term($n);
        $cmp = Math_IntegerOp::compare($fib1,$num);
        if ($cmp == 0) {
            return $fib1;
        } elseif ($cmp == 1) { // overshoot, see n - 1
            $new_n = Math_IntegerOp::sub($n, new Math_Integer(1));
        } else { // undeshoot, try n + 1
            $new_n = Math_IntegerOp::add($n, new Math_Integer(1));
        }
        $fib2 = Math_Fibonacci::term($new_n);
        $d1 = Math_IntegerOp::abs(Math_IntegerOp::sub($fib1, $num));
        $d2 = Math_IntegerOp::abs(Math_IntegerOp::sub($fib2, $num));
        $cmp = Math_IntegerOp::compare($d1, $d2);
        if ($cmp == -1 || $cmp == 0) {
            return $fib1;
        } else {
            return $fib2;
        }
    }/*}}}*/
    
    /**
     * Gets the index in the Fibonacci series of a given number.
     * If the integer given is not a Fibonacci number a PEAR_Error object
     * will be returned.
     * 
     * @param integer $num the Fibonacci number
     * @return mixed the index of the number in the series on success, PEAR_Error otherwise.
     * @access public
     */
    function getIndexOf($num) {/*{{{*/
        if (!Math_IntegerOp::isMath_Integer($num)) {
            return PEAR::raiseError("Invalid parameter: not a Math_Integer object");
        }
        // check in the lookup table
        
        $n = Math_Fibonacci::_estimateN($num);
        $fibn = Math_Fibonacci::term($n);
        $cmp = Math_IntegerOp::compare($num, $fibn);
        if ($cmp == 0) {
            return $n;
        } else {
            return PEAR::raiseError("Integer $num is not a Fibonacci number");
        }
    }/*}}}*/

    /**
     * Recursive utility method used by Math_Fibonacci::decompose()
     * 
     * @param integer $num
     * @param array $sum array of Fibonacci numbers
     * @return mixed null on success, PEAR_Error otherwise
     * @access private
     */
    function _recDecompose($num, &$sum) {/*{{{*/
        if (!Math_IntegerOp::isMath_Integer($num)) {
            return PEAR::raiseError('Not a valid Math_Integer object'); 
        }
        if (!is_array($sum)) {
            $sum = array();
        }
        $n = Math_Fibonacci::_estimateN($num);
        if (PEAR::isError($n)) {
            return $n;
        }
        $fibn = Math_Fibonacci::term($n);
        if (PEAR::isError($fibn)) {
            return $fibn;
        }
        $cmp = Math_IntegerOp::compare($fibn, $num);
        if ($cmp == 0) {
            $sum[] = $fibn;
            return null;
        } elseif ($cmp == -1) {
            $sum[] = $fibn;
            $newnum = Math_IntegerOp::sub($num, $fibn);
            Math_Fibonacci::_recDecompose($newnum, &$sum);
        } elseif ($cmp == 1) {
            $n_1 = Math_IntegerOp::sub($n, new Math_Integer(1));
            if (PEAR::isError($n_1)) {
                return $n_1;
            }
            $fibn_1 = Math_Fibonacci::term($n_1);
            if (PEAR::isError($fibn_1)) {
                return $fibn_1;
            }
            $sum[] = $fibn_1;
            $newnum = Math_IntegerOp::sub($num, $fibn_1);
            Math_Fibonacci::_recDecompose($newnum, &$sum);
        }
    }/*}}}*/

    /**
     * Estimates the approximate index for a given number
     * It uses the approximate formula:
     * F(n) ~ (PHI^n)/sqrt(5), where '~' means the 'closest integer to'
     * This equation is based on the relation: phi = -1/PHI
     * Which turns Lucas' formula into:
     * F(n) = (PHI^2n + 1)/(PHI^n * sqrt(5))
     * From which we get the formula above, after making the approximation:
     * (PHI^2n + 1) -> (PHI^2n)
     *
     * @param integer $num
     * @return integer the approximate index
     * @access private
     */
    function &_estimateN(&$num) {/*{{{*/
        if (Math_IntegerOp::isMath_Integer($num)) {
            $f = $num->toString();
        } else {
            $f = $num;
        }
        return Math_Fibonacci::_closestInt((log($f) + MATH_LNSQRT5) / MATH_LNPHI);
    }/*}}}*/
    
    /**
     * Finds the closest integer to a given number
     *
     * @param numeric $num
     * @return integer
     * @access private
     */
    function &_closestInt($num) {/*{{{*/
        $f = floor($num);
        $c = ceil($num);
        return new Math_Integer(($num - $f) < ($c - $num) ? $f : $c);
    }/*}}}*/

}/* End of Math_Fibonacci }}}*/

// vim: ts=4:sw=4:et:
// vim6: fdl=1:
?>