Bàn về phương pháp tối ưu tính tổng các số Fibonacci
hardcore
17
math
10
code
39
algorithm
33
White

Huy Trần viết ngày 14/10/2016

Cuối tuần này, nhóm #random à nhầm #hardcore của team Ruby Việt Nam có một buổi thảo luận rất thú vị về một bài toán không mấy đặc biệt, đó là: Tính tổng các số Fibonacci từ 1 tới 4 triệu

Giải pháp đơn giản

Để tính một số Fibonacci thì cực kì đơn giản, chỉ cần làm theo công thức:

alt text

Code thì khá là đơn giản bằng cách dùng đệ quy:

func Fibonacci(n: Int) -> Int {
  if n <= 2 {
    return 1
  }
  return Fibonacci(n - 1) + Fibonacci(n - 2)
}

Hoặc dùng vòng lặp để khử đệ quy:

func Fibonacci(n: Int) -> Int {
  var a = 0
  var b = 1
  var next = 0
  for i in 0..<n {
    if i <= 1 {
      next = i
    } else {
      next = a + b
      a = b
      b = next
    }
  }
  return next
}

Quay lại bài toán tính tổng các số Fibonacci, ta có thể implement một hàm tính tổng đơn giản như sau:

func Sum(n: Int) -> Int {
  var sum = 0
  for i in 0..<n {
    sum += Fibonacci(n)  
  }
  return sum
}

Tuy nhiên thì với thuật toán như vậy, chúng ta có gặp phải vấn đề gì không?

Câu trả lời là có, vấn đề rất lớn!

Đầu tiên hãy nhìn vào đồ thị biểu diễn thời gian cần để tính Fibonacci dưới đây:

alt text

Dễ nhận thấy, với số n càng lớn, thì thời gian để tính Fibonacci của số đó càng lâu.

Cho nên đối với bài toán ở đây là tính tổng các số Fibonacci từ 1 tới 4 triệu, thì xét về yếu tố thời gian, điều này cũng trở thành một vấn đề bất khả thi rồi. Để giải quyết bài toán này, chúng ta cần phải loại trừ được vấn đề thời gian do chạy đệ quy hoặc việc lặp gây ra.

Vì mọi vấn đề liên quan đến số học đều, hiển nhiên, có thể biểu diễn được bằng toán học, vậy đây cũng không phải là ngoại lệ, hãy xem chúng ta có thể mượn được gì từ toán nào.

Công thức tính tổng n số Fibonacci

Chúng ta có công thức tính tổng n số Fibonacci với mọi số n >= 2 như sau:

alt text

Nếu không tin tưởng vào công thức, thì các bạn có thể tham khảo chứng minh công thức tại đây

Vậy để tính tổng các số Fibonacci từ 1 tới 4 triệu, chúng ta có thể tìm số Fibonacci thứ 4 triệu lẻ 2 (4,000,002) rồi trừ giá trị này đi cho 1. Bài toán quay trở về tìm một số Fibonacci bất kì.

Tuy nhiên, 4 triệu lẻ 2 vẫn là một con số quá lớn để có thể tính toán bình thường trên một máy tính cá nhân (với các yếu tố như: tốc độ xử lý, giới hạn bộ nhớ, giới hạn của kiểu dữ liệu,...). Chúng ta cần tìm một giải pháp khác ít tốn kém hơn.

Công thức tìm một số Fibonacci bất kì

Chúng ta có 2 cách để thực hiện, một là dùng Công thức Binet, hai là dùng Ma trận

Sử dụng công thức Binet

Chúng ta có thêm công thức Binet để tìm một số Fibonacci bất kì như sau:

alt text

Áp dụng 2 công thức trên, chúng ta có thể loại bỏ hoàn toàn việc sử dụng đệ quy hoặc vòng lặp, và điều này sẽ cải thiện tốc độ tính toán một cách đáng kể.

Cách implement thì cực kì đơn giản:

import Foundation

func Fibonacci(n: Double) -> Double {
  return (pow((1.0 + sqrt(5.0)), n) - pow((1.0 - sqrt(5.0)), n)) / (pow(2.0, n) * sqrt(5.0))
}

func Sum(n: Double) -> Double {
  return Fibonacci(n: n + 2.0) - 1.0
}

Một nhược điểm duy nhất của cách này là việc tính toán với căn bậc 2 trên máy tính sẽ dẫn tới tình trạng làm tròn số và sẽ xuất hiện sai số nhất định khiến cho giá trị không thực sự chính xác.

Sử dụng ma trận

