Skip to content
TheChatArchiveThe Chat Archive
grok-3-preview-02-24· xAIHugging Face LMArena Human Preference 140K

Create an optimal Fibonacci function in TS.

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Claudeclaude-opus-4-20250514’s answer.
  1. User

    Create an optimal Fibonacci function in TS.

  2. Assistant

    Here's an optimized Fibonacci function in TypeScript that uses memoization to achieve O(n) time complexity while maintaining readability and type safety. I'll provide multiple implementations with different optimization techniques, and explain their trade-offs.

    // 1. Memoized Recursive Solution (Dynamic Programming)
    // Best for general use cases with good performance and readability
    function fibonacciMemo(n: number, memo: Map<number, number> = new Map()): number {
        // Handle negative numbers
        if (n < 0) throw new Error('Input must be a non-negative number');
        
        // Base cases
        if (n <= 1) return n;
        
        // Check if we've already calculated this value
        if (memo.has(n)) return memo.get(n)!;
        
        // Calculate and store the result
        const result = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
        memo.set(n, result);
        return result;
    }
    
    // 2. Iterative Solution
    // Most efficient in terms of space complexity O(1)
    function fibonacciIterative(n: number): number {
        // Handle negative numbers
        if (n < 0) throw new Error('Input must be a non-negative number');
        
        // Base cases
        if (n <= 1) return n;
        
        let prev = 0;
        let current = 1;
        
        for (let i = 2; i <= n; i++) {
            const next = prev + current;
            prev = current;
            current = next;
        }
        
        return current;
    }
    
    // 3. Closure-based Memoization
    // Good for repeated calls without passing memo around
    const fibonacciClosure = (() => {
        const memo: Map<number, number> = new Map();
        
        return function fib(n: number): number {
            if (n < 0) throw new Error('Input must be a non-negative number');
            if (n <= 1) return n;
            if (memo.has(n)) return memo.get(n)!;
            
            const result = fib(n - 1) + fib(n - 2);
            memo.set(n, result);
            return result;
        };
    })();
    
    // Usage examples with error handling
    function calculateFibonacci(n: number): number {
        try {
            console.log(`Calculating Fibonacci(${n})...`);
            
            // Choose implementation based on use case
            // const result = fibonacciMemo(n);        // For one-off calculations
            // const result = fibonacciIterative(n);   // For space efficiency
            const result = fibonacciClosure(n);     // For repeated calculations
            
            return result;
        } catch (error) {
            console.error(`Error: ${(error as Error).message}`);
            return -1;
        }
    }
    
    // Test the functions
    console.log(calculateFibonacci(0));  // 0
    console.log(calculateFibonacci(1));  // 1
    console.log(calculateFibonacci(5));  // 5
    console.log(calculateFibonacci(10)); // 55
    console.log(calculateFibonacci(-1)); // Error: Input must be a non-negative number
    
    // Performance test
    function performanceTest() {
        const n = 40;
        console.log('\nPerformance Test for n =', n);
        
        // Test Memoized
        console.time('Memoized');
        const memoResult = fibonacciMemo(n);
        console.timeEnd('Memoized');
        
        // Test Iterative
        console.time('Iterative');
        const iterResult = fibonacciIterative(n);
        console.timeEnd('Iterative');
        
        // Test Closure
        console.time('Closure');
        const closureResult = fibonacciClosure(n);
        console.timeEnd('Closure');
        
        console.log('Results match:', memoResult === iterResult && iterResult === closureResult);
    }
    
    performanceTest();
    

    Key Features and Optimizations:

    1. Type Safety:

      • Uses TypeScript's type system to ensure input and output are numbers
      • Proper error handling with typed errors
    2. Multiple Implementations:

      • Memoized Recursive: Uses dynamic programming with a Map for O(n) time complexity and O(n) space complexity
      • Iterative: Most space-efficient with O(1) space complexity and O(n) time complexity
      • Closure-based: Best for repeated calls as it maintains memoization state between calls
    3. Error Handling:

      • Validates input for negative numbers
      • Uses try-catch blocks in the wrapper function
    4. Performance Considerations:

      • All implementations avoid the naive recursive O(2^n) complexity
      • Memoization prevents recalculating previously computed values
      • Iterative solution minimizes stack space usage

    Trade-offs and When to Use Each:

    1. Memoized Recursive (fibonacciMemo):

      • Pros: Easy to understand, good performance, flexible
      • Cons: Uses O(n) space for memoization
      • Use when: You need a balance between readability and performance for one-off calculations
    2. Iterative (fibonacciIterative):

      • Pros: Most space-efficient, good performance
      • Cons: Slightly less intuitive than recursive solution
      • Use when: Memory usage is a concern or you need the absolute best performance
    3. Closure-based (fibonacciClosure):

      • Pros: Maintains memoization state between calls, good for repeated calculations
      • Cons: Uses O(n) space that persists between calls
      • Use when: You need to calculate multiple Fibonacci numbers repeatedly

    Additional Optimizations (Not Implemented):

    1. BigInt Support:

      • For very large Fibonacci numbers, you could modify the functions to use BigInt to handle numbers beyond JavaScript's safe integer limit (2^53 - 1)
    2. Matrix Exponentiation:

      • For extremely large n, you could implement matrix exponentiation to achieve O(log n) time complexity
    3. Tail Call Optimization:

      • While not supported in JavaScript/TypeScript, you could structure the code to be TCO-friendly for environments that support it

    Running the Code:

    The code includes a performance test that compares the execution time of each implementation. Note that for very large values of n, you might want to add BigInt support to handle the results accurately.

    This implementation provides a good balance of performance, readability, and maintainability while showcasing different optimization techniques for the Fibonacci sequence calculation.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.