Đến nội dung

Hình ảnh

Vui với thuật toán: Bài số 4

- - - - -

  • Please log in to reply
Chủ đề này có 13 trả lời

#1
namdung

namdung

    Thượng úy

  • Hiệp sỹ
  • 1205 Bài viết
Tôi muốn tìm số Fibonacci thứ 10^9

Nếu cài thuật toán theo công thức đệ quy F(n+1) = F(n) + F(n-1) thì chương trình nào cũng báo lỗi quá nhiều vòng lặp.

Các bạn hãy giúp tôi lập trình tính F(10^9) mà sử dụng ít vòng lặp hơn.

#2
Alligator

Alligator

    Sĩ quan

  • Founder
  • 428 Bài viết
Có lẽ giải thuật sau là gọn nhất với một vòng lặp while (minh họa bằng chương trình C)

main()
{
long N;
long Fm,Fn,Fp,i;

N=1000000000L;
Fm=1;
Fn=1;
i=2;

while (i<N)
  {
   i++;
   Fp=Fn+Fm;
   Fm=Fn;
   Fn=Fp;
  }

printf("F(%ld) = %ld\n",i,Fn);

return 0;
}

Kết quả

F(100000000) = 1532868155


Về mặt thực hành khi lập trình nên để ý là các biến (variables) đều được khai báo (declare) dạng số long integer (32-bit theo C chuẩn) có tầm (range) khoảng từ -2*10^9 đến 2*10^9 mới phù hợp với tầm các giá trị số trong bài toán này.
<span style='color:blue'>Roses are red,
violets are blue,
Fermat is dead,
but his theorem is true.
</span>

#3
namdung

namdung

    Thượng úy

  • Hiệp sỹ
  • 1205 Bài viết
Bạn xem kỹ lại đi, chắc là sai rồi, vì F(10^9) rất lớn, không thể "bé tí" như thế được.

Namdung

#4
TieuSonTrangSi

TieuSonTrangSi

    Thiếu úy

  • Founder
  • 526 Bài viết
Bài này vui đấy :Leftrightarrow

- Về mức độ lớn của http://dientuvietnam...metex.cgi?F_{N}, ta có http://dientuvietnam...etex.cgi?N=10^9 thì

http://dientuvietnam.net/cgi-bin/mimetex.cgi?F_{10^9}, hay chỉ cần vài chữ số đầu và số mũ của lũy thừa 10, tức là dạng

?

- Nếu máy không chịu 1 vòng lặp "dài"

do i= 1, 10^9
...
end do (i)

liệu ta có thể "ăn gian" bằng cách làm 2 hoặc 3 vòng "ngắn" imbricated nhau, kiểu :

do k= 1, 10^3
do j= 1, 10^3
do i= 1, 10^3
....
enddo (i)
enddo (j)
enddo (k)


không ?
Chí lớn trong thiên hạ không đựng đầy đôi mắt của giai nhân

#5
TieuSonTrangSi

TieuSonTrangSi

    Thiếu úy

  • Founder
  • 526 Bài viết
Muốn phát biểu thêm vài điều sau :

1) Số mũ của số phải tìm quá lớn, quá khả năng của tất cả các máy :Leftrightarrow Muốn lập trình tính thì phải làm một multiple-precision program, trữ một số trong một bảng (array), mỗi phần tử của bảng gồm 5 chữ số chẳng hạn, rồi định nghĩa lại phép cộng cho bảng...

2) Mình có ước lượng này. Xuất phát từ

http://dientuvietnam.net/cgi-bin/mimetex.cgi?(dfrac{1-sqrt{5}}{2}\)^N, vì nó rất nhỏ, chỉ ảnh hưởng đến những chữ số rất xa sau dấu phẩy. Vậy, ta hãy tính những chữ số đầu cùng số mũ của http://dientuvietnam...c{sqrt{5} 1}{2}\)^N. Như đã viết tại bài trên, ta có



(theo máy tính). Vậy,

.

Thiết nghĩ ta có thể chứng minh chặt chẽ được kết quả này bằng cách đánh giá sai số (estimate error) của từng giai đoạn trên.
Chí lớn trong thiên hạ không đựng đầy đôi mắt của giai nhân

