JavaScript大数除法bdiv函数转PHP实现错误与结果差异问题求解

问题背景 #

现有一个接收数组格式大整数作为输入的JavaScript除法函数，输入示例如下：

示例1：
x=[ 239709880, 250229420, 109667654, 196414465, 13098 ]
y=[ 78135241, 54642792, 249 ]

示例2：
x=[ 0, 0, 0, 0, 0, 0, 1 ]
y=[ 78135241, 54642792, 249 ]

示例3：
x=[ 49 ]
y=[ 33 ]

原始代码实现 #

JavaScript版bdiv函数 #

function bdiv(x,y) {
    var n=x.length-1, t=y.length-1, nmt=n-t, arr = []
    if(n < t || n==t && (x[n]<y[n] || n>0 && x[n]==y[n] && x[n-1]<y[n-1])) {
        arr['q']=[0]
        arr['mod']=x
        return arr
    }
    if(n==t && toppart(x,t,2)/toppart(y,t,2) <4) {
        var q=0, xx
        for(;;) {
            xx=bsub(x,y)
            if(xx.length==0) break
            x=xx; q++
        }
        arr['q']=[q]
        arr['mod']=x
        return arr
    }
    var shift, shift2
    shift2=Math.floor(Math.log(y[t])/log2)+1
    shift=bs-shift2

    if(shift) {
        x=x.concat()
        y=y.concat()
        for(i=t; i>0; i--) y[i]=((y[i]<<shift) & bm) | (y[i-1] >> shift2); y[0]=(y[0]<<shift) & bm
        if(x[n] & ((bm <<shift2) & bm)) { x[++n]=0; nmt++; }
        for(i=n; i>0; i--) x[i]=((x[i]<<shift) & bm) | (x[i-1] >> shift2); x[0]=(x[0]<<shift) & bm
    }
    var i, j, x2, y2,q=zeros(nmt+1)

    y2=zeros(nmt).concat(y)

    for(;;) {
        x2=bsub(x,y2)
        if(x2.length==0) break
        q[nmt]++
        x=x2
    }
    var yt=y[t], top=toppart(y,t,2)
    for(i=n; i>t; i--) {
        m=i-t-1
        if(i >= x.length)
            q[m]=1
        else if(x[i] == yt)
            q[m]=bm
        else
            q[m]=Math.floor(toppart(x,i,2)/yt)
        topx=toppart(x,i,3)
        while(q[m] * top > topx)
            q[m]--
        y2=y2.slice(1)
        x2=bsub(x,bmul([q[m]],y2))
        if(x2.length==0) {
            q[m]--
            x2=bsub(x,bmul([q[m]],y2))
        }
        x=x2
    }
    if(shift){
        for(i=0; i<x.length-1; i++)
            x[i]=(x[i]>>shift) | ((x[i+1] << shift2) & bm);
        x[x.length-1]>>=shift
    }
    while(q.length > 1 && q[q.length-1]==0)
        q=q.slice(0,q.length-1)
    while(x.length > 1 && x[x.length-1]==0)
        x=x.slice(0,x.length-1)
    arr['q']=q
    arr['mod']=x
    return arr;
}

JavaScript版toppart辅助函数 #

function toppart(x,start,len) {
    var n=0
    while(start >= 0 && len > 0){
        n=n*bx2+x[start--]
        len--
    }
    return n
}

初步PHP转换版存在的问题 #

问题1：数组拷贝逻辑错误 #

JS中x = x.concat()用于创建数组浅拷贝，避免修改原始传入的数组，现有PHP尝试的写法均不符合要求：

• array_push($x,$x)会生成嵌套数组
• $x=array_merge(...$x)会报参数类型错误
• $x=array_merge(array(),$x)触发无限循环

问题2：toppart函数计算结果差1 #

相同输入下，JS返回70144566321522750，PHP返回70144566321522751，误差随运行逐步扩大。
测试参数：$x=[ 210763776, 109357119, 261308872];$start=2;$len=2;$bx2=268435456;

现有PHP版toppart代码：

function toppart($x,$start,$len){
    global $bs, $bm, $bx2, $bx, $bd, $bdm, $log2;
    $n=0;
    while($start >= 0 && $len > 0){
        $n= bcadd(bcmul($n, $bx2),$x[$start--]);
        $len--;
    }
    return $n;
}

修复方案 #

1. 数组拷贝逻辑修复 #

JS的concat()做数组浅拷贝，PHP等价实现用array_slice即可，性能更稳定且无嵌套问题。在$shift判断块开头添加两行拷贝逻辑：

if($shift){
    // 新增两行数组拷贝，等价JS的x.concat()/y.concat()
    $x = array_slice($x, 0);
    $y = array_slice($y, 0);
    // 原有shift位运算逻辑不变
    for($i=$t; $i>0; $i--)
        $y[$i]=(($y[$i] << $shift) & $bm) | ($y[$i-1] >> $shift2);
    // ... 后续原有逻辑不变
}

注：PHP数组默认是值传递，若不需要保留原始传入数组不变，也可以省略拷贝步骤，直接修改参数即可

2. toppart精度差异修复 #

误差原因是JS使用双精度浮点数存储数字，最大安全整数仅为2^53-1，计算超过该范围的数值时会自动舍入丢失精度，而PHP的BC函数计算的是精确值，因此需要主动对齐JS的精度行为：

function toppart($x,$start,$len){
    global $bs, $bm, $bx2, $bx, $bd, $bdm, $log2;
    $n=0;
    while($start >= 0 && $len > 0){
        $n = bcadd(bcmul($n, $bx2), $x[$start--]);
        $len--;
    }
    // 新增：转成双精度浮点数对齐JS的精度行为
    return (int)(float)$n;
}

修改后输出结果与JS完全一致，误差问题解决。

内容的提问来源于stack exchange，提问作者szmegma