Fishtrap

php and other stuff I know

1 August 2011
by nat
0 comments

Borwein’s algorithm for Π a PHP implementation

One of the joys of Maths is the fact that the names for things sound impressive add to that the fact that the notation can look very off putting if you you don’t know what it says and this has the effect of making you seem very erudite when talking about it. With this in mind I thought I’d post a quick implementation of Borwein’s algorithm for convergance on Π.

The generation of increasing digits of Π is in itself completely pointless but makes an interesting area of research for mathematicians and computer scientists with parallel advances in algorithm and hardware. PHP is possibly the least suitable language to implement these computationally intense calculations. However, it is possible for todays PHP scripts to quickly generate digits that took hours of computing time in the 1950′s and 1960′s.  Borwein’s algorithm is interesting for the increasing number of correct digits it gives with each iteration. According to wikipedia the algorithm is given by starting out with:

\begin{align} a_0 & = 6 - 4\sqrt{2} \\ y_0 & = \sqrt{2} - 1 \end{align}

And then iterating

\begin{align} y_{k+1} & = \frac{1-(1-y_k^4)^{1/4}}{1+(1-y_k^4)^{1/4}} \\ a_{k+1} & = a_k(1+y_{k+1})^4 - 2^{2k+3} y_{k+1} (1 + y_{k+1} + y_{k+1}^2) \end{align} 

function borwein($precision){
	// set scale with suitable spare room
	bcscale($precision+5);
	//inital conditions
	$rootTwo = bcsqrt(2);
	$a = bcsub(6, bcmul(4, $rootTwo));
	$y = bcsub($rootTwo, 1);
	//number of interations needed
	$count = floor(log($precision)/log(4));
	for($k = 0; $k < $count; $k++){
		$sqrt = bcsqrt(bcsub(1,bcpow($y, 4)));
		$right = bcsqrt($sqrt);
		$top = bcsub(1, $right);
		$bottom = bcadd(1, $right);
		$y = bcdiv($top, $bottom);
		$onePlusY = bcadd(1, $y);
		$left = bcmul($a, bcpow($onePlusY, 4));
		$y2 = bcpow($y, 2);
		$power = bcpow(2, (2*$k+3));
		$expansion = bcadd($onePlusY, $y2);
		$right = bcmul($power, bcmul($y, $expansion));
		$a = bcsub($left, $right);
	}
return bcdiv(1, $a, $precision);
}
echo borwein(2037), PHP_EOL;

9 July 2011
by admin
0 comments

Factorial class

Earlier in the week i started experimenting with translating infinite series calculations for the value of Π into php. I started with the Chudnovsky brothers algorithm which I understood to be the fastest.

As you will see extensive use of factorials is made. I was using the bc extension for PHP which does not have a simple way of calculating factorials. I came up with the following class to try and calculate them efficiently from the nearest previously calculated. Using it I was able to cut the calculation time for 2037 digits in half.

<?php
class Factiorial {
	private static $_cache = array(1 => 1);
	public function calculate($n) {
		$nearest = $this->findNearestInCache($n);
		$answer = self::$_cache[$nearest];
		$diff = $n - $nearest;
		if ($diff > 0) {
			for ($i = $nearest; $i < $n; ++$i) {
				$answer = bcadd($answer, bcmul($answer,$i));
				self::$_cache[$i+1] = $answer;
			}
		} else {
			for ($i = $nearest; $i > $n; --$i) {
				$answer = bcdiv($answer,$i);
			}
		}
		return $answer;
	}
	private function findNearestInCache($n) {
		$keys = array_keys(self::$_cache);
		rsort($keys);
		$nearest = current($keys) ;
		$smallestDiff = abs(current($keys) - $n);
			foreach ($keys as $key) {
				if ($diff = abs($n - $key) < $smallestDiff) {
					$nearest = $key;
					$smallestDiff = $diff;
				}
			}
			return $nearest;
	}
}

This only really works because we are calculating successive factorials and will often be calculating the same value several times. Having arrays of several thousand items in the cache could be quite slow so I tried limiting the size of the cache array but the extra bookkeeping overhead proved to slow the script down.

16 June 2011
by nat
12 Comments

Compiling PHP to use mysqlnd on ubuntu

Distro maintainers seem to be a little slow in using mysqlnd. I guess they have their own ideas and needs.

The best way I’ve found of installing mysqlnd on ubuntu is to use dpkg to rebuild the .deb. Of course this will need to be done when ever you update the PHP package so is not recomended for anything other than experimental servers.

Quick step by step

Install everything needed to compile C code

sudo apt-get install build-essential debhelper

Install any special depandancies for building PHP such as bison

sudo apt-get build-dep php5

Install the PHP source for the current PHP package

sudo apt-get source php5

This will download the source code for your PHP version into the current directory

cd php5-5.3.2/

Then edit the file debian/patches/series or in older ubuntu releases debian/patches/order

