Fibonacci numbers

This is a discussion on Fibonacci numbers within the C++ Programming forums, part of the General Programming Boards category; Here it is if you've ever wanted to have a class that creates them, and we all do, I just ...

  1. #1
    Registered User Cela's Avatar
    Join Date
    Jan 2003
    Posts
    362

    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;
      }
    }
    *Cela*

  2. #2
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Wow, when you're bored, you're REALLY bored!

    Me likes by the way!

  3. #3
    Registered User Cela's Avatar
    Join Date
    Jan 2003
    Posts
    362
    >>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";
    }
    *Cela*

  4. #4
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,600
    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.
    Last edited by Sebastiani; 01-29-2003 at 10:20 PM.
    Code:
    if( numeric_limits< byte >::digits != bits_per_byte )
        error( "program requires bits_per_byte-bit bytes" );
    24bbs.cpp

  5. #5
    Registered User Cela's Avatar
    Join Date
    Jan 2003
    Posts
    362
    >>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.
    *Cela*

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Fibonacci numbers (using class)
    By -chr- in forum C++ Programming
    Replies: 3
    Last Post: 01-21-2009, 03:49 PM
  2. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  3. Fibonacci numbers in C
    By Alastor in forum C Programming
    Replies: 23
    Last Post: 10-10-2005, 01:45 PM
  4. the definition of a mathematical "average" or "mean"
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 7
    Last Post: 12-03-2002, 10:15 AM
  5. FIBONACCI NUMBERS, please help!
    By JamesAnthony23 in forum C Programming
    Replies: 5
    Last Post: 09-26-2002, 03:39 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21