Sau khi viết bài này thì được a @kiennt giới thiệu thêm một cách khác, đó là dùng ma trận.

Quay trở lại công thức tính một số Fibonacci:

alt text

Đồng nghĩa với:

alt text

Vì vậy ta có thể biểu diễn dưới dạng ma trận như sau:

alt text

Viết lại thành dạng như thế này:

alt text

Nếu không tin thì các bạn cứ thử tự chứng minh đi :smirk: tiếp, ta cũng có thể viết lại biểu thức trên thành:

alt text

Và sau khi thực hiện một vài phép tính toán đơn giản trên ma trận chúng ta thu được kết quả sau:

alt text

Với F(1) = 1F(0) = 0. Bài toán quay trở về dạng bài toán nhân 2 ma trận 2x2 và nhân một ma trận 2x2 với một ma trận 2x1.

Sau khi tính ra được ma trận trên, ta dễ dàng trích ra được giá trị của F(n) và áp dụng công thức tính tổng đã nói ở phần đầu.

Dưới đây là đoạn implement bằng Python của a @kiennt:

def mul_metrix_1(m1, m2):
    return (
        m1[0][0] * m2[0] + m1[0][1] * m2[1],
        m1[1][0] * m2[0] + m1[1][1] * m2[1]
    )


def mul_matrix(m1, m2):
    """
    matrix m1, m2 is 2x2 matrix which is respresend like
    ((r00, r01), (r10, r11))
    """

    return (
        (m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0], m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]),
        (m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0], m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1])
    )


def pow_matrix(m, n):
    """ m is 2x2 matrix """
    if n == 1:
        return m
    elif n % 2 == 0:
        a = pow_matrix(m, n / 2)
        return mul_matrix(a, a)
    else:
        return mul_matrix(pow_matrix(m, n - 1), m)


def fibo(n):
    if n == 0:
        return 1
    if n == 1:
        return 1

    a = ((1, 1), (1, 0))
    an = pow_matrix(a, n)
    pair_0 = (1, 1)
    pair_n = mul_metrix_1(an, pair_0)
    return pair_n[1]


for i in xrange(2, 10):
    print fibo(i)

Xin chân thành cảm ơn ae nhóm #hardcore của cộng đồng Ruby Việt Nam đã tích cực thảo luận để tổng hợp thành bài viết này, đặc biệt là @nguyenduyhao1111, @huydx, @kiennt, @unrealhoang

Hy vọng bài viết phần nào giúp cho các bạn nhận ra sự quan trọng của việc ứng dụng toán học, đặc biệt là việc sử dụng ma trận vào giải quyết các bài toán phức tạp trong lập trình. Viết xong bài tổng hợp này mình vẫn còn ngồi vắt tay lên trán mà suy nghĩ, giá mà hồi đó mình chăm học toán hơn thì tốt biết mấy :joy:


Update: Bác @TuanPM có viết một bài về sử dụng chip ESP32 dual core để tính số Fibonacci bằng cả 2 core rất hay, mời các bạn vào đọc :D

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

Huy Trần

109 bài viết.
1595 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
155 46
Tại sao phải viết blog kĩ thuật? Có rất nhiều bài viết trên mạng nói về vấn đề tại sao một lập trình viên nên thường xuyên viết các bài blog kĩ thu...
Huy Trần viết 3 năm trước
155 46
White
149 39
(Ảnh) Tiếp tục sêri (Link) lần này, chúng ta sẽ cùng tìm hiểu và mô phỏng lại một chức năng mà mọi người đang bắt đầu sử dụng hằng ngày, đó là chứ...
Huy Trần viết 2 năm trước
149 39
White
104 17
Phần 1: Tự truyện Tui và Toán đã từng là hai kẻ thù không đội trời chung trong suốt hơn mười lăm năm ròng rã. Ngay từ ánh nhìn đầu tiên đã ghét nh...
Huy Trần viết 2 năm trước
104 17
Bài viết liên quan
White
32 6
Mình có một anh bạn người Pháp tên là Aurelien, anh này có một biệt tài đó là convert được màu RGB sang mã Hex chỉ bằng cách tính nhẩm. Phương phá...
Huy Trần viết 1 năm trước
32 6
White
10 0
Hadoop là cái gì vậy? “Hadoop là một framework nguồn mở viết bằng Java cho phép phát triển các ứng dụng phân tán có cường độ dữ liệu lớn một cách ...
nguyenduyhao1111 viết gần 2 năm trước
10 0
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
109 bài viết.
1595 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!