# Technical Specification — MemoizedFibonacci

## Revision History

| Version | Date | Author | Description |
| :--- | :--- | :--- | :--- |
| 1.0 | 2026-06-22 | Antigravity Orchestrator | Initial technical design with Mermaid diagram, class architecture, and caching strategy. |
| 1.1 | 2026-06-22 | Antigravity Orchestrator | Refined LRU caching mechanism using ES6 Map insertion ordering. Added explicit detail on Async Slicing and Testing Strategy. |

---

## 1. System Architecture

The `MemoizedFibonacci` feature consists of three primary layers:
1. **API & Interface Layer:** Exposes synchronous and asynchronous methods to users.
2. **LRU Cache Layer:** Manages in-memory storage of computed sequences with automatic eviction based on Least Recently Used patterns.
3. **Computation Engine:** Performs iterative sequence calculations to prevent call stack overflow, handles dynamic upgrading to `BigInt` for large numbers, and schedules asynchronous chunks for heavy inputs.

---

## 2. API Design & Core Interface

```typescript
interface FibonacciConfig {
  maxCacheSize?: number;      // Maximum number of entries in the cache (default: 1000)
  useBigInt?: boolean;        // Force BigInt computation even for small inputs (default: false)
  asyncThreshold?: number;    // Input size to trigger asynchronous execution (default: 50000)
}

interface CacheStats {
  hits: number;
  misses: number;
  size: number;
  evictions: number;
}

class MemoizedFibonacci {
  // Built-in ES6 Map maintains insertion order.
  // By deleting and re-inserting a key on access, the most recently used keys move to the end.
  // The first key in map.keys() represents the Least Recently Used (LRU) element.
  private cache: Map<number, number | bigint>;
  private config: Required<FibonacciConfig>;
  private stats: CacheStats;

  constructor(config?: FibonacciConfig);

  /**
   * Calculates Fibonacci of n. Automatically picks sync/async mode based on threshold.
   * Returns a Promise resolving to number or bigint.
   */
  public calculate(n: number): Promise<number | bigint>;

  /**
   * Synchronously calculates Fibonacci of n.
   * Throws RangeError if n exceeds asyncThreshold to protect the thread.
   */
  public calculateSync(n: number): number | bigint;

  /**
   * Checks if the value for n is currently cached.
   */
  public isCached(n: number): boolean;

  /**
   * Dynamically updates the cache capacity limit. Evicts items if size exceeds new limit.
   */
  public setMaxCacheSize(size: number): void;

  /**
   * Retrieves cache usage statistics.
   */
  public getStats(): CacheStats;

  /**
   * Clears all cache entries and resets statistics.
   */
  public clearCache(): void;

  /**
   * Internal helper implementing iterative computation.
   */
  private computeIterative(n: number, isBigInt: boolean): number | bigint;

  /**
   * Internal helper performing non-blocking chunked computation.
   */
  private computeAsyncChunked(n: number, chunkSize: number): Promise<bigint>;
}
```

---

## 3. Detailed Logic Flow (Mermaid Diagram)

The following diagram illustrates the routing, validation, precision selection, and caching logic:

```mermaid
graph TD
    A[Start: Calculate F(n)] --> B{Validate input n >= 0}
    B -- No --> C[Throw RangeError: Invalid Input]
    B -- Yes --> D{Check Cache for n}
    
    D -- Hit (Yes) --> E[Update Map Insertion Order: Delete & Re-insert]
    E --> F[Increment Hit Metric]
    F --> G[Return Cached Value]
    
    D -- Miss (No) --> H[Increment Miss Metric]
    H --> I{Check Precision Mode: n > 78 or useBigInt}
    
    I -- Standard Number (n <= 78) --> J[Compute iteratively using standard Number]
    I -- BigInt (n > 78) --> K{Is n >= asyncThreshold?}
    
    K -- No (Sync BigInt) --> L[Compute iteratively using BigInt]
    K -- Yes (Async BigInt) --> M[Invoke computeAsyncChunked]
    
    M --> N[Loop in chunks of size 10,000 using setImmediate]
    N --> O[Yield control back to Event Loop after each chunk]
    
    J --> P[Store Result in Cache]
    L --> P
    O --> P
    
    P --> Q{Cache Size > maxCacheSize?}
    Q -- Yes --> R[Evict map.keys.next.value oldest entry]
    R --> S[Increment Eviction Metric]
    S --> T[Return Computed Result]
    Q -- No --> T
```

