C'est encore un autre défi concernant les chiffres de Fibonacci.

L'objectif est de calculer le 20'000'000 ^e nombre de Fibonacii le plus rapidement possible. La sortie décimale est d'environ 4 Mio de large; ça commence par:

28543982899108793710435526490684533031144309848579

La somme MD5 de la sortie est

fa831ff5dd57a830792d8ded4c24c2cb

Vous devez soumettre un programme qui calcule le nombre lors de l'exécution et met le résultat à stdout. Le programme le plus rapide, mesuré sur ma propre machine, gagne.

Voici quelques règles supplémentaires:

• Vous devez soumettre le code source et un exécutable binaire sur un Linux x64
• Le code source doit être inférieur à 1 Mio, en cas d'assemblage, il est également acceptable si seul le binaire est aussi petit.
• Vous ne devez pas inclure le nombre à calculer dans votre binaire, même de manière déguisée. Le nombre doit être calculé lors de l'exécution.
• Mon ordinateur a deux cœurs; vous êtes autorisé à utiliser le parallélisme

J'ai pris une petite implémentation sur Internet qui s'exécute en environ 4,5 secondes. Il ne devrait pas être très difficile de battre cela, en supposant que vous avez un bon algorithme.

C avec GMP, 3,6 s

Dieux, mais GMP rend le code laid. Avec une astuce de style Karatsuba, j'ai réussi à réduire à 2 multiplications par étape de doublement. Maintenant que je lis la solution de FUZxxl, je ne suis pas le premier à avoir l'idée. J'ai encore quelques trucs dans ma manche ... peut-être que je les essayerai plus tard.

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

Construit avec gcc -O3 m.c -o m -lgmp.

sauge

Hmm, vous semblez supposer que le plus rapide sera un programme compilé. Pas de binaire pour vous!

print fibonacci(2000000)

Sur ma machine, cela prend 0,10 seconde de processeur, 0,15 seconde de paroi.

edit: chronométré sur la console, au lieu du portable

Haskell

C'est mon propre essai, même si je n'ai pas écrit l'algorithme moi-même. Je l'ai plutôt copié de haskell.org et l' ai adapté pour l'utiliser Data.Vectoravec sa fameuse fusion de flux:

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

Cela prend environ 4,5 secondes lors de la compilation avec GHC 7.0.3 et les indicateurs suivants:

ghc -O3 -fllvm fib.hs

VACHE

 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

Meuglement! (Prend un certain temps. Buvez du lait ...)

Mathematica, interprété:

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

Chronométré:

0.032 secs on my poor man's laptop.

Et bien sûr, pas de binaire.

Ocaml, 0,856s sur mon ordinateur portable

Nécessite la bibliothèque zarith. J'ai utilisé Big_int mais c'est un chien lent par rapport à zarith. Cela a pris 10 minutes avec le même code! La plupart du temps a été consacré à l' impression du foutu numéro (environ 9½ minutes)!

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

Je ne peux pas croire à quel point la bibliothèque a fait une différence!

Haskell

Sur mon système, cela fonctionne presque aussi vite que la réponse de FUZxxl (~ 18 secondes au lieu de ~ 17 secondes).

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, algorithme naïf

Était curieux, et je n'avais pas utilisé gmp avant ... donc:

#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 million) prend environ 7 secondes ... donc cet algorithme ne gagnera pas la course.

J'ai implémenté la méthode de multiplication matricielle (depuis sicp, http://sicp.org.ua/sicp/Exercise1-19 ) dans SBCL mais cela prend environ 30 secondes pour terminer. Je l'ai porté sur C en utilisant GMP, et il renvoie le résultat correct en environ 1,36 secondes sur ma machine. C'est à peu près aussi rapide que la réponse de Boothby.

#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 secondes pour calculer, 18 secondes pour écrire

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
}

Aller

C'est d'une lenteur embarrassante. Sur mon ordinateur, cela prend un peu moins de 3 minutes. Ce n'est que 120 appels récursifs, cependant (après l'ajout du cache). Notez que cela peut utiliser beaucoup de mémoire (comme 1,4 Gio)!

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 code (je ne sais pas ce que vous utilisez)

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 

Il a fallu 56 heures à mon ordinateur pour faire ces deux termes. Mon ordinateur est un peu merdique. J'aurai le numéro dans un fichier texte le 22 octobre. 1.2 concerts est un peu gros à partager sur ma connexion.