Convert JavaScript function to PHP

Question

I have a JS function, with array inputs.

For example:

x=[ 239709880, 250229420, 109667654, 196414465, 13098 ]
y=[ 78135241, 54642792, 249 ]

OR:

x=[ 0, 0, 0, 0, 0, 0, 1 ]
y=[ 78135241, 54642792, 249 ]

OR:

x=[ 49 ]
y=[ 33 ]

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;
}

What I have done under 5 days so far in PHP:

function bdiv($x,$y){
    global $bs, $bm, $bx2, $bx, $bd, $bdm, $log2;
    $arr=[];
    $n=count($x)-1;
    $t=count($y)-1;
    $nmt=$n-$t;

    if($n < $t || $n==$t && ($x[$n]<$y[$n] || $n>0 && $x[$n]==$y[$n] && $x[$n-1]<$y[$n-1]))
        return ['q'=>[0], 'mod'=>$x];

    if($n==$t && toppart($x,$t,2)/toppart($y,$t,2) <4){
        $q=0;
        for(;;){
            $xx=bsub($x,$y);
            if(count($xx)==0)
                break;
            $x=$xx;
            $q++;
        }
        return ['q'=>[$q], 'mod'=>$x];
    }

    $shift2=floor(log($y[$t])/$log2)+1;
    $shift=$bs-$shift2;
    if($shift){

/////////////////////////////////////////////// Booboo
        //$x = array_merge(array(),$x);
        //$y = array_merge(array(),$y);

        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;
    }
    $q=zeros($nmt+1);

    //array_push($arr, zeros($nmt));
    //array_push($arr, $y);
    //$y2=array_merge(...$arr);
    //////////////////////////////////// use array_merge straight away
    $y2=array_merge(zeros($nmt),$y);

    for(;;){
        $x2=bsub($x,$y2);
        if(count($x2)==0)
            break;
        $q[$nmt]++;
        $x=$x2;
    }

    $yt=$y[$t];
    $top=toppart($y,$t,2);

    for($i=$n; $i>$t; $i--){
        $m=$i-$t-1;
        if($i >= count($x))
            $q[$m]=1;
        else if($x[$i] == $yt)
            $q[$m]=$bm;
        else
            $q[$m]=floor(toppart($x,$i,2)/$yt);

        $topx=toppart($x,$i,3);
        while($q[$m] * $top > $topx)
            $q[$m]--;

        $y2=array_slice($y2,1);
        $x2=bsub($x,bmul([$q[$m]],$y2));

        if(count($x2)==0){
            $q[$m]--;
            $x2=bsub($x,bmul([$q[$m]],$y2));
        }
        $x=$x2;
    }

    if($shift){
        for($i=0; $i<count($x)-1; $i++)
            $x[$i]=($x[$i] >> $shift) | (($x[$i+1] << $shift2) & $bm);
        $x[count($x)-1] >>= $shift;
    }

    while(count($q) > 1 && $q[count($q)-1]==0)
        $q=array_slice($q, 0, count($q)-1);
    while(count($x) > 1 && $x[count($x)-1]==0)
        $x=array_slice($x, 0, count($x)-1);

    return ['q'=>$q, 'mod'=>$x];
}

So as I marked in the PHP code I have a problem with the array_push($x,$x), seems like this is not the equivalent of x=x.concat(). Array_push add the whole current $x values as a new element to the existing $x array:

$x=[ 1, 2, 3 ];
array_push($x,$x);
then $x will be [ 1, 2, 3, [ 1, 2, 3 ] ]

If I try to flatten the array ($x=array_merge(...$x);) then a new PHP error shows up: array_merge(): Argument #1 is not an array

I would really appreciate it if anyone have any idea, how to convert properly this JS function to a PHP version. Thanks in advance.

==========================> UPDATE I

@Kiran Shakya idea to replace x=x.concat() with $x=array_merge(array(),$x); is actually working or at least I don't get any PHP error or warning on that, but start an infinite loop, which I have to shut manually. The script calling the toppart function, which operating with arbitrary precision numbers (multiply and add):

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

The interesting part is, the JS returned for an example 70144566321522750 but the PHP returned 70144566321522751. In the later loop the differences are much bigger.
I have checked all numbers in both versions and all the same inputs: x,start,len,bx2. This can be a bug or one of them cannot handle big integers or what can be the reason?

==========================> UPDATE II

I applied Booboo solution, I just completely skipped the concat() parts

So the inputs are:

$x=[ 210763776, 109357119, 261308872];
$start=2;
$len=2;
$bx2=268435456;

...and returns 70144566321522751 in PHP and 70144566321522750 in JS. I use bcadd() and bcmul() but the result is same if I'm using math operator signs.

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;
}

Answer 1

If what you are doing with x = x.concat() is attempting to ensure that the original passed array is not being modified by your function, you do not have to do anything to ensure that in your PHP version of this function because by default arguments will be copied rather than passed by reference. To force an array to be passed by reference in PHP, you must preceded the argument name with an ampersand (&). This can be demonstrated with the following program where we have defined two functions that each modify the first element of the passed array. In the first function, test1, the array argument is copied so the original passed array remains unmodified. But in the second function, test2, the array argument is passed by reference and when the function returns, the original passed array will have been modified. The only difference between the two functions is that in test1 the arguments is defined as $x and in test2 as &$x:

<?php

