To kolejne wyzwanie dotyczące liczb Fibonacciego.

Celem jest, aby obliczyć 20'000'000 ^th liczby Fibonacii tak szybko jak to możliwe. Wyjście dziesiętne ma około 4 MiB; zaczyna się od:

28543982899108793710435526490684533031144309848579

Suma MD5 wyniku wynosi

fa831ff5dd57a830792d8ded4c24c2cb

Musisz przesłać program, który oblicza liczbę podczas działania i podaje wynik stdout. Najszybszy program, mierzony na moim komputerze, wygrywa.

Oto kilka dodatkowych zasad:

• Musisz przesłać kod źródłowy i plik binarny do uruchomienia na Linuksie x64
• Kod źródłowy musi być krótszy niż 1 MiB, w przypadku złożenia jest również dopuszczalne, jeśli tylko plik binarny jest tak mały.
• Nie wolno dołączać liczby do obliczenia w pliku binarnym, nawet w przebraniu. Liczbę należy obliczyć w czasie wykonywania.
• Mój komputer ma dwa rdzenie; możesz używać równoległości

Wziąłem małą implementację z Internetu, która działa w około 4,5 sekundy. To nie powinno być trudne do pokonania, zakładając, że masz dobry algorytm.

C z GMP, 3.6s

Bogowie, ale GMP sprawia, że ​​kod jest brzydki. Dzięki sztuczce w stylu Karatsuba udało mi się zmniejszyć do 2 mnożników na krok podwojenia. Teraz, gdy czytam rozwiązanie FUZxxl, nie jestem pierwszym, który wpadł na ten pomysł. Mam jeszcze kilka sztuczek w rękawie ... może spróbuję później.

#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");
}

Zbudowany z gcc -O3 m.c -o m -lgmp.

szałwia

Hmm, wydaje się, że najszybszym będzie skompilowany program. Brak pliku binarnego dla Ciebie!

print fibonacci(2000000)

Na mojej maszynie zajmuje to 0,10 cpu sekundy, 0,15 sekundy ściany.

edit: czas na konsoli, a nie na notebooku

Haskell

To moja własna próba, chociaż sam nie napisałem algorytmu. Raczej skopiowałem go z haskell.org i dostosowałem do Data.Vectorswojej słynnej syntezy strumieniowej:

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

Trwa to około 4,5 sekundy po skompilowaniu z GHC 7.0.3 i następującymi flagami:

ghc -O3 -fllvm fib.hs

KROWA

 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

Muczeć! (Trwa chwilę. Wypij trochę mleka ...)

Matematyka, interpretowana:

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

Tymczasowy:

0.032 secs on my poor man's laptop.

I oczywiście nie ma pliku binarnego.

Ocaml, 0,856s na moim laptopie

Wymaga biblioteki zarith. Użyłem Big_int, ale jest on wolniejszy niż zarith. Ten sam kod zajął 10 minut! Większość czasu spędziłem na drukowaniu tego cholernego numeru (około 9½ minuty)!

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 ()

Nie mogę uwierzyć, jak bardzo zmieniła się biblioteka!

Haskell

W moim systemie działa to prawie tak szybko, jak odpowiedź FUZxxl (~ 18 sekund zamiast ~ 17 sekund).

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))

C, naiwny algorytm

Byłem ciekawy i wcześniej nie korzystałem z gmp ... więc:

#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 milion) zajmuje około 7 sekund ... więc ten algorytm nie wygra wyścigu.

Zaimplementowałem metodę mnożenia macierzy (z sicp, http://sicp.org.ua/sicp/Exercise1-19 ) w SBCL, ale jej ukończenie zajmuje około 30 sekund. Przeniesiłem go do C za pomocą GMP, i zwraca prawidłowy wynik w około 1,36 sekundy na moim komputerze. To prawie tak szybko, jak odpowiedź Boothby'ego.

#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 sekund na obliczenie, 18 sekund na napisanie

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
}

Udać się

Jest zawstydzająco wolny. Na moim komputerze zajmuje to nieco mniej niż 3 minuty. Jednak to tylko 120 połączeń rekurencyjnych (po dodaniu pamięci podręcznej). Pamiętaj, że może to zużywać dużo pamięci (np. 1,4 GiB)!

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))
}

pseudo kod (nie wiem, czego używacie)

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 

Te dwa terminy zajęły mojemu komputerowi 56 godzin. Mój komputer jest trochę gburowaty. Będę miał numer w pliku tekstowym 22 października. 1.2 koncerty są trochę duże do udostępnienia na moim połączeniu.