---

## 4. Key Implementation Mechanics

### 4.1 LRU Eviction Implementation (ES6 Map)
Instead of managing a separate `lruList` array (which incurs $O(N)$ lookup/splice operations), the implementation relies entirely on the ordered property of JavaScript's `Map`.
* **Read (Cache Hit):**
  ```javascript
  const value = this.cache.get(key);
  this.cache.delete(key);
  this.cache.set(key, value); // Re-inserts at the end of the Map
  ```
* **Write (Cache Miss & Capacity Exceeded):**
  ```javascript
  this.cache.set(key, value);
  if (this.cache.size > this.config.maxCacheSize) {
    const oldestKey = this.cache.keys().next().value;
    this.cache.delete(oldestKey); // Deletes the oldest insertion
    this.stats.evictions++;
  }
  ```
This architecture yields highly efficient $O(1)$ operations for both cache lookup and replacement.

### 4.2 Precision Safeguards & Double Limits
- **Standard Float Limits:** Standard numbers in JavaScript lose precision above $F(78)$ ($F(78) = 8944394323791464$, whereas $F(79) = 14472334024559020$ which exceeds `Number.MAX_SAFE_INTEGER`).
- **Automatic BigInt Upgrade:** If the class configuration is not explicitly set, inputs $n \ge 79$ automatically upgrade execution to `BigInt` mode.

### 4.3 Async Slicing / Non-blocking Loop
For large values of $n$ (e.g. $n \ge 100,000$), calculating Fibonacci in a single synchronous loop blocks the JS single-threaded event loop.
We employ a chunked calculation pattern:
```javascript
private async computeAsyncChunked(n: number, chunkSize: number = 10000): Promise<bigint> {
  let prev = 0n;
  let curr = 1n;
  let i = 2;

  const runChunk = (): Promise<bigint> => {
    return new Promise((resolve) => {
      setImmediate(() => {
        const target = Math.min(i + chunkSize, n + 1);
        for (; i < target; i++) {
          const next = prev + curr;
          prev = curr;
          curr = next;
        }
        if (i <= n) {
          resolve(runChunk()); // Recursively queue the next chunk
        } else {
          resolve(curr);
        }
      });
    });
  };

  return runChunk();
}
```

---

## 5. Error Handling & Edge Cases

| Condition | System Response |
| :--- | :--- |
| Negative Input ($n < 0$) | Throws `RangeError: Input must be a non-negative integer.` |
| Floating point Input (e.g., $n = 3.5$) | Throws `TypeError: Input must be an integer.` |
| Maximum Guardrail Breach ($n > 1,000,000$) | Throws `RangeError: Calculation size exceeds maximum guardrail of 1,000,000.` |
| Sync Call beyond Threshold ($n > asyncThreshold$) | Throws `RangeError: Input exceeds asyncThreshold. Use calculate() instead.` |

---

## 6. Testing Strategy

### 6.1 Unit Tests
* **Core Calculations:** Verify $F(0) = 0$, $F(1) = 1$, $F(10) = 55$, and $F(78) = 8944394323791464$.
* **BigInt Accuracy:** Verify $F(79)$ is correctly calculated as `14472334024559020n` (with tailing `n` specifying bigint).
* **Caching Performance:** Retrieve $F(50)$ twice. The second call must trigger a cache hit and have a latency under 1 microsecond.
* **LRU Eviction:** Set cache limit to 3. Populate cache with keys 1, 2, 3. Read key 1 (making it most recently used). Insert key 4. Verify key 2 is evicted.

### 6.2 Performance & Memory Benchmarks
* **Sync vs Async Threshold:** Test the threshold boundary. Verify that calling `calculate(49999)` completes synchronously within milliseconds, and `calculate(50001)` returns a Promise and yields event loop control.
* **Leak Testing:** Execute calculation loop of random values up to $n = 10,000$ for 100,000 iterations. Verify heap memory remains flat (no leakage outside the bounds of `maxCacheSize`).