Cài đặt hàm tính a^n tối ưu nhất
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).