Это еще одна проблема, связанная с числами Фибоначчи.

Цель состоит в том, чтобы как можно быстрее вычислить 20'000'000- ^е число Фибоначчи. Десятичный вывод составляет около 4 МБ; начинается с:

28543982899108793710435526490684533031144309848579

Сумма MD5 на выходе равна

fa831ff5dd57a830792d8ded4c24c2cb

Вы должны отправить программу, которая вычисляет число во время работы и помещает результат в stdout. Самая быстрая программа, измеренная на моей машине, побеждает.

Вот несколько дополнительных правил:

• Вы должны предоставить исходный код и исполняемый двоичный файл на Linux x64
• Исходный код должен быть короче 1 МБ, в случае сборки также допустимо, если только двоичный файл настолько мал.
• Вы не должны включать число для вычисления в вашем двоичном файле, даже в замаскированном виде. Число должно быть рассчитано во время выполнения.
• Мой компьютер имеет два ядра; вам разрешено использовать параллелизм

Я взял небольшую реализацию из Интернета, которая работает около 4,5 секунд. Это не должно быть очень сложно, если у вас есть хороший алгоритм.

C с GMP, 3,6 с

Боги, но GMP делает код ужасным. С помощью трюка в стиле Карацубы мне удалось сократить 2 умножения за шаг удвоения. Теперь, когда я читаю решение FUZxxl, я не первый, кто понял эту идею. У меня есть еще пара трюков в рукаве ... может быть, я попробую их позже.

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

#define DBL mpz_mul_2exp(u,a,1);mpz_mul_2exp(v,b,1);mpz_add(u,u,b);mpz_sub(v,a,v);mpz_mul(b,u,b);mpz_mul(a,v,a);mpz_add(a,b,a);
#define ADD mpz_add(a,a,b);mpz_swap(a,b);

int main(){
    mpz_t a,b,u,v;
    mpz_init(a);mpz_set_ui(a,0);
    mpz_init(b);mpz_set_ui(b,1);
    mpz_init(u);
    mpz_init(v);

    DBL
    DBL
    DBL ADD
    DBL ADD
    DBL
    DBL
    DBL
    DBL ADD
    DBL
    DBL
    DBL ADD
    DBL
    DBL ADD
    DBL ADD
    DBL
    DBL ADD
    DBL
    DBL
    DBL
    DBL
    DBL
    DBL
    DBL
    DBL /*Comment this line out for F(10M)*/

    mpz_out_str(stdout,10,b);
    printf("\n");
}

Построен с gcc -O3 m.c -o m -lgmp.

шалфей

Хм, вы, похоже, предполагаете, что самой быстрой будет скомпилированная программа. Нет бинарных для вас!

print fibonacci(2000000)

На моей машине это занимает 0,10 секунды, 0,15 секунды.

редактировать: приурочен к консоли, а не к ноутбуку

Haskell

Это моя собственная попытка, хотя я сам не написал алгоритм. Я скорее скопировал его с haskell.org и адаптировал для использования Data.Vectorс его знаменитым потоковым синтезом:

import Data.Vector as V
import Data.Bits

main :: IO ()
main = print $ fib 20000000

fib :: Int -> Integer
fib n = snd . V.foldl' fib' (1,0) . V.dropWhile not $ V.map (testBit n) $ V.enumFromStepN (s-1) (-1) s
    where
        s = bitSize n
        fib' (f,g) p
            | p         = (f*(f+2*g),ss)
            | otherwise = (ss,g*(2*f-g))
            where ss = f*f+g*g

Это занимает около 4,5 секунд при компиляции с GHC 7.0.3 и следующими флагами:

ghc -O3 -fllvm fib.hs

КОРОВА

 MoO moO MoO mOo MOO OOM MMM moO moO
 MMM mOo mOo moO MMM mOo MMM moO moO
 MOO MOo mOo MoO moO moo mOo mOo moo

Moo! (Занимает какое-то время. Выпей молока ...)

Mathematica, интерпретируется:

First@Timing[Fibonacci[2 10^6]]

Timed:

0.032 secs on my poor man's laptop.

И, конечно же, нет двоичного файла.

