Create an optimal Fibonacci function in TS.
- User
Create an optimal Fibonacci function in TS.
- 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:
-
Type Safety:
- Uses TypeScript's type system to ensure input and output are numbers
- Proper error handling with typed errors
-
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
-
Error Handling:
- Validates input for negative numbers
- Uses try-catch blocks in the wrapper function
-
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:
-
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
-
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
-
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):
-
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)
-
Matrix Exponentiation:
- For extremely large n, you could implement matrix exponentiation to achieve O(log n) time complexity
-
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.
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.