Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 13 kết quả

Đề tài: Phương pháp tính a^b

  1. #1
    Ngày gia nhập
    10 2007
    Bài viết
    10

    Mặc định Phương pháp tính a^b

    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:
    C++ Code:
    1. Integer Power( Integer& a, Integer& x );
    2. /*!
    3.     preserves Integer a,
    4.     preserves Integer x,
    5.    
    6.     requires
    7.         x => 0
    8.     ensures
    9.         Power= a^x
    10. !*/

    Đây là cách làm thông dụng nhất

    C++ Code:
    1. Integer result = 1, counter = 1;
    2.  
    3. while ( counter <= x )
    4. {
    5.     result = result * a;
    6.     counter ++;
    7. }
    8.  
    9. 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:

    C++ Code:
    1. if ( x < 1 )
    2. {
    3.     return 1;
    4. }
    5. else
    6. {
    7.     Integer result = Power(a, x/2);
    8.     if ( (x mod 2) == 0 )
    9.     {
    10.         return (result*result);
    11.     }
    12.     else
    13.     {
    14.         return (result*result*a);
    15.     }
    16. }

    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ể.
    Đã được chỉnh sửa lần cuối bởi hvutrong : 15-04-2008 lúc 11:12 AM.

  2. #2
    Ngày gia nhập
    02 2008
    Bài viết
    66

    Bạn viết một đoạn hoàn chỉnh xem nào.
    C++ Code:
    1. if ( x < 1 )
    2. {
    3.     return 1;
    4. }
    5. else
    6. {
    7.     Integer result = Power(a, x/2);
    8.     if ( (x mod 2) == 0 )
    9.     {
    10.         return (result*result);
    11.     }
    12.     else
    13.     {
    14.         return (result*result*a);
    15.     }
    16. }
    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.

  3. #3
    Ngày gia nhập
    10 2007
    Bài viết
    10

    Đồ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?

  4. #4
    Ngày gia nhập
    10 2007
    Bài viết
    43

    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
    C Code:
    1. #include <stdio.h>
    2. #include <conio.h>
    3. #include <iostream.h>
    4. #include <stdlib.h>
    5.  
    6. long ham(int x,int n)
    7.  {
    8.  
    9.    if(x==0&&n==0)
    10.    {
    11.    cout<<"1";
    12.    exit(1);
    13.    }
    14.  
    15.    if(x==0)
    16.     {
    17.      cout<<"0";
    18.      exit(1);
    19.     }
    20.  
    21.    if(n<0)
    22.    {
    23.    n = -n;
    24.     cout<<"1/"<<x*ham(x,n-1);
    25.     getch();
    26.    exit(1);
    27.  
    28.    }
    29.    if(n==0) return 1;
    30.    else
    31.  
    32.        return (x*ham(x,n-1));
    33.    }
    34.  
    35.    void main()
    36.    {
    37.     int y;
    38.    
    39.     int x;
    40.     cin>>x;
    41.     cin>>y;
    42.     ham(x,y);
    43.     cout<<ham(x,y);
    44.     getch();
    45.     }

    ở 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
    Đã được chỉnh sửa lần cuối bởi boy_popping : 24-10-2008 lúc 04:46 PM.

  5. #5
    Ngày gia nhập
    09 2008
    Bài viết
    19

    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).

  6. #6
    Ngày gia nhập
    07 2007
    Nơi ở
    TP.HCM
    Bài viết
    199

    Mặc định Phương pháp tính a^b

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

    C++ Code:
    1. int pow(int a, int power)
    2. {
    3.     int res = 1;
    4.  
    5.     while (power)
    6.     {
    7.         if (power & 1) res *= a;
    8.         a *= a;
    9.         power >>= 1;
    10.     }
    11.  
    12.     return res;
    13. }

    Thử viết hàm power với số mũ là float chứ không phải integer xem.
    Đã được chỉnh sửa lần cuối bởi DKhanh : 24-10-2008 lúc 10:00 PM.

  7. #7
    Ngày gia nhập
    01 2008
    Bài viết
    4

    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.
    C Code:
    1. luythua = 1;
    2. t= x;
    3. while(n>0)
    4. {
    5.     if(n%2)
    6.        luythua= luythua * t;
    7.     t= t* t;
    8.     n= n/2;
    9. }
    thuật toán này theo mình nghĩ là tối ưu
    Đã được chỉnh sửa lần cuối bởi zkday2686 : 18-11-2008 lúc 11:26 PM.

  8. #8
    Ngày gia nhập
    05 2013
    Bài viết
    11

    Trích dẫn Nguyên bản được gửi bởi hieusua Xem bài viết
    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?

  9. #9
    Ngày gia nhập
    01 2013
    Bài viết
    1,476

    Trích dẫn Nguyên bản được gửi bởi kuro97 Xem bài viết
    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.

  10. #10
    Ngày gia nhập
    03 2012
    Bài viết
    9

    [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
    C Code:
    1. #include <stdio.h>
    2. #include <conio.h>
    3. #include <iostream.h>
    4. #include <stdlib.h>
    5.  
    6. long ham(int x,int n)
    7.  {
    8.  
    9.    if(x==0&&n==0)
    10.    {
    11.    cout<<"1";
    12.    exit(1);
    13.    }
    14.  
    15.    if(x==0)
    16.     {
    17.      cout<<"0";
    18.      exit(1);
    19.     }
    20.  
    21.    if(n<0)
    22.    {
    23.    n = -n;
    24.     cout<<"1/"<<x*ham(x,n-1);
    25.     getch();
    26.    exit(1);
    27.  
    28.    }
    29.    if(n==0) return 1;
    30.    else
    31.  
    32.        return (x*ham(x,n-1));
    33.    }
    34.  
    35.    void main()
    36.    {
    37.     int y;
    38.    
    39.     int x;
    40.     cin>>x;
    41.     cin>>y;
    42.     ham(x,y);
    43.     cout<<ham(x,y);
    44.     getch();
    45.     }

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

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn