Thread: Fibonacci numbers

Here it is if you've ever wanted to have a class that creates them, and we all do, I just know it :-) This is a quick class I wrote while being bored, if anyone wants to make comments I'd welcome them. :-)

Code:

#include <iostream>
#include <cstdlib>
#include <cmath>

using namespace std;

class Fibonacci {
  unsigned long *cache;
  int cache_max;
public:
  explicit Fibonacci(int max = 46);
  ~Fibonacci();

  int max();
  unsigned long get(int);
  unsigned long operator[](int);
};

Fibonacci::Fibonacci(int max)
  : cache_max(max + 1)
{
  cache = new(nothrow) unsigned long[cache_max];

  if (cache == 0)
  {
    cerr<<"No memory"<<endl;
    exit(1);
  }

  for (int i = 0; i < cache_max; i++)
  {
    cache[i] = 0;
  }
}

Fibonacci::~Fibonacci()
{
  delete cache;
}

int Fibonacci::max()
{
  return cache_max;
}

unsigned long Fibonacci::get(int n)
{
  if (n > cache_max || n < 0)
  {
    cerr<<"Subscript out of range"<<endl;
    return 0;
  }
  else if (cache[n] == 0)
  {
    double s = sqrt(5.0);
    double x = 0.5 * s;

    // Deep magic
    cache[n] = ((pow(0.5 + x, n)) - (pow(0.5 - x, n))) / s;
  }

  return cache[n];
}

unsigned long Fibonacci::operator[](int sub)
{
  return get(sub);
}

int main()
{
  Fibonacci fib;

  for (int i = 0; i < fib.max(); i++)
  {
    cout<< fib[i] <<endl;
  }
}

>>Wow, when you're bored, you're REALLY bored!
Tell me about it, I actually wrote it in Perl first, then ported it to C++. Next I'll add operator overloading to the Perl script. :-)

Code:

#!usr/bin/perl -w

use strict;

package Fibonacci;

sub make {
  my $self = shift;
  my $ref = {cache_max => 47, cache => []};

  bless $ref, $self;
}

sub get {
  my ($self, $sub) = @_;

  if ($sub < 0 || $sub > $self->{cache_max}) {
    print STDERR "Subscript is out of range\n";
  }

  return $self->{cache}->[$sub] if defined $self->{cache}->[$sub];

  my $s = sqrt 5.0;
  my $x = 0.5 * sqrt 5.0;

  # Deep magic
  $self->{cache}->[$sub] = 
    int((((0.5 + $x) ** $sub) - ((0.5 - $x) ** $sub)) / $s);
}

sub max {
  my $self = shift;

  $self->{cache_max};
}

package main;

my $fib = Fibonacci->make;

for (my $i = 0; $i < $fib->max; $i++) {
  print $fib->get($i), "\n";
}

Minor bug...delete cache should be delete [] cache...but yeah, you were right, I've always wanted the code for that one.

One more comment, too. IMO you needn't bounds check on the array access's because of the speed tradeoff of the two comparisons. Most code will/should mind it's own bounds...and if it does then not only does your code do bounds checking, so does their's! :-/

- cheers.

>>Minor bug...delete cache should be delete [] cache
Yikes, I can't believe I missed that. Thanks for your sharp eyes. That's a major bug by the way, it's undefined behavior. :-)

>>IMO you needn't bounds check on the array access's because of the speed tradeoff of the two comparisons.
I like to be neighborly and protect people against themselves when I can :-) But a middle ground is probably better, give the user a choice of a range checked get() for more compact code, or non checked get() for speedyness, like the [] and at() methods of vector.