# 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. 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 {
  private cache: Map<number, number | bigint>;
  private lruList: number[]; // Tracks usage order (least recently used at the front)
  private config: Required<FibonacciConfig>;
  private stats: CacheStats;

  constructor(config?: FibonacciConfig);

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

  /**
   * Synchronously calculates Fibonacci of n.
   * Throws warning/error if n is larger than asyncThreshold.
   */
  public calculateSync(n: number): number | bigint;

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

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

  /**
   * Private helper implementing iterative Fibonacci sequence.
   */
  private computeIterative(n: number, isBigInt: boolean): number | 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 Error: Invalid Input]
    B -- Yes --> D{Check Cache for n}
    D -- Hit (Yes) --> E[Update LRU Order]
    E --> F[Return Cached Value]
    D -- Miss (No) --> G{Check Precision Mode: n > 78 or useBigInt}
    G -- Standard Number (n <= 78) --> H[Compute using standard arithmetic]
    G -- BigInt (n > 78) --> I{Is n >= asyncThreshold?}
    I -- No (Sync BigInt) --> J[Compute iteratively using BigInt]
    I -- Yes (Async BigInt) --> K[Offload computation to worker thread / chunked loop]
    K --> L[Iterate asynchronously without blocking event loop]
    H --> M[Store Result in Cache]
    J --> M
    L --> M
    M --> N{Cache Size > maxCacheSize?}
    N -- Yes --> O[Evict Least Recently Used entry]
    O --> P[Return Computed Result]
    N -- No --> P
```

---

## 4. Key Implementation Mechanics

### 4.1 LRU Eviction Implementation
To avoid linear scanning for evictions, the cache is backed by:
- A `Map` mapping `n` to the value (either `Number` or `BigInt`).
- A doubly-linked list or ordered array (`lruList`) tracking usage keys. On a cache hit, the key is moved to the end. On a cache insertion, if the map exceeds `maxCacheSize`, the key at the front of `lruList` is deleted from both the list and the map.

### 4.2 Precision Safeguards
- **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 500,000$), calculating Fibonacci in a single synchronous loop blocks the JS single-threaded event loop for several milliseconds. The `MemoizedFibonacci` class handles this via:
- **Chunked execution:** Splitting the loop into chunks of 10,000 iterations and yielding back control using `setImmediate` or `setTimeout(..., 0)` to allow standard event-loop ticks to execute.
- Alternatively, utilizing **Worker Threads** via `node:worker_threads` for CPU offloading in Node.js environments.

---

## 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$) | Automatically truncated using `Math.floor(n)` with a console warning, or throws a `TypeError`. |
| Out of Memory Risk ($n > 1,000,000$) | Rejects promise with a warning about resource exhaustion unless a `force` flag is set. |
| Cache Collision (Standard vs BigInt) | Values in cache are stored with consistent type based on configuration to avoid mixed-type arithmetic downstream. |