sudo vim debian/patches/series

remove the lines
force_libmysqlclient_r.patch
and while we’re at it remove this line which removes the config flags from phpinfo() apparently done by debian to stop false bug reports but quite annoying
052-phpinfo_no_configure.patch

then edit the rules file

sudo vim debian/patches/rules

sudo vim debian/rules

search for
–with-mysql=shared, /usr \
replace with
–with-mysql=mysqlnd \

same with
–with-mysqli=shared, /usr \
replace with
–with-mysqli=mysqlnd \

make –enable-pdo=shared or –with-pdo=shared \

into –with-enable or –with-pdo

and
–with-pdo-mysql=shared, /usr \
into
–with-pdo-mysql=mysqlnd \

This will build mysql as a static module rather than load it dynamically this will save building each mysql extension separately with mysqlnd

stop the tests running by exporting an environment variable

export DEB_BUILD_OPTIONS=nocheck

Now build the package

sudo dpkg-buildpackage

Go and do something else for a little while.

Once done if you

cd ..
ls

You should see a big list of debs

dpkg the ones you need such as

sudo dpkg -i php5-common_5.3.2-1ubuntu4.9_amd64.deb
sudo dpkg -i libapache2-mod-php5_5.3.2-1ubuntu4.9_amd64.deb

bingo the output of phpinfo() and php -m should confirm you have mysqlnd installed

1 June 2011
by nat
2 Comments

MySQL native driver or mysqlnd

This is the first post of an series on the MySQL native driver or mysqlnd. In particualr I hope to cover the creation of a mysqlnd plugin both as a C extension to PHP and also as PHP code using mysqlnd_uh.

What is mysqlnd?

Quite simply mysqlnd is a PHP extension that handles talking to MySQL databases. Previously this was done via a C library from MySQL called libmysql. This library was used by many different languages to talk to a MySQL server and it worked well. However, with MySQL and PHP being so popular the MySQL team looked at improving the performance of the combination as well as being more compatible with the PHP license. In particular in the traditional setup every result set was being copied twice once within libmysql and once in the PHP mysql extensions. Mysqlnd is a PHP extension that exports no new PHP functions it has the sole job of talking to mysql servers. If installed it will be used by all the other mysql libraries such as mysqli etc as the client. It has the added benefit of not needing to be built against any one version of libmysql making it more portable.

Where can I get my mysqlnd?

You may already be using it! Mysqlnd has been in the PHP code base since PHP 5.3. It is the default mysql client on PHP windows binaries.
to find out do

php -m

to list all installed modules

[PHP Modules]
apc
bcmath
bz2
....
mysqlnd
...

or look at the output of phpinfo(); in a browser.

If you don’t have it then I’m afraid the only way is to recompile PHP with the correct flags. These are

--with-mysql=mysqlnd \
--with-mysqli=mysqlnd \
--with-pdo-mysql=mysqlnd \

Distro packagers have been reluctant to switch from libmysql as stability is of prime importance to them. If you want to build php on ubuntu to include mysqlnd see this post.

What now, I can’t see anything?

As mentioned before mysqlnd adds no new PHP functions. There is however, one PHP function that will only work if you are using this newer client. mysqli_result::fetch_all gets all the results from a results set as an array which is assoivative, numeric or both. If you try using this function with libmysql you will get an error.

<?php
$mysqli = new mysqli("localhost", "nat", "supersecretpassword", "mysql");
$query = "SELECT * from db";
$result = $mysqli->query($query);
$rows = $result->fetch_all();
var_dump($rows);

Fatal error: Call to undefined method mysqli_result::fetch_all() in /home/nat/test.php on line 8

The function is useful in some cases but putting large result sets into memory is generally not the best idea as it will consume large amounts of memory (not true see Ulf’s comments) and there are already functions to seek, iterate and find the size of results sets.

25 May 2011
by nat
0 comments

Simplest Possible Mandlebrot Script

While working on explaning the mandlebrot set I came up with this script which reduces it down to the most simple. You will need https://github.com/natmchugh/complex_numbers or else some similar PHP implementation.

You can see the output here.

<?php
if ('cli' != php_sapi_name()) {
	echo "<pre>";
}
$maxIterations = 50;
$step = 1/10;
for ($imaginary = 1; $imaginary > -1; $imaginary = $imaginary - $step) {
	for ($real = -1.5 ; $real < 0.5; $real = $real + $step) {
		$z = new ComplexNumber(0,0);
		$c = new ComplexNumber($real, $imaginary);
		$iterationCount = 0;
		while ($z->lessThanTwo() && $iterationCount < $maxIterations) {
			$z->square();
			$z->add($c);
			++$iterationCount;
		}
		if ($iterationCount >= $maxIterations) {
			echo '*';
		} else {
			echo ' ';
		}
	}
	echo PHP_EOL;
}
if ('cli' != php_sapi_name()) {
	echo "</pre>";
}