// $x is passed by value:
function test1($x)
{
    $x[0] = 9;
    print_r($x);
}

// $x is passed by reference:
function test2(&$x)
{
    $x[0] = 9;
    print_r($x);
}

$my_array = [0, 1, 2];
echo "Pass by value:\n";
test1($my_array); //$my_array remains unmodified
print_r($my_array);

echo "\n\nPass by reference:\n";
test2($my_array); //$my_array is modified
print_r($my_array);

Prints:

Pass by value:
Array
(
    [0] => 9
    [1] => 1
    [2] => 2
)
Array
(
    [0] => 0
    [1] => 1
    [2] => 2
)


Pass by reference:
Array
(
    [0] => 9
    [1] => 1
    [2] => 2
)
Array
(
    [0] => 9
    [1] => 1
    [2] => 2
)

Update

You have several issues. First, you describe toppart returning different values in the JavaScript and PHP versions and you ask us to explain the discrepeancy but you never specify what the actual start, len and bx2 value inputs were to the functions and leave us to figure that out for ourselves. And did you post the PHP version of toppart because I don't see it.

Second, let me elaborate on my previous response. I should have said that arrays will by default be copied rather than passed by reference (class objects will be passed by reference, but that is not applicable here). But that is not just for passing arguments to functions. Consider the following:

$a = [0, 1, 2];
$b = $a; // copy-on-write
$b[0] = 9; // $b is [9, 1, 2]
echo $a; // $a is still [0, 1, 2]

So if you have a JavaScript array a and the assignment b = a, which is a reference copy such that if you modify b you are modifying the array referenced by b you are also modifying the array referenced by a, the semantic equivalent in PHP is $b = @$a;. This ensures that $b and $a not only refer to the same array but if you modify the array referenced by $b, you will be modifying the same array referenced by $a.

So if you have a JavaScript function defined as follows:

function bdiv(x, y)
{
etc.

where $x and $y are arrays, theoretically bdiv could modify the actual arrays being passed and aliased as x and y and therefore the semantic equivalent in PHP would be to define this function as follows:

function bdiv(@$x, @$y)
{
etc.

But here is the problem. Later on in the JavaScript code we have:

x=x.concat()

In JavaScript you have no choice but to pass array arguments by reference. Ealrly on in the JavaScript code there is:

        for(;;) {
            xx=bsub(x,y)
            if(xx.length==0) break
            x=xx; q++
        }

The assignment to x is conditionally executed but would certainly modify the passed x argument. So later on when the code x=x.concat() is executed to assign a copy of the current value of x to x, this would certainly prevent further subsequent modification of the passed array, but what else does it accomplish? Prior to the copy of x there are assignments such as arr['mod'] = x and after the copy of x is made we have assignments to x[0]. Without the copy of x being made that assignment to x[0] would also be updating the array stored at arr['mod']. So the array copy is being done to prevent that.

There are several PHP idioms for making a copy of an array, as already pointed out, for example, $x = array_merge([], $x). But even if you execute this statement in PHP, once you have defined the argument to bdiv as @$x, i.e. pass by reference, you would still be subsequently modifying the passed array as you make assignments to the array referenced by x. So there can be no exact PHP equivalent of the JavaScript result as far as what the passed JavaScript x array will end being when the function returns. The following PHP program demonstrated that even after a copy of x is assigned to x and then an assignment is made to the new array referenced by x, it updates the passed array:

<?php

function test(&$x)
{
    $x = array_merge(array(), $x);
    $x[0] = 9;
    print_r($x);
}

$arr = [0, 1, 2];
test($arr);
print_r($arr);

Prints:

Array
(
    [0] => 9
    [1] => 1
    [2] => 2
)
Array
(
    [0] => 9
    [1] => 1
    [2] => 2
)

So this array copying will not have the other effect of preventing further modifications to the passed array. As far as I can tell the original JavaScript program actually leaves the original passed array in an undefined state. You might as well leave the PHP function defined as bdiv($x, $y) so that the original arrays are left unmodified.

But the above discussion suggests that you may have a problem elsewhere. Where you have a JavaScript assignment of the form a = b where b is an array and there is a subsequent modification to a, for example a[i] = some_value, the equivalent PHP code must be $a = @$b; etc,, that is, a reference assignment.

And as mentioned in a comment by @AKX, you should look into the BC Math functions if you are having issues with toppart.

Answer 2

I am confused why your JavaScript code even has:

x=x.concat()
y=y.concat()

They don't serve any purpose other than assigning a new copy of same array to itself. If it was intended to avoid modification on the original array, then you can simply replace those two lines of code with:

$x = array_merge(array(), $x);
$y = array_merge(array(), $y);

They both serve exact same purpose.

At this point, I am not sure about rest of the php code that you wrote so far, but if it helps you in anyway, that is fine.

Answer 3

replace array_push with array_merge.

This will return the merged array then store the result in $x;

array_merge is meant for arrays. it will take the values from one array and append it to the other. just like concat does in JS.

... splits the array ($x) into several values, this is not the correct input. it is the equivalent of array_merge(1,2,3) (i.e arrays are not being inputted)

$x = array(1,2,3);
$x = array_merge($x,$x);
var_dump($x); //output: [1,2,3,1,2,3]

echo $x[4]; // output: 2

if i've misunderstood the question please let me know.

Answer 4

Use array_merge instead of array_push i.e

  $x = array(1, 2, 3);
       print_r(array_merge($x,$x));