Menyetel ke Julia: Membuat Deret Fibonacci – Beragampengetahuan

Oleh: Jan Vanhove

Repost dari:

Saat ini saya belajar sedikit tentang Julia, dan saya pikir saya akan berbagi dengan Anda beberapa upaya saya dalam membuat kode Julia. Saya akan meninggalkan Anda dengan pitch, dan saya akan langsung ke tujuan posting blog ini: menulis tiga fungsi Julia berbeda yang dapat menghasilkan deret Fibonacci.

Deret Fibonacci

Deret Fibonacci yang terkenal adalah deret bilangan asli yang tak terhingga, bilangan pertamanya adalah 1, 1, 2, 3, 5, 8, 13, …. Urutannya didefinisikan sebagai berikut:

\[\textrm{Fibonacci}(n) =
\begin{cases}
1, & \textrm{for $n = 1$ or $n = 2$}, \\
\textrm{Fibonacci}(n – 1) + \textrm{Fibonacci}(n – 2), & \textrm{otherwise}.
\end{cases}\]

Mari tulis beberapa fungsi Julia yang dapat menghasilkan string ini.

Julia

Anda dapat mengunduh Julia dari julialang.org. Saat ini saya menggunakan paket Pluto.jl yang memungkinkan Anda menulis kode Julia di notebook reaksi. Lihat halaman Pluto.jl untuk informasi lebih lanjut.

Alternatif pertama: Fungsi rekursif murni

Deret Fibonacci didefinisikan secara rekursif: Untuk mendapatkan WANITAAngka Fibonacci, pertama Anda perlu menghitung n-1th dan n-2Angka Fibonacci dan kemudian menjumlahkannya. Kita dapat menulis fungsi Julia yang secara akurat mencerminkan definisi deret Fibonacci sebagai berikut:

function fibonacci(n)
  if n <= 2
    return 1
  end
  return fibonacci(n - 1) + fibonacci(n - 2)
end

Fungsi ini mengasumsikan bahwa n adalah bilangan asli bukan nol. Jika n sama dengan atau kurang dari 2, yaitu jika n adalah 1 atau 2, itu segera mengembalikan 1, sesuai dengan definisi string. Jika kondisi ini tidak terpenuhi, output dihitung secara rekursif. Fungsi tersebut dapat dijalankan sebagai berikut:

fibonacci(10)

## 55

Periksa! Tapi dari sudut pandang komputasi, fibonacci() fungsionalitas yang cukup boros. Mendapatkan fibonacci(10)kita perlu menghitung fibonacci(9) Dan fibonacci(8). Tapi untuk menghitung fibonacci(9)Kami Tetapi juga perlu menghitung fibonacci(8). Untuk berdua fibonacci(9) Dan fibonacci(8)kita perlu menghitung fibonacci(7)dll. Sebenarnya kita perlu menghitung nilai dari fibonacci(8) dua kali, itu fibonacci(7) tiga kali, yaitu fibonacci(6) lima kali, dan dari fibonacci(5) tujuh kali. Jadi kita akan melakukan banyak perhitungan berulang-ulang. Untuk alasan ini, fibonacci() Fungsi yang sangat tidak efisien: Meskipun Anda dapat menghitung fibonacci(10) dalam sepersekian detik, mungkin perlu beberapa menit untuk menghitung, misalnya, fibonacci(60). Untungnya, kami dapat mempercepat fungsi kami secara dramatis.

Opsi dua: Rekursi dengan mnemonik

Memoisasi adalah teknik pemrograman di mana setiap hasil antara yang telah Anda hitung disimpan dalam larik. Sebelum menghitung hasil antara lainnya, cari di array terlebih dahulu jika Anda belum benar-benar menghitungnya, menghemat banyak perhitungan yang tidak perlu. Fungsi Julia berikut sedikit lebih terlibat daripada yang sebelumnya, tetapi jauh lebih efisien.

function fib_memo(n)
  known = zeros(Int64, n)
  function memoize(k)
    if known[k] != 0
      # do nothing
    elseif k == 1 || k == 2
      known[k] = 1
    else
      known[k] = memoize(k-1) + memoize(k-2)
    end
    return known[k]
  end
  return memoize(n)
end

Fungsi keseluruhan yang sebenarnya akan kita panggil fib_memo(). Itu menciptakan sebuah array yang disebut known dengan n nol. Kemudian itu mendefinisikan fungsi di dalamnya memoize(). Fungsi berikut mendapatkan bilangan bulat k yang sebenarnya akan antara 0 dan n dan lakukan hal berikut. Pertama, ia memeriksa apakah knilai th dalam array known masih 0. Jika diubah, fungsinya hanya mengembalikan nilai knilai th di known. Jika tidak, jika k sama dengan 1 atau 2, itu menetapkan nilai pertama atau kedua known ke 1. Jika k lebih dari 2 pukulan kNilai dari known dihitung secara rekursif. Dalam semua kasus, memoize() fungsi kembali k Nilai dari known Himpunan. di luar fib_memo() fungsi kemudian hanya mengembalikan hasil dari memoize(n).