Ocaml, 0,856 с на моем ноутбуке

Требуется библиотека зарита. Я использовал Big_int, но это собака медленная по сравнению с Зарит. Прошло 10 минут с тем же кодом! Большая часть времени была потрачена на печать чертового номера (9,5 минут или около того)!

module M = Map.Make
  (struct
    type t = int
    let compare = compare
   end)

let double b = Z.shift_left b 1
let ( +. ) b1 b2 = Z.add b1 b2
let ( *. ) b1 b2 = Z.mul b1 b2

let cache = ref M.empty 
let rec fib_log n =
  if n = 0
  then Z.zero
  else if n = 1
  then Z.one
  else if n mod 2 = 0
  then
    let f_n_half = fib_log_cached (n/2)
    and f_n_half_minus_one = fib_log_cached (n/2-1)
    in f_n_half *. (f_n_half +. double f_n_half_minus_one)
  else
    let f_n_half = fib_log_cached (n/2)
    and f_n_half_plus_one = fib_log_cached (n/2+1)
    in (f_n_half *. f_n_half) +.
    (f_n_half_plus_one *. f_n_half_plus_one)
and fib_log_cached n =
    try M.find n !cache
    with Not_found ->
      let res = fib_log n
      in cache := M.add n res !cache;
      res

let () =
  let res = fib_log 20_000_000 in
  Z.print res; print_newline ()

Я не могу поверить, как много изменила библиотека!

Haskell

В моей системе это работает почти так же быстро, как ответ FUZxxl (~ 18 секунд вместо ~ 17 секунд).

main = print $ fst $ fib2 20000000

-- | fib2: Compute (fib n, fib (n+1)).
--
-- Having two adjacent Fibonacci numbers lets us
-- traverse up or down the series efficiently.
fib2 :: Int -> (Integer, Integer)

-- Guard against negative n.
fib2 n | n < 0 = error "fib2: negative index"

-- Start with a few base cases.
fib2 0 = (0, 1)
fib2 1 = (1, 1)
fib2 2 = (1, 2)
fib2 3 = (2, 3)

-- For larger numbers, derive fib2 n from fib2 (n `div` 2)
-- This takes advantage of the following identity:
--
--    fib(n) = fib(k)*fib(n-k-1) + fib(k+1)*fib(n-k)
--             where n > k
--               and k ≥ 0.
--
fib2 n =
    let (a, b) = fib2 (n `div` 2)
     in if even n
        then ((b-a)*a + a*b, a*a + b*b)
        else (a*a + b*b, a*b + b*(a+b))

С, наивный алгоритм

Было любопытно, и я не использовал gmp раньше ... так:

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

int main(int argc, char *argv[]){
    int n = (argc>1)?atoi(argv[1]):0;

    mpz_t temp,prev,result;
    mpz_init(temp);
    mpz_init_set_ui(prev, 0);
    mpz_init_set_ui(result, 1);

    for(int i = 2; i <= n; i++) {
        mpz_add(temp, result, prev);
        mpz_swap(temp, result);
        mpz_swap(temp, prev);
    }

    printf("fib(%d) = %s\n", n, mpz_get_str (NULL, 10, result));

    return 0;
}

fib (1 миллион) занимает около 7 секунд ... так что этот алгоритм не выиграет гонку.

