CODEWITHSUNDEEP
phppythonintprime-factoring
Vahid Najafi
Vahid Najafi

Reputation: 5263

Php prime factorization time and size issue

There is a python implemention code for prime factorization. It tooks about 0.1 second for returning the answer. I implemented that for php. In large numbers it runs about 3 seconds (And sometimes it never return the answer)

NOTE: I even used BCMath functions in php for handling very large numbers.

NOTE: All other functions inside this function (mentioned below), are tested separately, but there is a problem in one of them (pollard_brent) that use php built in function gmp_mod. When I run this:

// python handles these big numbers fine, and returns 1 for this:
echo gmp_mod(10000000000000000000001 , 2);

Gives me this error: 

Message: gmp_mod(): Unable to convert variable to GMP - wrong type

My factorization code:

public function primefactors($n, $sort = false) {
    $smallprimes = $this->primesbelow(10000);
    $factors = [];

    $limit = bcadd((bcpow($n, 0.5)) , 1);

    foreach ($smallprimes as $checker) {
        if ($checker > $limit) {
            break;
        }
        // while ($n%$checker == 0) {
        while ( bcmod($n, $checker) == 0 ) {
            array_push($factors, $checker);
            // $n = (int)($n/$checker);
            $n = bcdiv($n, $checker);
            // $limit = (int)(bcpow($n, 0.5)) + 1;
            // $limit = (bcpow($n, 0.5)) + 1;
            $limit = bcadd((bcpow($n, 0.5)) , 1);
            if ($checker > $limit) {
                break;
            }
        }
    }

    if ($n < 2) {
        return $factors;
    }

    while ($n > 1) {
        if ($this->isprime($n)) {
            array_push($factors, $n);
            // var_dump($factors);
            break;
        }
        $factor  = $this->pollard_brent($n);
        $factors = array_merge($factors, $this->primefactors($factor)); 
        $n = (int)($n/$factor);
    }
    if ($sort) {
        sort($factors);
    }

    return $factors;

}

Any idea?

Upvotes: 1

Views: 183

Answers (1)

AbraCadaver
AbraCadaver

Reputation: 78994

As pointed out in the comments, the manual shows that both arguments must be a GMP object or a numeric string. This works:

echo gmp_mod("10000000000000000000001", "2");

Smaller numbers may work as PHP will convert the integer to a string within the function, however 10000000000000000000001 is longer than PHP_INT_MAX so it won't work.

echo 10000000000000000000001;

Yields:

1.0E+22

Upvotes: 3

Related Questions