Tulis Fibonacci tercepat

10

Ini adalah tantangan lain tentang angka-angka Fibonacci.

Tujuannya adalah untuk menghitung angka Fibonacii ke- 20'000'000 secepat mungkin. Output desimal sekitar 4 MiB besar; dimulai dengan:

28543982899108793710435526490684533031144309848579

Jumlah MD5 dari output adalah

fa831ff5dd57a830792d8ded4c24c2cb

Anda harus mengirimkan program yang menghitung angka saat berjalan dan menempatkan hasilnya stdout. Program tercepat, seperti yang diukur pada mesin saya sendiri, menang.

Berikut ini beberapa aturan tambahan:

  • Anda harus mengirimkan kode sumber dan runnable biner di Linux x64
  • Kode sumber harus lebih pendek dari 1 MiB, dalam hal perakitan juga dapat diterima jika hanya biner yang kecil.
  • Anda tidak harus memasukkan nomor yang akan dihitung dalam biner Anda, bahkan dengan cara yang disamarkan. Angka harus dihitung pada saat runtime.
  • Komputer saya memiliki dua inti; Anda diizinkan menggunakan paralelisme

Saya mengambil implementasi kecil dari Internet yang berjalan sekitar 4,5 detik. Seharusnya tidak terlalu sulit untuk mengalahkan ini, dengan asumsi bahwa Anda memiliki algoritma yang baik.

FUZxxl
sumber
1
Sobat, seperti Sage yang memiliki presisi float tak tentu akan menjalankan hal itu dalam waktu kurang dari 1/10 detik. Itu hanya ungkapan sederhana sepertiphi = (1+sqrt(5))/2
JBernardo
4
Bisakah kita menampilkan angka dalam hex?
Keith Randall
2
@Keith Nggak. Itu bagian dari spec.
FUZxxl
3
Karena diukur pada CPU Anda , kami mungkin juga memiliki beberapa informasi lebih lanjut tentang itu, bukan? Intel atau AMD? Ukuran L1 dan cache instruksi? Instruksi mengatur ekstensi?
JB
2
Saat saya menghitungnya, string awal dan MD5 Anda adalah untuk nomor 20'000'000, bukan hanya 2'000'000.
JB

Jawaban:

4

C dengan GMP, 3.6s

Dewa, tapi GMP membuat kode jelek. Dengan trik ala Karatsuba, saya berhasil mengurangi hingga 2 kali lipat setiap langkah berlipat. Sekarang saya membaca solusi FUZxxl, saya bukan orang pertama yang memiliki ide. Aku punya beberapa trik lagi di lengan bajuku ... mungkin aku akan mencobanya nanti.

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

Dibangun dengan gcc -O3 m.c -o m -lgmp.

stan
sumber
LOL. Selain penamaan pengenal, itulah solusi saya :)
JB
@JB: PERTAMA! : D
boothby
Simpan;) Trik berikutnya di lengan bajuku akan mendapat manfaat dari Haskell lebih banyak dari C.
JB
Trik pertama lengan baju saya terbentur bug GHC. Drat. Saya harus kembali ke yang kedua, yang tidak terlalu menyenangkan untuk diimplementasikan, sehingga akan membutuhkan waktu dan motivasi.
JB
3,6 detik di mesin saya.
FUZxxl
11

Sage

Hmm, Anda tampaknya menganggap bahwa yang tercepat adalah program yang dikompilasi. Tidak ada biner untuk Anda!

print fibonacci(2000000)

Di komputer saya, dibutuhkan 0,10 cpu detik, 0,15 detik dinding.

edit: diberi batas waktu pada konsol, bukan pada notebook

stan
sumber
1
Gagasan saya bukanlah untuk mengetahui, seberapa cepat CAS Anda dapat melakukan ini, tetapi seberapa cepat Anda dapat mengkodekannya sendiri.
FUZxxl
11
Sebagai catatan, saya hanya menempatkan ini sebagai sok pintar; Anda tidak mengatakan untuk tidak menggunakan builtin.
Stanby
5

Haskell

Ini adalah percobaan saya sendiri, walaupun saya tidak menulis algoritma sendiri. Saya lebih suka menyalinnya dari haskell.org dan mengadaptasinya untuk digunakan Data.Vectordengan aliran fusi yang terkenal:

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

Ini membutuhkan waktu sekitar 4,5 detik ketika dikompilasi dengan GHC 7.0.3 dan flag-flag berikut:

