Duncan's blog

October 29, 2014

Project Euler: problem 99 (PHP) – Largest exponential

Filed under: PHP,Project Euler — duncan @ 7:00 am

99I’m doing these Project Euler mathematical puzzles as a simple practical exercise for teaching myself PHP, and I’d appreciate any feedback on my code.

Problem 99:

Comparing two numbers written in index form like 211 and 37 is not difficult, as any calculator would confirm that 211 = 2048 < 37 = 2187.

However, confirming that 632382518061 > 519432525806 would be much more difficult, as both numbers contain over three million digits.

Using base_exp.txt, a 22K text file containing one thousand lines with a base/exponent pair on each line, determine which line number has the greatest numerical value.

NOTE: The first two lines in the file represent the numbers in the example given above.

Interesting, sounds quite difficult.  At first I thought I could use the BC Math functions which have proven so useful in many of the previous puzzles and “support numbers of any size and precision”.  However they didn’t seem to work; according to this StackExchange question they “can handle numbers greater than 2^1000000 (which is 301,030+ digits)“. We’re dealing with numbers here that are ten-fold of that!  So I used the GMP functions instead, which “allow you to work with arbitrary-length integers”.

<?php
$pairs = file('p099_base_exp.txt');

$max = 0;

foreach($pairs as $key=>$pair) {
	$numbers = explode(",", $pair);
	$base = $numbers[0];
	$exponent = $numbers[1];

	$power = gmp_pow($base, intval($exponent));
	
	if (gmp_cmp($power, $max) > 0) {
		$max = $power;
		$lineNumber = $key;
	}
}

echo $lineNumber+1;

I read the file in using file(), turning each line into an array element.  I then loop over those 1000 array elements, using explode() to split each line into its base and exponent parts.

Then I use the gmp_pow() function; however when I tried it initially simply using gmp_pow($base, $exponent) it threw up this error: “A non well formed numeric value encountered“.  It expects $exponent to be an integer, which to all intents and purposes, it seems to be.  However I had to explicitly cast it to an integer, using either intval($exponent) or (int)$exponent – both seemed to work.

Initially I thought I had to use a GMP number for the base, so was using gmp_init() to create one from $base.  However in the end that didn’t seem to be necessary.  So the gmp_pow() function is fussy about what kind of value it gets for the exponenent, but less-so for the base… curious.

After working out the power, I then compare it the maximum power so far, using gmp_cmp().  Each time I get a new maximum value I keep track of which line number that belongs to.  At the end when I output that I increment it by 1, due to PHP arrays being zero-indexed.

This is very slow code, taking close to 5 minutes!

PS: to get the GMP functions to work on my Windows environment I had to uncomment this line in php.ini:

extension=php_gmp.dll

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: