View Full Version : Có ai biết thuật toán tính log số lớn không ?
Làm sao để tính log hay ln của một số lớn ? Có ai biết cách tính cái này không? Cho mình hỏi thêm tí nữa ở trong C có hàm pow() để tính số mũ thế với số thực lớn thì làm sao để tính được ???
Bạn có thể cho ví dụ không ? câu hỏi hơi chung chung
Muốn tính được mấy cái log hay số mũ lớn thì bạn cần xây dựng các phép toán + - * / div và mod trên số lớn ( số lớn ở đây là những chuỗi số chứ không phải các số bình thường, nghĩa là các số lớn ở đây đều là kiểu string thuần túy)
Đúng rồi, đầu tiên là xây dựng các phép toán trên "số lớn", +-*/ đã, kế đó là khai triển ra chuỗi (xem phần giải tích cổ điển í), rồi tính, "thế thôi".
Nên xây dựng số lớn kiểu thực, bắt chước floating point.
Tất nhiên là mình đã xây dựng sẵn các hàm tính số lớn cơ bản rồi. Nhưng ý mình muốn hỏi là làm thế nào hay ai biết phương pháp tính log của số lớn không đấy ?
To erafc : bạn có thể nói rõ hơn về thuật toán khai triển được không ? Mình cũng đã tìm hiểu cái này nhưng không được >
thewallfan
17-11-2005, 21:12
Để tính log(a)x thì ta đưa về lnx như sau:
log(a)x = lnx/lna ;
sau đó áp dụng khai triển chuỗi Taylo của ln(1+x) :
ln(1+x) = x - x^2/2 + x^3/3 - ... + (-1)^n*x^(n+1)/(n+1)....
để tính.
Muốn biết thêm về khai triển chuỗi các hàm sơ cấp ,hãy tìm đọc các sách về Toán cao cấp.
1 word: google.
Để tính log(a)x thì ta đưa về lnx như sau:
log(a)x = lnx/lna ;
sau đó áp dụng khai triển chuỗi Taylo của ln(1+x) :
ln(1+x) = x - x^2/2 + x^3/3 - ... + (-1)^n*x^(n+1)/(n+1)....
để tính.
Muốn biết thêm về khai triển chuỗi các hàm sơ cấp ,hãy tìm đọc các sách về Toán cao cấp.
Sorry nhưng công thức của bác là bậy bạ. Người ta muốn tính số lớn mà tương cái CT Taylor này (bác coi lại coi Toán sơ cấp xem nó đúng với x trong khoảng nào nhé).
Muốn dùng CT trên phải decompose x một tí. Google đê.
Đúng rồi ngay cả với sin cos khai triển Taylo cũng chỉ đúng số nhỏ nhưng vì nó tuần hoàn nên dễ dàng. Còn Taylo áp dụng với ln thì không thể được. Ai có cách khác không ?
thewallfan
18-11-2005, 20:21
Xin lỗi tôi đã nhầm công thức vì tài liệu tôi đọc nó không ghi rõ khoảng xác định của x trong công thức đó.Bạn có thể vào đây để xem khai triển đúng của lnx :
http://www.efunda.com/math/taylor_series/logarithmic.cfm
Và theo tôi để tính lnx thì chỉ có cách là khai triển nó ra chuỗi thôi và tùy theo sai số cho phép để bạn tính gần đúng giá trị của nó.
Hmm, đã nói là các bác google dùm em cái mà.
Tính ln có cả trăm cách, nói cả ngày cũng ko hết.
C1: Cái CT của bác thewallfan là xài được nhưng phải decompose. Nó chỉ áp dụng cho ln(1+x) với -1<x<1 nên chỉ đúng (gần đúng với x<2). Nhớ thêm ln(ab) = lna+lnb nên dùng đệ quy chia cho e (lne=1), đến chừng nào còn lại số nào nhỏ hơn 2 (gần 0 càng tốt) thì áp dụng Taylor cho ln(1+x). Ví dụ 123455678 = e^=19+0.691703=>ln(12345678) = 19+ln(0.691703). Dùng Taylor cho cái này ln(1-0.308297) đến term thứ 10 chẳng hạn, biết luôn sai số là ~O(0.308297^10)~1e-5.
C2: y=lnx thì x = exp(y). Giải PT này (bằng Newton, bisection hay cái gì cũng được) thì biết x thôi. (Nếu bạn nghĩ dùng cách giải 1 pt để tính một giá trị gì đó là tệ thì nghĩ lại - một ví dụ cực đẹp là tính x^(-0.5)). Muốn tính exp(x) thì có thể để ý là hàm này có behavior khá tốt, và có thể áp dụng khai triển Taylor cho mọi x.
Ngoài ra còn cả tỉ cách. 2 cách trên là nghĩ ra tạm còn bác nào muốn tốt hơn thì google.
Ờ viết xong mới thấy bác gì đó hỏi cả pow(x). x^y = exp(y*ln(x)), cứ thế mà tiếp...
Cải tiến phát.
Quả táo xài số lớn kiểu gì vậy, giả dụ dùng floating point, cơ số 10 nhá (mấy cũng được, ko quan trọng), x = a*10^b, 0<a<10, b thuộc Z, viết kiểu khoa học ấy, x=aE+b.
Khi đó ln(x) =ln(a) + b*ln(10). Ko nên chia dần cho e, chậm mà sai số tích lũy lại rất lớn.
Công việc bây giờ là tính ln(10) và ln(a). Trước hết nên tính sẵn ln(10), e thành các const để trong lib, vì phải dùng đến nó nhiều lần, ngại làm thì lấy maple nhờ nó tính hộ cũng được.
Để tính ln(a), 0<a<10, có thể làm bằng C1 hay C2 của mach2 đều good, C2 thì dùng Newton cho nhanh (e^y - hàm đẹp mà), chia đôi chậm lắm, đặc biệt khi tính giá trị e^y, mỗi lần tính lại phải khai triển 1 phát.
Chùi em xin các bác. Idea thì như thế nhưng chẳng có gì phải bàn với cái này cả. Người ta chế ra bao nhiêu cách rồi hichic, sao lại đi chế bánh xe chi cho mệt nếu mục đích là sử dụng. Các bác cứ google một phát ra cả mớ, có cả publication cho cả vụ này mới kinh hehe
Nhưng chắc các bác muốn bàn cho nó vui. Thế thì em cũng muốn :) Nói về tốc độ thì cứ như cách của bác erafc là hay. Em chia cho e là hơi chuối. Cứ chia cho 10 là hay nhất, hoặc giả tìm a sao cho x = a+y sao cho y nhỏ hơn 2 rồi cứ thế mà phán Taylor quanh a cũng được (đạo hàm bậc n chỏ ln tính lý thuyết được nên chả lo, với lại nó (ln(a))'(n) ~ a^(-n) càng làm tăng phần hấp dẫn). Vấn đề là ln(a) phải đẹp, chẳng hạn như là a phân tích được bằng tích một đống số nguyên tố - để thuận cho việc lập một cái bảng tra tính trước ln của các số nguyên tố này. Cái này em nghĩ đại ra cho vui chắc ko có ý nghĩa thực dụng vì lăn tăn quá.
Cách của bạn HP (dùng khai triển với mọi x>0) là cực kỳ bất hợp lý. Bạn nhắm phải dùng đến term n thứ mấy để có được sai số chấp nhận được -> 1e-8 với x = 25? (n~100). Chưa kể đến việc tính x^n khi cả x lớn và n lớn là ko chấp nhận đựơc vì sai số tăng dần (bác erafc chỉ ra em dùng chia cho e là bậy bạ -> thank bác nhiều). Nhiều khi một cách có vẻ đúng trên mặt lý thuyết là ko phù hợp trên mặt thực hành ;)
Em cảm ơn các bác nhiều, em cũng đã thử và kết quả cũng khá tốt.
Bên cạnh đây em xin hỏi tí nữa. Cái công thức x^y với x, y thực , lớn thì tính như thế nào được ạ. Em đã thử nhiều cách nhưng đều không được.
"lớn" theo bạn là lớn thế nào? Cơ bản là x^y = exp(y*ln(x)) thôi.
Theo tôi thì tính thế này. A = x^y = 10^(y*log(x)). log(x) là log cơ số 10. Bạn tính y*log(x) xong rồi, cho nó là một số dạng a+b, trong đó a là integer, b là phần dư (số thực). Thế thì:A = 10^(a+b) = 10^b*10^a, trong đó 10^a là phần exponential trong biểu diễn số thực, vấn đề còn lại là tính 10^b. Tính cái này thì dễ, 10^b = exp(b*ln(10)). Dùng khai triển Taylor tính exp(b*log(10)). Cách này hơi dài dòng nhưng an toàn cao, vả lại có thể lợi dụng "a" để biểu diễn số lớn.
Powered by vBulletin® Version 4.2.0 Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.