ghc -O3 -fllvm fib.hs
FUZxxl
sumber
Aneh ... Saya perlu mengubah 20000000 menjadi 40000000 untuk mendapatkannya untuk mencetak nomor yang diharapkan.
JB
Kena kau. Seharusnya enumFromStepN (s-1)bukanenumFromStepN s
JB
@ JK Maaf atas semua kebingungan ini. Awalnya saya menguji program dengan nilai yang berbeda untuk mendapatkan angka yang cukup besar dan menyimpan output ke file yang berbeda. Tetapi beberapa cara saya membingungkan mereka. Saya telah memperbarui nomor untuk mencocokkan hasil yang diinginkan.
FUZxxl
@ brownby Tidak, saya tidak mengubah nomor fibonacci yang diinginkan, melainkan output referensi, yang salah.
FUZxxl
Catatan: ini tentang 1.5s di komputer saya, tetapi LLVM bukan Data.Vektor tampaknya tidak membawa keuntungan yang signifikan.
JB
4

LEMBU

 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

Melenguh! (Butuh beberapa saat. Minum susu ...)

Timtech
sumber
1
Catatan: Meskipun ini benar-benar berhasil, mungkin tidak akan pernah mencapai 20.000.000 ...
Timtech
2

Mathematica, diartikan:

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

Jangka waktu:

0.032 secs on my poor man's laptop.

Dan tentu saja, tidak ada biner.

Belisarius
sumber
Tidak mencetak stdout.
Stanby
@ bbyby Salah Ini menulis ke output standar jika Anda menggunakan antarmuka baris perintah. Lihat misalnya stackoverflow.com/questions/6542537/...
Dr. belisarius
Tidak, saya menggunakan antarmuka commandline, versi 6.0. Bahkan menggunakan -batchoutput, itu hanya mencetak informasi waktu dan bukan angka Fibonacci.
Stanby
Maaf, tidak dapat mereproduksi karena saya tidak memiliki matematika.
FUZxxl
5
curl 'http://www.wolframalpha.com/input/?i=Fibonacci%5B2+10^6%5D' | grep 'Decimal approximation:' | sed ... Ini berjalan dalam waktu yang konstan sehubungan dengan kecepatan koneksi internet Anda. ;-)
ESultanik
2

Ocaml, 0.856d di laptop saya

Membutuhkan perpustakaan zarith. Saya menggunakan Big_int tapi anjingnya lambat dibandingkan dengan zarith. Butuh 10 menit dengan kode yang sama! Sebagian besar waktu dihabiskan untuk mencetak angka sial (sekitar 9 ½ menit)!

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

Saya tidak percaya betapa banyak perbedaan yang dibuat perpustakaan!

ReyCharles
sumber
1
Sebagai perbandingan, solusi @ boothby membutuhkan waktu 0,875 untuk berjalan di laptop saya. Tampaknya perbedaannya diabaikan. Juga, ternyata laptop saya cepat : o
ReyCharles
1

Haskell

Di sistem saya, ini berjalan hampir secepat jawaban FUZxxl (~ 18 detik, bukan ~ 17 detik).

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))
Joey Adams
sumber
Bagus. Saya suka Haskell.
Arlen
Saya menjalankan ini dalam ghci. Saya cukup terkesan. Haskell sangat bagus untuk jenis masalah kode matematika ini.
Undreren
1

C, algoritma naif

Penasaran, dan saya belum pernah menggunakan gmp sebelumnya ... jadi:

#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 juta) membutuhkan waktu sekitar 7 detik ... jadi algoritma ini tidak akan memenangkan perlombaan.

bayi-kelinci
sumber
1

Saya menerapkan metode penggandaan matriks (dari sicp, http://sicp.org.ua/sicp/Exercise1-19 ) di SBCL tetapi butuh sekitar 30 detik untuk menyelesaikannya. Saya porting ke C menggunakan GMP, dan mengembalikan hasil yang benar dalam waktu sekitar 1,36 detik pada mesin saya. Ini tentang secepat jawaban stan.

#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;
}
Erik Haliewicz
sumber
1

Java: 8 detik untuk menghitung, 18 detik untuk menulis

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
}
averykhoo
sumber
0

Pergilah

Ini sangat lambat. Di komputer saya dibutuhkan kurang dari 3 menit. Ini hanya 120 panggilan rekursif, meskipun (setelah menambahkan cache). Perhatikan bahwa ini mungkin menggunakan banyak memori (seperti 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))
}
ReyCharles
sumber
Saya mencoba memparalelkannya (sebelum menambahkan cache) menggunakan rutinitas go dan mulai menggunakan memori 19 GiB: /
ReyCharles
-4

kode semu (saya tidak tahu apa yang kalian gunakan)

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 

Komputer saya membutuhkan 56 jam untuk melakukan kedua istilah itu. Komputer saya agak jelek. Saya akan memiliki nomornya di file teks pada 22 Oktober. 1.2 gigs agak besar untuk dibagikan pada koneksi saya.

Thomas Olson
sumber
1
Saya bingung dengan jawaban Anda. Kodesemu? Namun Anda punya timing? Kirimkan kodenya! Bahasa tidak masalah!
Stanby
Itu, dan hasilnya hanya sekitar 4 juta digit ...
Wug