首页 文章

PHP中任意大整数的算法

提问于
浏览
8

好的,因此PHP不是处理任意大整数的最佳语言,因为它本身只支持32位有符号整数 . 我想要做的是创建一个可以表示任意大二进制数的类,并能够对其中两个执行简单的算术运算(加/减/乘/除) .

我的目标是处理128位整数 .

我正在研究几种方法,以及我看到的问题 . 任何关于你会选择什么以及如何进行评论的输入或评论将不胜感激 .

Approach #1: 创建一个128位整数类,在内部将整数存储为四个32位整数 . 这种方法的唯一问题是,我不确定在操作两个操作数的各个块时如何处理溢出/下溢问题 .

Approach #2: 使用bcmath扩展名,因为它看起来像它旨在解决的问题 . 我唯一担心采用这种方法是bcmath扩展的比例设置,因为可以't be any rounding errors in my 128-bit integers; they must be precise. I' m也担心能够最终将bcmath函数的结果转换为二进制字符串(我稍后需要将其转换为某些字符串) mcrypt加密函数) .

Approach #3: 将数字存储为二进制字符串(可能是LSB优先) . 从理论上讲,我应该能够以这种方式存储任意大小的整数 . 我所要做的就是编写四个基本的算术函数来对两个二进制字符串执行add / sub / mult / div并生成二进制字符串结果 . 这正是我需要交给mcrypt的格式,所以's an added plus. This is the approach I think has the most promise at the moment, but the one sticking point I'得到的是PHP不必将它分解为字节大小的块(没有双关语),此时我对处理溢出的问题方法#1的/下溢适用 .

4 回答

  • 3

    PHP GMP extension会更好 . 作为额外的好处,您可以使用它来进行十进制到二进制转换,如下所示:

    gmp_strval(gmp_init($n, 10), 2);
    
  • 4

    已经有各种各样的classes available,因此您可能希望在编写自己的解决方案之前先查看它们(如果仍然需要编写自己的解决方案) .

  • 1

    据我所知,bcmath扩展名是你想要的扩展名 . PHP手册中的数据有点稀疏,但您可以通过使用bcscale()函数或大多数其他bcmath函数中的可选第三个参数来将精度设置为您所需的精度 . 不太确定二进制字符串的东西,但是一些谷歌搜索告诉我你应该能够通过使用pack()函数来做到这一点 .

  • 0

    我实现了以下PEMDAS complaint BC evaluator,这可能对您有用 .

    function BC($string, $precision = 32)
    {
        if (extension_loaded('bcmath') === true)
        {
            if (is_array($string) === true)
            {
                if ((count($string = array_slice($string, 1)) == 3) && (bcscale($precision) === true))
                {
                    $callback = array('^' => 'pow', '*' => 'mul', '/' => 'div', '%' => 'mod', '+' => 'add', '-' => 'sub');
    
                    if (array_key_exists($operator = current(array_splice($string, 1, 1)), $callback) === true)
                    {
                        $x = 1;
                        $result = @call_user_func_array('bc' . $callback[$operator], $string);
    
                        if ((strcmp('^', $operator) === 0) && (($i = fmod(array_pop($string), 1)) > 0))
                        {
                            $y = BC(sprintf('((%1$s * %2$s ^ (1 - %3$s)) / %3$s) - (%2$s / %3$s) + %2$s', $string = array_shift($string), $x, $i = pow($i, -1)));
    
                            do
                            {
                                $x = $y;
                                $y = BC(sprintf('((%1$s * %2$s ^ (1 - %3$s)) / %3$s) - (%2$s / %3$s) + %2$s', $string, $x, $i));
                            }
    
                            while (BC(sprintf('%s > %s', $x, $y)));
                        }
    
                        if (strpos($result = bcmul($x, $result), '.') !== false)
                        {
                            $result = rtrim(rtrim($result, '0'), '.');
    
                            if (preg_match(sprintf('~[.][9]{%u}$~', $precision), $result) > 0)
                            {
                                $result = bcadd($result, (strncmp('-', $result, 1) === 0) ? -1 : 1, 0);
                            }
    
                            else if (preg_match(sprintf('~[.][0]{%u}[1]$~', $precision - 1), $result) > 0)
                            {
                                $result = bcmul($result, 1, 0);
                            }
                        }
    
                        return $result;
                    }
    
                    return intval(version_compare(call_user_func_array('bccomp', $string), 0, $operator));
                }
    
                $string = array_shift($string);
            }
    
            $string = str_replace(' ', '', str_ireplace('e', ' * 10 ^ ', $string));
    
            while (preg_match('~[(]([^()]++)[)]~', $string) > 0)
            {
                $string = preg_replace_callback('~[(]([^()]++)[)]~', __FUNCTION__, $string);
            }
    
            foreach (array('\^', '[\*/%]', '[\+-]', '[<>]=?|={1,2}') as $operator)
            {
                while (preg_match(sprintf('~(?<![0-9])(%1$s)(%2$s)(%1$s)~', '[+-]?(?:[0-9]++(?:[.][0-9]*+)?|[.][0-9]++)', $operator), $string) > 0)
                {
                    $string = preg_replace_callback(sprintf('~(?<![0-9])(%1$s)(%2$s)(%1$s)~', '[+-]?(?:[0-9]++(?:[.][0-9]*+)?|[.][0-9]++)', $operator), __FUNCTION__, $string, 1);
                }
            }
        }
    
        return (preg_match('~^[+-]?[0-9]++(?:[.][0-9]++)?$~', $string) > 0) ? $string : false;
    }
    

    它会自动处理舍入错误,只需将精度设置为您需要的任何数字 .

相关问题