Skip to main content

Lazy Fibonacci Array

What’s the 1,337th number in the Fibonacci sequence? It’s 1.1667830241021E+279, of course!

Here’s an cool snippet of PHP code I wrote several months ago which implements not only PHP’s Iterator interface to provide an lazily-iterable list of Fibonacci numbers, but also the ArrayAccess interface and some fancy math to provide indexed access, too. Lazy evaluation is pretty cool because it saves memory. In this case, in effect you have an array of 1,478 of elements (bound only by the capacity of float values) while only using 984 bytes of memory for the object:

<?php
class Fibonacci implements Iterator, ArrayAccess
{
    const PHI = 1.618033989;

    private $a;
    private $b;
    private $i;

    public function __construct() {
    }

    public function rewind() {
        $this->a = 1;
        $this->b = 0;
        $this->i = 0;
    }

    public function current() {
        return $this->b;
    }

    public function key() {
       return $this->i;
    }

    public function next() {
        $this->i++;
        $tmp = $this->a + $this->b;
        $this->a = $this->b;
        $this->b = $tmp;
    }

    public function valid() {
        return $this->offsetExists($this->i);
    }

    public function offsetExists($i) {
        // Fib(1476) = float(1.30698922376E+308)
        // Fib(1477) = float(INF)
        return $i > -1 && $i < 1478;
    }

    public function offsetGet($i) {
        // en.wikipedia.org/wiki/Fibonacci_number#Computation_by_rounding
        return floor((pow(self::PHI, $i) / sqrt(5)) + 0.5);
    }

    public function offsetSet($i, $val) {
        throw new Exception("sequence is read-only");
    }

    public function offsetUnset($i) {
        throw new Exception("sequence is read-only");
    }
}

$mem = memory_get_usage();
$fib = new Fibonacci();

echo "Memory used for Fibonacci object: " . (memory_get_usage() - $mem) . "\n";
echo "The 1337th number in the sequence is: " . $fib[1337] . "\n";

echo "Here is the sequence:\n";
foreach ($fib as $i => $f) {
    var_dump($f);
}

Comments

Popular posts from this blog

Geolocation Search

Services that allow users to identify nearby points of interest continue to grow in popularity. I'm sure we're all familiar with social websites that let you search for the profiles of people near a postal code, or mobile applications that use geolocation to identify Thai restaurants within walking distance. It's surprisingly simple to implement such functionality, and in this post I will discuss how to do so.

The first step is to obtain the latitude and longitude coordinates of any locations you want to make searchable. In the restaurant scenario, you'd want the latitude and longitude of each eatery. In the social website scenario, you'd want to obtain a list of postal codes with their centroid latitude and longitude.

In general, postal code-based geolocation is a bad idea; their boundaries rarely form simple polygons, the area they cover vary in size, and are subject to change based on the whims of the postal service. But many times we find ourselves stuck on a c…

Composing Music with PHP

I’m not an expert on probability theory, artificial intelligence, and machine learning. And even my Music 201 class from years ago has been long forgotten. But if you’ll indulge me for the next 10 minutes, I think you’ll find that even just a little knowledge can yield impressive results if creatively woven together. I’d like to share with you how to teach PHP to compose music. Here’s an example: You’re looking at a melody generated by PHP. It’s not the most memorable, but it’s not unpleasant either. And surprisingly, the code to generate such sequences is rather brief. So what’s going on? The script calculates a probability map of melodic intervals and applies a Markov process to generate a new sequence. In friendlier terms, musical data is analyzed by a script to learn which intervals make up pleasing melodies. It then creates a new composition by selecting pitches based on the possibilities it’s observed. . Standing on ShouldersComposition doesn’t happen in a vacuum. Bach was f…

Creepy JavaScript Tracking

I recently began allergy shots so my new Monday morning routine includes me sitting in a doctor's office for 30 minutes (I must wait after receiving the shots and be checked by a nurse to make sure there was no reaction). With nothing else better to do while I waited last week, I started playing around with some JavaScript. This is what I came up with:
<html> <head> <title>Test</title> <script type="text/javascript"> window.onload = function () { var mX = 0,  mY = 0, sX = 0,  sY = 0, queue = [], interval = 200, recIntv = null, playIntv = null, b = document.body, de = document.documentElement, cursor = document.getElementById("cursor"), record = document.getElementById("record"), play = document.getElementById("play"); window.onmousemove = function (e) { e = e || window.event; if (e.pageX || e.pageY) { …