Unfortunately, the basic idea I came up with turned out to be the same as x0x7 (computation using multiplication). But, it seems that Rust with rug is quite a bit faster than Ruby. So, I was able to reach 100M within 2.87 seconds on my machine. I did come up with an optimization for the second round to reduce the amount of Fibonacci numbers computed. Instead of the half points, the closest power of 2 is used as a reference point. In my testing, this brought the time down from 14.89 to 8.95 seconds. At that point, printing 20MB to the terminal already takes a long time, so I did my tests with stdout redirected.

I didn't use AI/LLM tools.

Code:

use std::fs;
use std::collections::HashMap;

type MyBigUInt = rug::Integer;

pub struct Fib {
    // Cache to hold already computed results
    cache : HashMap<u64, MyBigUInt>,
}

fn bconst(val: u64) -> MyBigUInt {
    MyBigUInt::from(val)
}

impl Fib {

    pub fn new() -> Self {
        return Self {cache : HashMap::new()}
    }

    // Compute sum of fibonacci nubers
    pub fn compute_sum(numbers_in : Vec<u64>) -> MyBigUInt
    {
        let mut inst = Self::new();
        let mut sum :MyBigUInt = bconst(0);
        for number in numbers_in {
            sum += inst.compute(number);
        }

        return sum;
    }

    // Compute fibonacci number recursively and with caching
    pub fn compute(&mut self, number_in : u64) -> MyBigUInt
    {
        // Handle 0, 1, ...
        if number_in <= 4 {
            return MyBigUInt::from(match number_in {
                0 => 0u32,
                1 => 1u32,
                2 => 1u32,
                3 => 2u32,
                4 => 3u32,
                _ => panic!("not reachable"),
            });
        }

        if self.cache.contains_key(&number_in) { return self.cache[&number_in].clone(); }

        let upper = 1 << (number_in-1).ilog2(); // Largest power of 2 smaller than number_in
        let lower = number_in - upper;

        // F[l+u] = F[u-1] * F[l] + F[u] * F[l+1]

        // Compute recursively
        let f_lower = self.compute(lower);
        let f_lowerp1 = self.compute(lower+1);
        let f_upper = self.compute(upper);
        let f_upperm1 = self.compute(upper-1);

        let res = f_upperm1 * f_lower + f_upper * f_lowerp1;
        self.cache.insert(number_in, res.clone());
        return res;
    }
    
}

fn main() {

    // Read input file
    let file_path = "input.list";
    let contents = fs::read_to_string(file_path).expect("Unable to read input file");

    // Parse lines to integers
    let mut numbers_in : Vec<u64> = Vec::new();
    for line in contents.lines() {
        let trimmed = line.trim();
        if !trimmed.is_empty() {         
            match trimmed.parse::<u64>() {
                Ok(val) => numbers_in.push(val),
                Err(..) => println!("Input line is not an integer: {}", trimmed),
            };   
        }
    }

    // Compute sum
    let sum = Fib::compute_sum(numbers_in).to_string();

    // Print sum
    println!("{sum}");
}

Cargo.toml:

[package]
name = "fibonacci"
version = "0.1.0"
edition = "2024"

[dependencies]
rug = "1.30.0"

#!/usr/bin/ruby

def fib(a)
 return a if a<2 
 fib(a-1)+fib(a-2)
end

def fibN(a,memo={})
 return fib(a) if a<4 
 n=a/2
 memo[a] ||= fibN(n+1,memo)*fibN(a-n,memo)+fibN(n,memo)*fibN(a-n-1,memo)
end

puts(File.readlines('input.list').map(){|i| i.to_i}.reduce(0){|acc,num| acc+fibN(num)}.to_s)