A week ago, I have released a bcpow() no fraction exponent work around. It is good, like all my scripts, but it is not fast. This code could take 12.152509 second to run the following statement on my pc.
The main reason of slowness is in the algorithm. There is a bcpow() function that will use the second number passed to bcroot() as the exponent. In that above script, it multiple 2 for over 3000 times!
PHP's bcsqrt() function is very fast, with a little math knowledge you would know that 3072 = 1024 * 3 = 2^10 * 3. The new version of the function takes advantage of the bcsqrt()'s speed. So now, it runs bcsqrt() 10 times and then multiple it with bcpow($whatever, 3). Result? check this out:
0.000928 second.
You might want to know how did I found a number's product that is a power of 2.First of my attempt was do many bcmod() to the number until it returns 1. But then I noticed in binary, a number that have a product that is a power of 2, will have some trailing zeros, the number of trailing zeros is the exponent of 2. The other product will be what remains in the front. It will be great for you to know the function decbin() and bindec(). For example:
decbin(10) = 1010. 1 trailing zeros, so 10 = 2^1 * bindec(101)
decbin(12) = 1100. 2 trailing zeros, so 12 = 2^2 * bindec(11)
decbin(16) = 10000. 4 trailing zeros, so 16 = 2^4 * bindec(1)
Neat...I uses like 10 minute of my free time trying this...
Here is the new version of the function, it still need the bcgetscale() function that exists in my last post about bcroot()
//Version 0.2 of BCRoot
//Change Log: It uses a lot bcsqrt() to make the speed fast
//fix a small decimal bug, where the last decimal could be wrong
function bcroot($a, $n, $scale='default'){
$default = bcgetscale();//Get the scale
if($scale == 'default'){
$scale = $default;//use default scale
}
if($n & ($n-1)){//check if $n is the power of 2, return 0 if is
//decbin is the reason this function can't have number
//larger than 2^31
$bin = decbin($n);
$i = strlen($bin)-1;
$pow = 0;
while($i){
if($bin[$i]==='0'){
++$pow; --$i;
}else{
break;
}
}
$n = bcdiv($n, bcpow(2, $pow),0);
//now use Newton?s method to find the number
bcscale($scale+15);
$x = 1;
$k = 0;
$limit = ceil(log($scale+15)/log(2))+1;
while($k<$limit){
$t1 = bcdiv(1,$n);
$t21 = bcmul(bcsub($n,1),$x);
$t22 = bcdiv($a,bcpow($x, $n-1));
$t2 = bcadd($t21,$t22);
$x = bcmul($t1, $t2);
++$k;
}
$i = 0;
while($i < $pow){
$x = bcsqrt($x,$scale+3);
++$i;
}
bcscale($default);
return bcadd($x,0,$scale);
}else{
//here use many bcsqrt, because this is FAST
$i = 0;
$pow = log($n)/log(2);
while($i < $pow){
$a = bcsqrt($a,$scale+3);
++$i;
}
return bcadd($a,0,$scale);
}
}
Recent comments
1 day 2 hours ago
1 day 18 hours ago
1 day 20 hours ago
3 days 18 hours ago
3 days 18 hours ago
3 days 18 hours ago
3 days 23 hours ago
4 days 7 hours ago
4 days 10 hours ago
5 days 18 hours ago