35minutes
18-04-2008, 11:41
Phần này tuy đơn giản nhưng không phải ai cũng biết, thế nên mình giới thiệu qua cho một số bạn tham khảo.
Trong tính toán, chúng ta thường xuyên phải tính a^x. Không tính đến việc dùng hàm pow có sẵn trong thư viện "math.h", bạn sẽ viết hàm Power như thế nào?
Vì hàm mũ thường cho ra kết quả rất lớn, biến int hay long thường không đáp ứng nổi nên mình giả sử như các bạn có 1 đối tượng là Integer có thể lưu giữ 1 số nguyên dương lớn bất kì ( bạn có thể tự tạo 1 đối tượng như thế dựa trên 1 vector < int > hay stack <int>)
Đây là contract của hàm:
Integer Power(
Integer& a,
Integer& x
);
/*!
preserves Integer a,
preserves Integer x,
requires
x => 0
ensures
Power= a^x
!*/
Đây là cách làm thông dụng nhất
Integer result = 1, counter = 1;
while ( counter <= x )
{
result = result * a;
counter ++;
}
return result;
Như vậy với a^x thì chương trình sẽ phải thực hiện x phép nhân. Giả sử bạn thực hiện a^4 thì ct thực hiện 4 phép nhân, a^999999 thì ct sẽ thực hiện 999999 phép nhân.
Cách làm như sau, bạn chỉ tốn 5 phép nhân cho a^10, với a^100 bạn chỉ tốn 8 phép nhân.
Để ý a^x = a^(x/2) . a^(x/2) , chúng ta có thể viết hàm trên theo dạng đệ quy như sau:
if ( x < 1 )
{
return 1;
}
else
{
Integer result = Power(a, x/2);
if ( (x mod 2) == 0 )
{
return (result*result);
}
else
{
return (result*result*a);
}
}
với cách làm trên chương trình thực hiện "xấp xỉ" n phép nhân cho đến khi x(1/2)^n < 1 tương đương với n > log (base2) x.
Số nguyên tố lớn nhất người ta tìm được tính đến bây giờ là 2^32582657-1, nếu bạn có 1 máy tính đủ sức để tính con số trên, với cách làm đầu tiên, bạn tốn 32582657 phép nhân. Còn với cách làm thứ 2, bạn sẽ chỉ tốn khoảng log (base2) 32582657 = 25 phép nhân ( nhiều hơn 1 chút vì phải tính thêm các phép nhân của những lần mũ lẻ nhưng chắc chắn ct sẽ không thực hiện quá 50 phép nhân ). Đáng kể phải không! Mình đã thực hiện thử và đo thời gian thực thi, ở những con số lớn như mũ vài trăm, cách 2 nhanh hơn khá nhiều.
Trong tính toán, chúng ta thường xuyên phải tính a^x. Không tính đến việc dùng hàm pow có sẵn trong thư viện "math.h", bạn sẽ viết hàm Power như thế nào?
Vì hàm mũ thường cho ra kết quả rất lớn, biến int hay long thường không đáp ứng nổi nên mình giả sử như các bạn có 1 đối tượng là Integer có thể lưu giữ 1 số nguyên dương lớn bất kì ( bạn có thể tự tạo 1 đối tượng như thế dựa trên 1 vector < int > hay stack <int>)
Đây là contract của hàm:
Integer Power(
Integer& a,
Integer& x
);
/*!
preserves Integer a,
preserves Integer x,
requires
x => 0
ensures
Power= a^x
!*/
Đây là cách làm thông dụng nhất
Integer result = 1, counter = 1;
while ( counter <= x )
{
result = result * a;
counter ++;
}
return result;
Như vậy với a^x thì chương trình sẽ phải thực hiện x phép nhân. Giả sử bạn thực hiện a^4 thì ct thực hiện 4 phép nhân, a^999999 thì ct sẽ thực hiện 999999 phép nhân.
Cách làm như sau, bạn chỉ tốn 5 phép nhân cho a^10, với a^100 bạn chỉ tốn 8 phép nhân.
Để ý a^x = a^(x/2) . a^(x/2) , chúng ta có thể viết hàm trên theo dạng đệ quy như sau:
if ( x < 1 )
{
return 1;
}
else
{
Integer result = Power(a, x/2);
if ( (x mod 2) == 0 )
{
return (result*result);
}
else
{
return (result*result*a);
}
}
với cách làm trên chương trình thực hiện "xấp xỉ" n phép nhân cho đến khi x(1/2)^n < 1 tương đương với n > log (base2) x.
Số nguyên tố lớn nhất người ta tìm được tính đến bây giờ là 2^32582657-1, nếu bạn có 1 máy tính đủ sức để tính con số trên, với cách làm đầu tiên, bạn tốn 32582657 phép nhân. Còn với cách làm thứ 2, bạn sẽ chỉ tốn khoảng log (base2) 32582657 = 25 phép nhân ( nhiều hơn 1 chút vì phải tính thêm các phép nhân của những lần mũ lẻ nhưng chắc chắn ct sẽ không thực hiện quá 50 phép nhân ). Đáng kể phải không! Mình đã thực hiện thử và đo thời gian thực thi, ở những con số lớn như mũ vài trăm, cách 2 nhanh hơn khá nhiều.