#6
Alligator

Alligator

    Sĩ quan

  • Founder
  • 428 Bài viết
:leq Chết thật, mình sai rồi, mọi người tha cho tội ẩu nhé.
Kết quả sai là vì tràn số (overflow) khi số vượt qua giới hạn 32-bit thì nó quay lại từ đầu. Nhưng C chuẩn thì dạng biến số nguyên chỉ có đến thế. Thật ra lúc viết code đã đinh ninh chuyện coi chừng overflow rồi, nhưng nghĩ số long integer tầm 4 triệu chắc cũng đủ ai ngờ chẳng thấm vào đâu (căn bản vì mình không có khái niệm gì về độ lớn của các số Fibonacci ở vị trí cao cả)
Hèn gì mà khi thử tính bằng Maple thì báo lỗi, trong khi Maple có khả năng tính số nguyên (chính xác) khá mạnh.
Anh 2TS nói kết quả có 208 triệu chữ số, để thử ước lượng xem cần chỗ chứa là bao nhiêu (mọi người xem giùm có đúng không, run rồi :leq )
10^(208e9) chuyển qua binary là khoảng 0.6909610438e12 bit tức là khoảng 80 GB (Gigabyte). Lớn quá đúng là không uP nào chịu nổi. Tính từng đoạn như anh 2TS đề xuất chắc được nhưng cũng lằng nhằng lắm đây. Để suy nghĩ thêm.
<span style='color:blue'>Roses are red,
violets are blue,
Fermat is dead,
but his theorem is true.
</span>

#7
HaiDang

HaiDang

    Trung sĩ

  • Thành viên
  • 180 Bài viết
Bài này mà tính ra số thứ 10^9 chắc chết luôn, bản thân vòng lặp ít nhất là 10^9 lần, trong đó phép cộng ít nhất là 10^9, độ phức tạp 10^18 + thêm các phép toán, trời, khủng khiếp!!!!
Ý, chịu hết nỗi rồi nè !!!! buông tha anh!!!!
Hình đã gửi Hình đã gửi

#8
namdung

namdung

    Thượng úy

  • Hiệp sỹ
  • 1205 Bài viết
Như tôi đã nói từ đầu, nếu dùng công thức F(n+1) = F(n) + F(n-1) thì chắc chắn sẽ bị báo lỗi quá nhiều vòng lặp, chưa nói đến vụ tràn số.

Như vậy, chúng ta có 2 vấn đền cần giải quyết:

1) Hạn chế số vòng lặp
2) Lưu trữ dữ liệu

Tôi đã viết 1 chương trình Maple, chạy hết 6 phút thì nó dừng vì không đủ bộ nhớ (đã dùng đến 530M)

Nếu chỉ cần biết 10000 chữ số tận cùng của F(n) chẳng hạn thì chương trình của tôi chạy được (chỉ mất vài giây). Kết quả là khoảng 1,5 trang A4. Như vậy để biễu diễn 208 triệu chữ số, ta cần 20800 x 1,5 trang A4 = 31200 trang A4. Một cuốn sách cũng ác đấy!

Bây giờ chúng ta thử đặt ra các yêu cầu giới hạn hơn:

1) Tìm 1 triệu chữ số tận cùng của F(10^9)
2) Tìm 10 chữ số đầu tiên của F(10^9)

Namdung

#9
nemo

nemo

    Hoa Anh Thảo

  • Founder
  • 416 Bài viết
Nếu để tìm số Fibonacci lớn nhất có thể sao ta không sử dụng công thức http://dientuvietnam...{n 1}-F^2_{n-1}, số vòng lặp sẽ giảm đáng kể.
<span style='color:purple'>Cây nghiêng không sợ chết đứng !</span>

#10
TieuSonTrangSi

TieuSonTrangSi

    Thiếu úy

  • Founder
  • 526 Bài viết
Ý của nemo rất hay :leq Khi áp dụng ta cũng có thể phối hợp công thức đó với http://dientuvietnam...F_{n 1}^2 F_n^2 để tính các giá trị tương ứng với chỉ số lẻ.