Я реализовал метод умножения матриц (из sicp, http://sicp.org.ua/sicp/Exercise1-19 ) в SBCL, но для его завершения требуется около 30 секунд. Я перенес его на C, используя GMP, и он возвращает правильный результат примерно за 1,36 секунды на моей машине. Это примерно так же быстро, как ответ Бутби.

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

int main()
{
  int n = 20000000;

  mpz_t a, b, p, q, psq, qsq, twopq, bq, aq, ap, bp;
  int count = n;

  mpz_init_set_si(a, 1);
  mpz_init_set_si(b, 0);
  mpz_init_set_si(p, 0);
  mpz_init_set_si(q, 1);
  mpz_init(psq);
  mpz_init(qsq);
  mpz_init(twopq);
  mpz_init(bq);
  mpz_init(aq);
  mpz_init(ap);
  mpz_init(bp);

  while(count > 0)
    {
      if ((count % 2) == 0)
        {
          mpz_mul(psq, p, p);
          mpz_mul(qsq, q, q);
          mpz_mul(twopq, p, q);
          mpz_mul_si(twopq, twopq, 2);

          mpz_add(p, psq, qsq);    // p -> (p * p) + (q * q)
          mpz_add(q, twopq, qsq);  // q -> (2 * p * q) + (q * q) 
          count/=2;
        }

      else
       {
          mpz_mul(bq, b, q);
          mpz_mul(aq, a, q);
          mpz_mul(ap, a, p);
          mpz_mul(bp, b, p);

          mpz_add(a, bq, aq);      // a -> (b * q) + (a * q)
          mpz_add(a, a, ap);       //              + (a * p)

          mpz_add(b, bp, aq);      // b -> (b * p) + (a * q)

          count--;
       }

    }

  gmp_printf("%Zd\n", b);
  return 0;
}

Java: 8 секунд для вычисления, 18 секунд для записи

public static BigInteger fibonacci1(int n) {
    if (n < 0) explode("non-negative please");
    short charPos = 32;
    boolean[] buf = new boolean[32];
    do {
        buf[--charPos] = (n & 1) == 1;
        n >>>= 1;
    } while (n != 0);
    BigInteger a = BigInteger.ZERO;
    BigInteger b = BigInteger.ONE;
    BigInteger temp;
    do {
        if (buf[charPos++]) {
            temp = b.multiply(b).add(a.multiply(a));
            b = b.multiply(a.shiftLeft(1).add(b));
            a = temp;
        } else {
            temp = b.multiply(b).add(a.multiply(a));
            a = a.multiply(b.shiftLeft(1).subtract(a));
            b = temp;
        }
    } while (charPos < 32);
    return a;
}

public static void main(String[] args) {
    BigInteger f;
    f = fibonacci1(20000000);
    // about 8 seconds
    System.out.println(f.toString());
    // about 18 seconds
}

Идти

Это смущающе медленно. На моем компьютере это занимает чуть меньше 3 минут. Впрочем, это всего лишь 120 рекурсивных вызовов (после добавления кеша). Обратите внимание, что для этого может потребоваться много памяти (например, 1,4 ГБ)!

package main

import (
    "math/big"
    "fmt"
)

var cache = make(map[int64] *big.Int)

func fib_log_cache(n int64) *big.Int {
    if res, ok := cache[n]; ok {
        return res
    }
    res := fib_log(n)
    cache[n] = res
    return res
}

func fib_log(n int64) *big.Int {
    if n <= 1 {
        return big.NewInt(n)
    }

    if n % 2 == 0 {
        f_n_half := fib_log_cache(n/2)
        f_n_half_minus_one := fib_log_cache(n/2-1)
        res := new(big.Int).Lsh(f_n_half_minus_one, 1)
        res.Add(f_n_half, res)
        res.Mul(f_n_half, res)
        return res
    }
    f_n_half := fib_log_cache(n/2)
    f_n_half_plus_one := fib_log_cache(n/2+1)
    res := new(big.Int).Mul(f_n_half_plus_one, f_n_half_plus_one)
    tmp := new(big.Int).Mul(f_n_half, f_n_half)
    res.Add(res, tmp)
    return res
}

func main() {
    fmt.Println(fib_log(20000000))
}

псевдокод (я не знаю, что вы, ребята, используете)

product = 1
multiplier = 3 // 3 is fibonacci sequence, but this can be any number, 
      // generating an infinite amount of sequences
y = 28 // the 2^x-1 term, so 2^28-1=1,284,455,535th term
for (int i = 1; int < y; i++) {
  product= sum*multiplier-1
  multiplier= multiplier^2-2
}
multiplier=multiplier-product // 2^28+1 1,284,455,537th 

Моему компьютеру потребовалось 56 часов, чтобы выполнить эти два условия. Мой компьютер отчасти дерьмовый. У меня будет номер в текстовом файле 22 октября. 1,2 гига немного больше, чтобы поделиться на моем соединении.