Mungkin pada titik ini, komputer Anda sudah berjalan fibonacci(60) dan Anda dapat mencoba implementasi alternatif:

fib_memo(60)

## 1548008755920

Perhatikan seberapa cepat fungsi baru ini! Bahkan angka Fibonacci ke-200 dapat dihitung dalam sepersekian detik:

fib_memo(200)

## -1123705814761610347

Sayangnya kami sekarang mengalami masalah lain: integer overflow. Hasil perhitungan menjadi sangat besar sehingga melebihi kisaran bilangan bulat 64-bit. Untuk mengatasi masalah ini, kami dapat bekerja dengan BigIntegers sebagai gantinya:

function fib_memo(n)
  known = zeros(BigInt, n)
  function memoize(k)
    if known[k] != 0
      # do nothing
    elseif k == 1 || k == 2
      known[k] = 1
    else
      known[k] = memoize(k-1) + memoize(k-2)
    end
    return known[k]
  end
  return memoize(n)
end

fib_memo(200)

## 280571172992510140037611932413038677189525

Cantik!

Opsi ketiga: Gunakan rumus Binet

Alternatif ketiga adalah solusi matematis daripada solusi pemrograman. Menurut rumus Binet, WANITAangka Fibonacci ke-th dapat dihitung sebagai

\[\textrm{Fibonacci}(n) = \frac{\varphi^n – \psi^n}{\sqrt{5}},\]

di mana $\varphi = \frac{1 + \sqrt{5}}{2}$, Rasio Emas,
dan $\psi = \frac{1 – \sqrt{5}}{2}$, konjugasinya. Di Julia:

function fib_binet(n)
  φ = (1 + sqrt(5))/2
  ψ = (1 - sqrt(5))/2
  fib_n = 1/sqrt(5) * (φ^n - ψ^n)
  return BigInt(round(fib_n))
end

Perhatikan bahwa Anda dapat menggunakan simbol matematika seperti $\varphi$ dan $\psi$ di Julia.
Fungsi ini juga berjalan sangat cepat:

fib_binet(60)

## 1548008755920

fib_binet(200)

## 280571172992512015699912586503521287798784

Perhatikan, bagaimanapun, bahwa hasil untuk angka Fibonacci ke-200
27 urutan besarnya berbeda dari urutan yang diperoleh menggunakan
fib_memo():

fib_binet(200) - fib_memo(200)

## 1875662300654090482610609259

Dengan menggunakan rumus Binet, kita sudah cukup
rapi dunia aritmatika bilangan bulat dan memasuki dunia
Aritmatika floating point penuh dengan kesalahan perkiraan.
Sementara kami melakukannya, kami juga dapat menghitung dan membuat grafik ukuran
perkiraan kesalahan ini. Pada kode di bawah ini, saya pertama kali menggunakan
daftar pemahaman untuk menghitung 200 Fibonacci pertama
nomor menggunakan keduanya fib_memo() Dan fib_binet().
Perhatikan bahwa saya menambahkan titik (.) untuk kedua nama fungsi.
Ini adalah notasi Julia untuk menjalankan perhitungan vektor.
Perhatikan lebih lanjut bahwa saya mengakhiri semua baris dengan titik koma untuk menghasilkan
prompt tidak dicetak.
Kemudian saya menghitung nilai absolut dari selisih antara
angka yang diperoleh dengan kedua metode perhitungan. Catatan lagi
gunakan titik di keduanya abs.() Dan .- perlu untuk memiliki keduanya
dari fungsi-fungsi ini beroperasi pada vektor. Terakhir,
Saya mengubah perbedaan absolut ini menjadi perbedaan relatif dari
jawaban benar;

fib_integer = fib_memo.(1:200);
fib_math    = fib_binet.(1:200);
abs_diff = abs.(fib_math .- fib_integer);
rel_diff = abs_diff ./ fib_integer;

Untuk menyelesaikan posting blog ini, mari sekarang grafik absolut dan
perbedaan relatif saat menggunakan paket Plots.jl.
Sementara Gambar 1 menunjukkan bahwa kesalahan mutlak menjadi sangat besar,
Gambar 2 menunjukkan bahwa perbedaan tersebut hanya sampai satu
bagian yang tidak signifikan dari jawaban yang benar.

using Plots
plot(1:200, abs_diff, seriestype=:scatter,
     xlabel = "n",
     ylabel = "absolute difference",
     label = "")
plot(1:200, rel_diff, seriestype=:scatter, 
     xlabel = "n",
     ylabel = "relative difference",
     label = "")

Gambar 1. Perbedaan mutlak antara
Angka Fibonacci diperoleh dengan menggunakan fib_binet()
dan yang diperoleh dengan menggunakan fib_memo().

Gambar 2. Perbedaan relatif antara
Angka Fibonacci diperoleh dengan menggunakan fib_binet()
dan yang diperoleh dengan menggunakan fib_memo().

Terkait