Advanced Distance Conversion Using Fibonacci Mathematics

A sophisticated command-line utility converting miles to kilometers using the mathematical properties of the Fibonacci sequence and the golden ratio.

View on GitHub Get Started

Project Overview

An educational demonstration of mathematical concepts applied to practical computation problems

Mathematical Insight

The project leverages the proximity between the golden ratio (φ ≈ 1.618034) and the exact miles-to-kilometers conversion factor (1.609344).

Relative error: ~0.54%

Algorithmic Approaches

Three distinct implementations explore computational strategies: iterative Fibonacci with interpolation, cached Fibonacci conversion, and golden ratio conversion.

O(1) to O(log φ(n)) complexity

Systems Programming

Built with C for performance and low-level control, with careful attention to error handling, integer overflow protection, and floating-point precision.

POSIX-style CLI parser

Golden Ratio Spiral

Conversion Error Distribution

Mathematical Foundations

Connecting abstract mathematics to practical computation

Fibonacci Sequence

F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2 for n ≥ 2

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,...

Golden Ratio

φ = lim (n→∞) Fn+1/Fn = (1 + √5)/2 ≈ 1.618034

Binet's Formula

Fn = (φn - (-φ)-n) / √5

Conversion Relationship

1 mile = 1.609344 kilometers

Relative error:
(φ - 1.609344) / 1.609344 × 100% ≈ 0.54%

Linear Interpolation

km = Fk+1 + (miles - Fk) ×
(Fk+2 - Fk+1) / (Fk+1 - Fk)

Error Propagation

εrel = |(Fk+1/Fk - φ) + (φ - 1.609344)/1.609344|

Algorithmic Implementations

Three distinct approaches with unique computational characteristics

$ cat algorithms.c

// Iterative Fibonacci with Interpolation
float fib_interpolate(float miles) {
  if (miles < 5.0f) return basic_miles2km(miles);

  uint64_t prev_mile = 0; // F₀
  uint64_t prev_km = 1; // F₁
  uint64_t curr_mile = 1; // F₁
  uint64_t curr_km = 1; // F₂

  while (curr_mile <= miles) {
    uint64_t next_mile = curr_km;
    uint64_t next_km = prev_km + curr_km;

    if (next_km < curr_km) break; // Overflow protection

    prev_mile = curr_mile;
    prev_km = curr_km;
    curr_mile = next_mile;
    curr_km = next_km;
  }

  return prev_km + (miles - prev_mile) *
         ((float)(curr_km - prev_km) / (curr_mile - prev_mile));
}
1

Fibonacci Sequence Generation

Compute Fibonacci pairs until current mile value exceeds input

F₀=0
F₁=1
F₂=1
F₃=2
F₄=3
F₅=5
F₆=8
F₇=13
F₈=21
2

Interval Identification

Locate the Fibonacci pair bracketing the input value

Fₖ=5
Input=10
Fₖ₊₁=13
3

Linear Interpolation

Calculate the proportional distance between Fibonacci points

Fₖ=5
Fₖ₊₁=13
Fₖ₊₁=8
Fₖ₊₂=21
km = 8 + (10-5) × (21-8)/(13-5) ≈ 16.125

Iterative Fibonacci

Dynamically computes Fibonacci numbers until bracketing the input value. Uses 64-bit integers for precision with overflow protection.

Time: O(log φ(miles)) | Space: O(1)

Key Insight: As n increases, the ratio Fn+1/Fn approaches φ, enabling approximation.

Cached Conversion

Precomputes Fibonacci numbers up to F₉₃ (max before 64-bit overflow). Uses static cache for single initialization with constant-time lookup.

Time: O(1) | Space: O(94)

Optimization: Cache is initialized on first function call, minimizing startup overhead.

Golden Ratio

Direct implementation of Binet's closed-form formula. Uses logarithmic calculation to find Fibonacci index with floating-point precision.

Time: O(1) | Space: O(1)

Precision Note: Double precision maintains accuracy until ~F₇₀ (1e14 miles).

Command-Line Interface

POSIX-style option processing with conflict detection and validation

$ ./fib_miles2km --help
Advanced distance converter: miles to kilometers
Usage: ./fib_miles2km [OPTIONS] [distance]

Options:
-h, --help Show help information
-f, --fib=ARG Convert using basic Fibonacci
-b, --basic=ARG Convert using standard formula
-i, --fib-interp=ARG Convert using Fibonacci interpolation
-c, --fib-cache=ARG Convert using cached Fibonacci
-g, --fib-golden=ARG Convert using golden ratio

$ ./fib_miles2km --fib-interp 21
21.00 miles ≈ 34.00 km (Fibonacci interpolation)

$ ./fib_miles2km --fib-golden 55.3
55.30 miles ≈ 89.11 km (Golden Ratio)

$ ./fib_miles2km 100
100.00 miles = 160.93 km

Parser Architecture

The command parser implements a robust POSIX-style option processing system with:

  • Conflict detection between conversion methods
  • Input validation for distance values
  • Comprehensive error reporting
  • Default fallback to standard conversion

Error Handling

Comprehensive checks include:

  • Invalid numeric inputs
  • Negative distance values
  • Conflicting conversion methods
  • Integer overflow protection
  • Floating-point underflow/overflow

Performance Characteristics

Algorithm selection tradeoffs for different use cases

Method Time Complexity Space Complexity Max Input (miles) Precision Use Case
Basic O(1) O(1) ∞ Exact General purpose
Interpolation O(log φ(n)) O(1) F₉₂ ≈ 7.5e19 ~0.54% error Mathematical demonstration
Cached O(1) O(94) F₉₂ ≈ 7.5e19 ~0.54% error Repeated conversions
Golden Ratio O(1) O(1) ∞ Degrades with n Large values (> F₉₂)

Time Efficiency

Golden Ratio: 100%
Cached: 98%
Basic: 95%
Interpolation: 85%

Memory Efficiency

Golden Ratio: 100%
Basic: 100%
Interpolation: 95%
Cached: 90%

Precision

Basic: 100%
Cached: 99.46%
Interpolation: 99.46%
Golden Ratio: 98%

Limitations

  • Golden ratio precision limited by double-precision floating point (53-bit mantissa)
  • Maximum input F₉₃ ≈ 7.5e19 miles for integer-based methods
  • Linear interpolation assumes constant ratio between Fibonacci points
  • No SIMD or multi-threading optimization

Future Work

  • Arbitrary-precision arithmetic using GMP
  • Hybrid algorithmic approaches combining methods
  • Error correction with machine learning models
  • WebAssembly port for browser execution
  • Formal error distribution analysis
  • AVX-512 vectorization for cache initialization