有一个素数因子分解的算法python
。它对大整数运行约10毫秒。我重写了它的php
。此外,对于非常大的整数,我在php中使用了bc
和gmp
函数。结果是非常慢并且需要大约4秒钟的相同输入!PHP vs python,php中的性能问题
这里是我的代码:
(注:功能分成主要功能是分开测试,他们都非常快)
public function primefactors($n, $sort = false) {
$smallprimes = $this->primesbelow(10000);
$factors = [];
// NOTE: bc or gmp functions is used for big numbers calculations
$limit = bcadd(bcsqrt($n) , 1);
foreach ($smallprimes as $checker) {
if ($checker > $limit) {
break;
}
// while (gmp_mod($n, $checker) == 0) {
// 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 = bcadd(bcsqrt($n) , 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;
}
有没有在我的代码的任何性能问题?或者php
本身有性能问题?为什么python如此之快? (约40倍的速度)
编辑:这里是Python代码:
smallprimes = primesbelow(10000) # might seem low, but 1000*1000 = 1000000, so this will fully factor every composite < 1000000
def primefactors(n, sort=False):
factors = []
limit = int(n ** .5) + 1
for checker in smallprimes:
if checker > limit: break
while n % checker == 0:
factors.append(checker)
n //= checker
limit = int(n ** .5) + 1
if checker > limit: break
if n < 2: return factors
while n > 1:
if isprime(n):
factors.append(n)
break
factor = pollard_brent(n) # trial division did not fully factor, switch to pollard-brent
factors.extend(primefactors(factor)) # recurse to factor the not necessarily prime factor returned by pollard-brent
n //= factor
if sort: factors.sort()
return factors
没有相应的Python代码我们如何比较你的“翻译”? –
好吧,让我提供python代码。谢谢。 –
@ Ev.Kounis请检查编辑部分。 –