fibonacci series


See On Github

Data

Tags

recursion

Source Code

//
//  Fibonacci.h
//  Algorithms
//
//  Created by intoxicated on 1/4/14.
//  Copyright (c) 2014 intoxicated. All rights reserved.
//

#import <Foundation/Foundation.h>

@interface Fibonacci : NSObject

+ (id)initFibWith:(NSInteger)size;

- (void)resetWithSize:(NSInteger)size;

- (long)recursive:(NSInteger)nth;
- (long)memorization:(NSInteger)nth;
- (long)iter1:(NSInteger)nth;
- (long)iter2:(NSInteger)nth;

@end
//
//  Fibonacci.m
//  Algorithms
//
//  Created by intoxicated on 1/4/14.
//  Copyright (c) 2014 intoxicated. All rights reserved.
//

#import "Fibonacci.h"

#define integer(x) [NSNumber numberWithLong:x]

static Fibonacci * instance;

@interface Fibonacci ()
@property (nonatomic, strong) NSMutableArray * array;
@end

@implementation Fibonacci

+ (id)initFibWith:(NSInteger)size
{
    @synchronized(self)
    {
        if (instance == NULL){
            instance = [[self alloc] init];
            instance.array = [[NSMutableArray alloc] initWithCapacity:size+1];
            for(int i = 0; i < size+1; i++)
                [instance.array addObject:[NSNull null]];
        }
    }
    
    return instance;
}

- (void)resetWithSize:(NSInteger)size
{
    instance.array = [[NSMutableArray alloc] initWithCapacity:size+1];
    for(int i = 0; i < size+1; i++)
        [instance.array addObject:[NSNull null]];
}

/**
 * Basic recursive Fibonnacci nth number
 * O(n!)
 */
- (long)recursive:(NSInteger)nth
{
    if(nth < 2)
        return nth;
    return [self recursive:nth-1] + [self recursive:nth-2];
}

/**
 * Improved recursive Fibonacci by memorizing
 * perform O(n) additions
 */
- (long)memorization:(NSInteger)nth
{
    if(nth < 2)
        return nth;
    else
    {
        if([instance.array objectAtIndex:nth] == [NSNull null])
        {
            [instance.array insertObject:integer([self memorization:nth-1] + [self memorization:nth-2])
                          atIndex:nth];
        }
        return [[instance.array objectAtIndex:nth] integerValue];
    }
}

/**
 * Same as above but savin some space by using dynamic programming
 * running O(n) space O(n)
 */
- (long)iter1:(NSInteger)nth
{
    [instance.array replaceObjectAtIndex:0 withObject:integer(0)];
    [instance.array replaceObjectAtIndex:1 withObject:integer(1)];
    
    for(int i = 2; i <= nth; ++i)
    {
        [instance.array replaceObjectAtIndex:i withObject:
         integer([[instance.array objectAtIndex:i-1] integerValue] +
                 [[instance.array objectAtIndex:i-2] integerValue])];
    }
    return [[instance.array objectAtIndex:nth] integerValue];
}

/**
 * This one only requires to remember previous two number to get
 * next fibonacci number
 * running O(n) space O(1)
 */
- (long)iter2:(NSInteger)nth
{
    NSInteger prev = 1;
    NSInteger curr = 0;
    NSInteger next;
    for(int i = 1; i <= nth; i++)
    {
        next = curr + prev;
        prev = curr;
        curr = next;
    }
    return curr;
}


@end
//
//  main.m
//  Fibonacci
//
//  Created by intoxicated on 1/4/14.
//  Copyright (c) 2014 intoxicated. All rights reserved.
//

#import <Foundation/Foundation.h>
#import "Fibonacci.h"

#define SIZE 15 //change this to see difference
                //first recursive method would take much longer if size exceeds 45

#define RESET(obj) [obj resetWithSize:SIZE];

int main(int argc, const char * argv[])
{
    @autoreleasepool {
        Fibonacci * test = [Fibonacci initFibWith:SIZE];
        
        NSDate *methodStart = [NSDate date];
        NSLog(@"Recursive %d th Fibonacci: %lu", SIZE,[test recursive:SIZE]);
        NSDate *methodFinish = [NSDate date];
        NSTimeInterval executionTime = [methodFinish timeIntervalSinceDate:methodStart];
        NSLog(@"Execution Time = %f", executionTime);
        
        RESET(test);
        
        methodStart = [NSDate date];
        NSLog(@"Memorized Recursive %dth Fibonacci: %lu", SIZE, [test memorization:SIZE]);
        methodFinish = [NSDate date];
        executionTime = [methodFinish timeIntervalSinceDate:methodStart];
        NSLog(@"Execution Time = %f", executionTime);
        
        RESET(test);

        methodStart = [NSDate date];
        NSLog(@"Speed up more! %dth Fibonacci: %lu", SIZE, [test iter1:SIZE]);
        methodFinish = [NSDate date];
        executionTime = [methodFinish timeIntervalSinceDate:methodStart];
        NSLog(@"Execution Time = %f", executionTime);
        
        RESET(test);
        
        methodStart = [NSDate date];
        NSLog(@"FASTER! %dth Fibonacci: %lu", SIZE, [test iter2:SIZE]);
        methodFinish = [NSDate date];
        executionTime = [methodFinish timeIntervalSinceDate:methodStart];
        NSLog(@"Execution Time = %f", executionTime);
        
        
        
    }
    return 0;
}