Phương pháp tính a^b

[hvutrong]

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 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 theo mình ước tính). Đáng kể phải không nào. Mình đã thực hiện thử và đo thời gian thực thi, ở những con số lớn, cách 2 nhanh hơn đáng kể.

[mushu]

Bạn viết một đoạn hoàn chỉnh xem nào.

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);    }}

Viết như vậy mình đâu có thấy nó tính đủ đâu.
Hơn nữa số càng lớn cũng đồng nghĩa với việc tính toán càng lâu.

[hvutrong]

Đồng ý với bạn là số càng lớn tính càng lâu nhưng 50 phép nhân và 32582657 phép nhân đủ tạo nên 1 khác biệt "cực kì đáng kể" nếu máy bạn có thể chạy được với những con số lớn như thế.

Còn bạn nói tính không đủ tức là sao?

[boy_popping]

nếu tính a^b mà chạy đệ quy sợ là CT sẽ chạy vòng vòng mãi và không đủ bộ nhớ
bt boy làm thì áp dụng với số nhỏ thôi, mọi người coi dùm cách này có đc gọi là nhanh hay ko

#include <stdio.h>#include <conio.h>#include <iostream.h>#include <stdlib.h> long ham(int x,int n) {    if(x==0&&n==0)   {   cout<<"1";   exit(1);   }    if(x==0)    {     cout<<"0";     exit(1);    }    if(n<0)   {   n = -n;    cout<<"1/"<<x*ham(x,n-1);    getch();   exit(1);    }   if(n==0) return 1;   else        return (x*ham(x,n-1));   }    void main()   {    int y;        int x;    cin>>x;    cin>>y;    ham(x,y);    cout<<ham(x,y);    getch();    }

ở bài của bạn hvutrong sẽ ko tính đc số lớn vì bạn khai báo biến là integer
mà nếu khai báo kiểu khác thì sẽ ko có được x%2==0

[hieusua]

Cách tính lũy thừa này "nghe có vẻ" là tối ưu hơn rất nhiều, nhưng mình có cách chứng minh nó tốn thời gian không kém gì cách nhân truyền thống (Trong trường hợp worst case).

[DKhanh]

Hàm power của mình không cần dùng đệ quy nè.

int pow(int a, int power){     int res = 1;     while (power)    {        if (power & 1) res *= a;        a *= a;        power >>= 1;    }     return res;}

Thử viết hàm power với số mũ là float chứ không phải integer xem.

[wawa]

Mình cũng có 1 thuật giải cho hàm pow.
tính x^n với x,n là số nguyên.

luythua = 1;t= x;while(n>0){    if(n%2)        luythua= luythua * t;    t= t* t;    n= n/2;}

thuật toán này theo mình nghĩ là tối ưu

[kuro97]

Cách tính lũy thừa này "nghe có vẻ" là tối ưu hơn rất nhiều, nhưng mình có cách chứng minh nó tốn thời gian không kém gì cách nhân truyền thống (Trong trường hợp worst case).

Xin phép được xem cách chứng mình của anh?

[prog10]

Xin phép được xem cách chứng mình của anh?

Nếu là a^b mod p thì đúng sai quá rõ ràng.
Nhưng nếu chỉ là a^b thì sẽ phức tạp hơn.
Vấn đề là có thể thực hiện phép bình phương (a^2) nhanh hơn 1 phép nhân khác (a*b), với a và b đều có n chữ số.
Và FFT - Toom-Cook - Karatsuba đều chỉ hiệu quả khi cả 2 thừa số vượt 1 ngưỡng nhất định.
Vì vậy cho dù tính mod hay ko tính mod thì bình phương-nhân vẫn nhanh hơn.

[trantuyen7372]

[QUOTE=boy_popping;56134]nếu tính a^b mà chạy đệ quy sợ là CT sẽ chạy vòng vòng mãi và không đủ bộ nhớ
bt boy làm thì áp dụng với số nhỏ thôi, mọi người coi dùm cách này có đc gọi là nhanh hay ko

#include <stdio.h>#include <conio.h>#include <iostream.h>#include <stdlib.h> long ham(int x,int n) {    if(x==0&&n==0)   {   cout<<"1";   exit(1);   }    if(x==0)    {     cout<<"0";     exit(1);    }    if(n<0)   {   n = -n;    cout<<"1/"<<x*ham(x,n-1);    getch();   exit(1);    }   if(n==0) return 1;   else        return (x*ham(x,n-1));   }    void main()   {    int y;        int x;    cin>>x;    cin>>y;    ham(x,y);    cout<<ham(x,y);    getch();    }

ở đoạn code này vẫn bị lỗi bạn à :(