Difference between revisions of "Cài đặt hàm tính a^n tối ưu nhất"

Latest revision as of 17:13, 27 June 2017

Việc tính a^n (a mũ n), trong đó a là số thực còn n là số nguyên dương, thực ra rất đơn giản nếu mọi người sử dụng thư viện toán học trong C/C++. Trường hợp không sử dụng thư viện, các bạn cũng có thể cài đặt đơn giản thông qua sử dụng vòng lặp for/while hoặc sử dụng đệ quy, trong trường hợp này độ phức tạp là O(n).

Ở đây mình xin đưa ra giải pháp cài đặt hàm tính a^n tối ưu với độ phức tạp O(log2(n)) và tận dụngtoán tử bit trong cài đặt. Chi tiết cài đặt như dưới:

Tệp main.cpp:

#include <stdio.h>
#include <time.h>
#include <math.h>

#define    N_MAX2    100

// Calculate a pow n (n<=2*N_MAX2)
double g_pow_buffer[N_MAX2];
double powan(double a, int n) {
    if (n<0) return 0;
    if (n==0) return 1;

    // Tinh n/2
    int ndiv2 = (n >> 1);
    if (ndiv2+1>N_MAX2) return 0;

    int powNum = 0;                        // So phan tu trong mang tam
    double result = a;                     // Chua ket qua phep tinh a pow n
    int powCount = 1;                      // Luu so mu
    g_pow_buffer[powNum++] = result;

    // Tinh a mu n su dung vong lap
    while (powCount < n) {
        if (powCount <= ndiv2) {
            result = result*result;
            g_pow_buffer[powNum++] = result;
            powCount = powCount << 1;
        } else {
            // Tinh phan con lai su dung toan tu bit
            int remainCount = n - powCount;
            int bitCount = 0;
            while (remainCount) {
                if (remainCount & 0x00000001) {
                    result *= g_pow_buffer[bitCount];
                }
                remainCount = remainCount >> 1;
                bitCount++;
                powNum++;
            }
            break;
        }
    }
 
    // Tra ve ket qua
    return result;
}
 
int main() {
    int maxN = 200;
    double a = 3.14159;
    double myResult[maxN];
    double myResultTimeSpent = 0;
    double mathResult[maxN];
    double mathResultTimeSpent = 0;

    // Tinh toan su dung ham tu viet
    clock_t begin = clock();
    for (int i=0; i<maxN; i++) {
        myResult[i] = powan(a, i);
    }
    clock_t end = clock();
    myResultTimeSpent = (double)(end - begin) / CLOCKS_PER_SEC;

    // Tinh toan su dung ham toan hoc
    begin = clock();
    for (int i=0; i<maxN; i++) {
        mathResult[i] = pow(a, i);
    }
    end = clock();
    mathResultTimeSpent = (double)(end - begin) / CLOCKS_PER_SEC;

    // In ket qua
    printf("Total time use my function: %lf (seconds)\n", myResultTimeSpent);
    printf("Total time use math function: %lf (seconds)\n", mathResultTimeSpent);
    for (int i=0; i<maxN; i++) {
        printf("%lf^%d: %lf (MyFunc) - %lf (Math)\n", a, i, myResult[i], mathResult[i]);
    }

    return 0;
}

Code trên cũng thử so sánh thời gian thực hiện giữa hàm tự cài đặt và hàm pow trong thư viện math (Bạn cần để ý rằng hàm pow trong thư viện math cài đặt tổng quát hơn cho trường hợp với n là double):

./AMuN
Total time use my function: 0.000019 (seconds)
Total time use math function: 0.000041 (seconds)
3.141590^0: 1.000000 (MyFunc) - 1.000000 (Math)
3.141590^1: 3.141590 (MyFunc) - 3.141590 (Math)
3.141590^2: 9.869588 (MyFunc) - 9.869588 (Math)
3.141590^3: 31.006198 (MyFunc) - 31.006198 (Math)
3.141590^4: 97.408762 (MyFunc) - 97.408762 (Math)
3.141590^5: 306.018392 (MyFunc) - 306.018392 (Math)
3.141590^6: 961.384321 (MyFunc) - 961.384321 (Math)
3.141590^7: 3020.275370 (MyFunc) - 3020.275370 (Math)
3.141590^8: 9488.466899 (MyFunc) - 9488.466899 (Math)
3.141590^9: 29808.872726 (MyFunc) - 29808.872726 (Math)
3.141590^10: 93647.256468 (MyFunc) - 93647.256468 (Math)
3.141590^11: 294201.284447 (MyFunc) - 294201.284447 (Math)
3.141590^12: 924259.813206 (MyFunc) - 924259.813206 (Math)
3.141590^13: 2903645.386568 (MyFunc) - 2903645.386568 (Math)
3.141590^14: 9122063.309989 (MyFunc) - 9122063.309989 (Math)
3.141590^15: 28657782.874030 (MyFunc) - 28657782.874030 (Math)
3.141590^16: 90031004.099223 (MyFunc) - 90031004.099223 (Math)
3.141590^17: 282840502.168078 (MyFunc) - 282840502.168078 (Math)
3.141590^18: 888568893.206212 (MyFunc) - 888568893.206213 (Math)
3.141590^19: 2791519149.207705 (MyFunc) - 2791519149.207706 (Math)
...

Download source code: [[File:AMuN.zip]]  (Đọc tệp README để biết cách build và chạy).