Fibonacci\.(rb|c|java|php) и скука

Вечером в голову взъелась мысль самому проверить, настолько ли пхп тормознут, насколько убог. Попутно вышло немножко (пусть и баянно) потестировать производительность ещё кое-чего, решил поделиться результатами с общественностью.
Особенно растекаться мыслью по древу здесь нечего, поэтому изложу тезисно. Первое, что пришло на ум - ряд Фибоначчи. Простой, но ёмкий алгоритм, считать будем 100000-е число.
(реализации могут хромать, писалось на коленке "просто чтобы посмотреть")

Java (1.6.0.14 on Sun):

import java.io.*;
import java.math.BigInteger;
import java.util.Date;

class Fibonacci
{
    public static void main(String args[])
    {
        System.out.println("100000-е число Фибоначчи");
        long start_time = System.currentTimeMillis();
        fibonacci(100000);
        long end_time = System.currentTimeMillis();
        System.out.println("Время выполнения:" + (end_time - start_time));
    }

    public static void fibonacci(int n)
    {
        BigInteger a = BigInteger.valueOf(0);
        BigInteger b = BigInteger.valueOf(1);

        for (int i=0; i<n; i++) {
            a = a.add(b);
            b = a.subtract(b);
        }
        System.out.println(a.toString());
    }
}

"Чистое" время выполнения ~2.35c - надо учитывать, что сюда же входит время на загрузку виртуальной машины. Впрочем, учитывая, что библиотек импортируется минимум - основное время всё же тратится на цикл. В код включён замер времени выполнения самого цикла, отдаётся чистое количество миллисекунд (которое я ночью так и не раскурил).

Следующий пример - на ruby (1.8.7p72):

class FibonacciRb
  def self.main
    #puts "Num of seq:\n"
    puts "100000-е число Фибоначчи"
    n = 100000 #STDIN.readline.to_i
    fibonacci(n)
  end

  def self.fibonacci(n)
    starttime = Time.now.to_f
    a, b = 0, 1
    n.times do
      a, b = b, a + b
    end
    exectime = Time.now.to_f - starttime
    printf("%d\n", a)
    printf("Время выполнения: %.2fs\n", exectime)
  end
end
FibonacciRb.main()

Время вышло около 0.9с - один из лучших результатов на сегодня. Реализация jruby 1.3 (аналог ruby 1.8.6p287) выполнялся примерно на одну секунду с небольшим быстрее - 1.9-2.2. Скомпилированный javac класс опережает его не больше чем на 10мс.

Один из самых быстрых, но кошмарных результатов показал php. Встроенные средства или библиотеки не дают возможности работать с такими большими числами, поэтому был взят Math_BigInteger из Pear-а (не обновлявшийся уже несколько лет):

<?php
include('Math/BigInteger.php');

echo("100000-е число Фибоначчи:\n");

$n = 10000;

$a = new Math_BigInteger(0);
$b = new Math_BigInteger(1);

for ($i=0;$i<$n;$i++) {
    $a = $a->add($b);
    $b = $a->subtract($b);
}
echo($a->toString());

Даже в такой реализации PHP осилил всего 2090 целочисленных регистров (из 20899) за 0.9 секунды (дальше валится). Искать ещё-одну-костыльную-реализацию BigInteger меня заломало, хотя может быть и есть что-то работающее.

Несмотря на всё, наибольшую скорость показал (сюрприз, ага) ANSI C. Скомпилированный gcc с параметрами -O3 исполняемый файл посчитал искомое число всего за 0.3 секунды. Собственно, как нормальный макроассемблер С не умеет "из коробки" работать с 20000-значными числами, и для целей поддержки этого был беззастенчиво использован GNU MP.

#include <stdio.h>
#include <gmp.h>

int fibonacci(int n);

int main()
{
    int n;
    printf("100000-е число Фибоначчи:\n");
    n = 100000;
    fibonacci(n);
    return 0;
}

int fibonacci(int n)
{
    int i;
    mpz_t a, b;
    mpz_init(a);
    mpz_init(b);
    mpz_set_ui(a, 0);
    mpz_set_ui(b, 1);
    for (i = 0; i < n; i++) {
        mpz_add(a, a, b);
        mpz_add(b, a, b);
    }
    gmp_printf("%Zd\n", a);
    mpz_clear(a);
    mpz_clear(b);
    return 0;
}

Все эксперименты (в оконцовке) проводились на Ubuntu 9.04 x86-64, проц AMD Athlon 64 1.8GHz, 3Gb RAM (хотя все сырцы, кроме сишных, написаны и опробованы на ходу в метро на EeePC 900 =) ).

Upd.: Да, я понимаю, что можно запилить целую кучу всего, чтобы каждая из реализаций работала ещё быстрее.

Upd.2: В комментарии было предложено реализовать варианты с использованием рекурсивного алгоритма. Да, в идеале он выглядит логичней и компактней, но... Попробуйте сами ;) Результата на ruby (1.8-1.9, jruby) я не дождался даже для 1000-го числа, 100-е за нормальное время посчитали только ruby 1.9 и (как ни странно) jruby (даже в режиме 1.8).
Всё остальное у меня валилось stack level too deep (что неудивительно, если рассчитать сложность алгоритма и количество рекурсий).

Upd.3: Камрад Денис из Уфы прислал "плоский вариант" на python:

def fibiter(a):
        i = 0
        j = 1
        count = 1
        while count < a:
                j = i + j
                i = j - i
                count = count + 1
        return j
print fibiter(100000)

(Блоки отступами - это полный вынос мозга)

Ну и напоследок - самый быстрый и "красивый" вариант, разумеется на Сях, и разумеется "читерский" :-) *барабанная дробь* Миллиардное число Фибоначчи! Рекомендую перенаправить вывод в файл, потому что число выйдет в длину около 200 мегабайтов.

#include <stdio.h>
#include <gmp.h>

int main()
{
    printf("100000-е число Фибоначчи:\n");
    mpz_t n;
    mpz_init(n);
    mpz_fib_ui(n, 1000000000);
    gmp_printf("%Zd\n", n);
    mpz_clear(n);
    return 0;
}