Thử với http://dientuvietnam...metex.cgi?N=100 : hàng dưới là (chỉ số của) những số hạng cần tính để có được hàng trên.

100
49 51
24 25 26
11 12 13 14
5 6 7 8

Hy vọng là số vòng lặp cần thiết tỉ lệ với . Hình như còn nhiều công thức "thần sầu" hơn nữa :leq, chẳng hạn : , hoặc

.
Chí lớn trong thiên hạ không đựng đầy đôi mắt của giai nhân

#11
namdung

namdung

    Thượng úy

  • Hiệp sỹ
  • 1205 Bài viết
Các bạn đi đúng hướng rồi đấy. Bằng các công thức như Nemo và TSTS đưa ra, chúng ta sẽ đưa số vòng lặp từ bậc N xuống còn log(N).

Như vậy ý thứ nhất đã được giải quyết và theo tôi, chúng ta đã giải quyết được cơ bản vấn đề.

Với ý thứ hai, để lưu giữ giữ liệu một số có khoảng 208 triệu chữ số, có lẽ chúng ta không nên dùng hệ thập phân nữa mà dùng hệ đếm N - phân với N lớn hơn. Ví dụ N = 128 hay N = 256 (miễn là ta đủ các ký tự để biểu diễn).

Chú ý là Maple có cơ chế làm việc với số lớn rất tốt. Bạn nào hiểu rõ về cơ chế này có thể chia sẻ cùng các bạn trong diễn đàn nhé.

#12
TieuSonTrangSi

TieuSonTrangSi

    Thiếu úy

  • Founder
  • 526 Bài viết
Về cơ sở lý thuyết thì coi như ta đi đúng hướng ^_^ Còn về kỹ thuật thực tiễn thì tôi thấy cũng nên lưu ý đến một vấn đề (kinh điển) sau.

Trong công thức của nemo, có http://dientuvietnam...etex.cgi?F_n^2. Vậy, ta phải biết thực hiện phép nhân giữa hai số "lớn". Gọi http://dientuvietnam...n/mimetex.cgi?M là hệ M-phân ta sử dụng để biểu diễn các số :

http://dientuvietnam.net/cgi-bin/mimetex.cgi?c_k<M, nhưng chuyện này không khó, và cũng không tốn kém lắm). Vấn đề chính ở đầy là phép nhân :lol: rất tốn kém : nếu ta đếm xem cần bao nhiêu phép tính để có http://dientuvietnam...n/mimetex.cgi?C, thì ta được http://dientuvietnam...imetex.cgi?n^2.

Có một kỹ thuật dùng Fast Fourrier Transform làm giảm đi số phép tính : ta chỉ cần phép tính thôi thay vì . Dụng cụ này dường như đã có sẵn trong Maple (khi làm việc với số lớn). Còn nếu bạn muốn viết lập trình lại từ đầu thì phải viết luôn cái... FFT ^_^
Chí lớn trong thiên hạ không đựng đầy đôi mắt của giai nhân

#13
RongChoi

RongChoi

    Thượng sĩ

  • Founder
  • 215 Bài viết
Anh TSTS nói rõ hơn tác dụng của FFT trong phép nhân 2 số lơn được ko? Với bác namdung có thể giải thích tác dụng của việc dùng cơ số lớn?
Ngoài ra thì phép nhân giữa 2 số có 2n chữ số luôn có thể đưa về phép nhân giữa 2 số có n chữ số, trong bất kể hệ cơ số nào vì mọi số A (có 2n chữ số trong hệ cơ số M) đều có thể biểu diễn bởi :
,
với có n chữ số.

#14
namdung

namdung

    Thượng úy

  • Hiệp sỹ
  • 1205 Bài viết
Đúng là trong bài này ta sẽ đụng đến việc nhân số lớn. Bản thân trong Maple đã cài sẵn thuật toán nhân số lớn bằng FFT nên tốc độ rất nhanh.

Về thuật toán nhân nhanh, chúng ta sẽ nói thêm ở một topic khác.

Việc sử dụng cơ số lớn chủ yếu để lưu trữ kết quả thôi. Cũng giống như ta dùng hệ thập lục phân vậy đó: chữ F thay được cho số 1111 dài ngoằng.

Namdung




1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh