Mgccl's Ivory Towerso tired

I did a small update on BCext to improve it's factorial calculating function. The algorithm follows in my old post. I also found a flaw in the 4th formula.
Reintroduced to BCext, which remind me of bcrand() function I did a long time ago, that directed me to PHPRPC. The author of PHPRPC created a not so fast large random number generator on bcmath, I want to see if he have any new version(no, it's still the old generator).

Opening the page surprised me. PHPRPC have gone a long way, it's on it's 3.0 version. Looking at the improvement and the benchmark, I think I have found the future for my lifestream. PHPRPC is like XMLRPC... but faster and easier.

Talking about lifestreams. Here are some really lifestream worthy stuff. WhatPulse. Problem with whatpulse... security. Sometimes all I need is a reliable server that record how much keystroke one have. whatpulse fails at it by having so much anti-cheat security that made me loss many keystrokes. Maybe modify pykeylogger and send result to your own server? People see how many keys you stroked real time on your profile page? AWESOME!

Ok, maybe some are not lifestream worthy, just some life statistics.
Other possibilities. Spending log(I'm using GNUcash :), playlist and chat log.

You will say there are stuff like this online. RescueTime replace ManicTime+ self written script, Whatpulse replace pykeylogger + self written script(well this one is so easy I don't see the reason to use Whatpulse...), last.fm or w/e replace foobar2000+self written script that require learning foobar2000's API, mint replace gnucash + self written script turn gnucash export into more usable format, IM history replace pidgin + self written script analyze chat logs.

Nah. When you using those services. The data is not your data, the data is their data, they don't give you the freedom to access your data(export, API). (unless you pay some fees in some instances, like RescueTime)

I used a lot of time to make it, after I failed last time, I thought there are better ways to work around. Here is how it works:
1. Subtract the minimal value from the maximal value
2. Generate the numbers for the digits by using rand()
3. Combine the digits
4. Check if it is too large or not, if is, redo 2, if not,go on.
5. Add the minimal value to the random value.

In worst case, by chance, 10 random number need to be generated before we get a good one. Numbers like 100000, 10000.
In best case, only one will be generated, numbers like 99999, 9999
In average, one out of 5 generation, because average number are 500000

function bcrand($min, $max){
	bcscale(0);
	if(bccomp($max,$min)!=1){
		return 0;
	}
	$top = bcsub($max,$min);
	$length = strlen($top);
	$rand ='';
	$n = 0;
	while(9*$n < $length){
		if($length - 9*$n >= 9){
			$rand .= mt_rand(0,999999999);
		}else{
			$rand .= mt_rand(0,str_repeat('9',$length-9*$n));
		}
		++$n;
	}
	while(bccomp($rand,$top)==1){
		$rand = substr($rand,1,$length).mt_rand(0,9);
	}
	return bcadd($rand,$min);
}

I saw another function, also called bcrand(), in PHPRPC[CHINESE], a implementation of RPC in PHP, you can find it in the bcmath.php inside the file. Here is the function for the people who can not read the Chinese website.

function bcrand($n, $s) {
    $lowBitMasks = array(0x0000, 0x0001, 0x0003, 0x0007,
                         0x000f, 0x001f, 0x003f, 0x007f,
                         0x00ff, 0x01ff, 0x03ff, 0x07ff,
                         0x0fff, 0x1fff, 0x3fff, 0x7fff);
 
    $r = $n % 16;
    $q = floor($n / 16);
    $result = '0';
    $m = '1';
    for ($i = 0; $i < $q; $i++) {
        $rand = mt_rand(0, 0xffff);
        if (($q - 1 == $i) and ($r == 0) and ($s == 1)) {
            $rand |= 0x8000;
        }
        $result = bcadd(bcmul($m, $rand), $result);
        $m = bcmul($m, '65536');
    }
    if ($r != 0) {
        $rand = mt_rand(0, $lowBitMasks[$r]);
        if ($s == 1) {
            $rand |= 1 << ($r - 1);
        }
        $result = bcadd(bcmul($m, $rand), $result);
    }
    return $result;
}

This version is different because it returns a random n-byte number, for example, bcrand(20,0) could return 634834.
I found mine is pretty fast :-)

You think use PHP to calculate the 2000 places after pi in 8 seconds is fast? you haven't see anything yet. This is the 3rd last attempt of finding pi (at least till 2020). I still have 2 more algorithms going to try. This one uses Borwein's quartic convergence algorithm on pi finding.

You want to know the speed right? It uses less than 4 second to find the 2000th place of pi! and it is only slightly slower than the older pi calculator when precision is very low(between 1 to 30).

Feel free to check the source.
This was modified to be part of the BCext class I am working on right now.

function bcpi($precision){
	bcscale($precision+6);
	$a = bcsqrt(2);
	$b = 0;
	$p = bcadd(2, $a);
	$i = 0;
	$count = ceil(log($precision+6)/log(2))-1;
	while($i < $count){
		$sqrt_a = bcsqrt($a);
		$a1 = $a;
		$a = bcdiv(bcadd($sqrt_a,bcdiv(1,$sqrt_a)),2);
		$b_up = bcmul($sqrt_a,bcadd(1,$b));
		$b_down = bcadd($a1,$b);
		$b = bcdiv($b_up, $b_down);
		$p_up = bcmul(bcmul($p,$b),bcadd(1,$a));
		$p_down = bcadd(1, $b);
		$p = bcdiv($p_up, $p_down);
		++$i;
	}
 
return bcadd($p,0,$precision);
}

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.

bcroot(2,3072);

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.3 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
//fix important bug.
 
fufunction bcroot($a, $n, $scale='default'){
    $default = bcgetscale();//Get the scale
    if($scale == 'default'){
        $scale = $default;//use default scale
    }
    $limit = ceil(log($scale+15)/log(2))+1;
    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
        $x = 1;
        $k = 0;
        bcscale($scale*$limit);
        while($k<$limit*$scale){
            $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;
        }
        $x = bcadd($x,0,$scale+1);
    }else{
    //here use many bcsqrt, because this is FAST
        $i = 0;
        $pow = log($n)/log(2);
        while($i < $pow){
            $a = bcsqrt($a,$scale*$limit);
            ++$i;
        }
        $x = bcadd($a,0,$scale+1);
    }
    bcscale($default);
    return bcround($x,$scale);
}
 
function bcround($x,$scale){
	if($x[strlen($x)-1]<5){
    	$x = bcadd($x,0,$scale);
    }else{
    	$y = str_replace(array('1','2','3','4','5','6','7','8','9'),0,$x);
    	$y[strlen($y)-1] = 10 - $x[strlen($x)-1];
    	$x = bcadd(bcadd($x,$y,$scale+1),0,$scale);
    }
	return $x;
}

I have tried to make a system that can generate a large random number, and I have encounter with problems. Here is the code that work when you first see it, but then you find there will be a great flaw in the system. I will show you step by step:

function bcrand($min, $max, $rand='rand'){
//ok, first, we subtract $max with $min
//because in the end we are going to
//add the number with $min
$rand_max = bcsub($max,$min);
$max_len = strlen($max);
 
 
 
$rand_num[0] = $rand(0,$max[0]);
  if($rand_num[0] == $max[0]){
    $ismax = 1;
}
 
$i = 1;
do{
  if($ismax){
    $rand_num[$i] = $rand(0,$max[$i]);
    if($rand_num[$i] == $max[$i]){
      $ismax = 1;
    }
  }else{
    $rand_num[$i] = $rand(0,9);
  }
  ++$i;
  usleep(mt_rand(0,10));
}while($i < $max_len);
 
 
//make the $rand_num array into a string
$i = 0;
do{
$return_num .= $rand_num[$i];
++$i;
}while($i<$max_len);
//add the returning number with the min
//number, it also take out the prefix zeros
$return_num = bcadd($return_num,$min);
return $return_num;
}

The concept is pretty easy, generate each digit of the number, and then put them together.
The first problem I meet is there could be a digit larger than the max number I specified. To solve that problem, I made the it generate the first digit equal or less than the max number's first digit first. and if the first digit is the max digit possible, the next digit will follow the same way.
This worked out fine, but if you really think about it, this is not right.
Suppose chose a number between 0 and 1000, if it choses the first digit, there is half of the chance of choosing 1, and lead to half of the chance of getting 1000, and half of the chance get the rest 999 numbers.
So I still have to work on that a bit more.