Tính lũy thừa n^k với n và k lớn sử dụng hệ cơ số 10^9 (một tỷ)

Sử dụng hệ cơ số 10^9

Sau đây là chương trình trên C++ sử dụng thuật toán bình phương và nhân.

// Tinh 2^64 tren he co so 10^9
#include <iostream>
#include <time.h>
#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <stack>

typedef unsigned int uint;  // uint = 0 -> 2^32-1

#define maxd 100000

#define radix9 1000000000

using namespace std;

int plus9(uint *ketqua, uint *b, uint *c, int d)
{
    uint n = 0;
    for (int i = 0; i < d; i++) {
        n += b[i] + c[i];  // add with carry
        ketqua[i] = n % radix9;
        n /= radix9;
    }
    if (n > 0) ketqua[d++] = n;   // add a new digit
    return d;
}

int nhanhe10_9voi1so(uint * a, uint * ketqua, int d, uint x) { // a la so trong he co so 10^9,
                                      //0 <= x < 10^9
    int i;
    long long n = 0;
    for (i=0; i<d; i++) {
        n = a[i] * (long  long) x + n;
        ketqua[i] = n % radix9;
        n = n / radix9;
    }
    if (n > 0) {
        ketqua[d] = n;
        d++;
    }

    return d;
}

int max2(int a, int b) {
    if (a > b) return a;
        else return b;
}

int binhphuong(uint * a, uint * ketqua, int d) {
    int i, j, dketqua = 0, dtemp;
    uint temp[maxd];

    memset(ketqua, 0, maxd * sizeof(uint));
    for (i=d-1; i>=0; i--) cout << ketqua[i] << ".";
    cout << endl;
    //for (i=0; i<maxd; i++) ketqua[i] = 0;
    //ketqua[0] = 0;

    for (i = 0; i < d; i++) {
        //memset(temp, maxd * sizeof(uint), 0); // Thuc ra thi khong can dong nay
        dtemp = nhanhe10_9voi1so(a, temp, d, a[i]);
        if (i != 0) {
                for (j=dtemp-1; j>=0; j--) temp[j+i] = temp[j];
                for (j=0; j<i; j++) temp[j] = 0;
                dtemp = dtemp + i;
        }

        dketqua = plus9(ketqua, ketqua, temp, max2(dtemp, dketqua));
    }

    return dketqua;
}

int nhan(uint * a, uint * b, uint * ketqua, int d1, int d2) {
    int i, j, dketqua = 0, dtemp;
    uint temp[maxd];

    memset(ketqua, 0, maxd * sizeof(uint));
    //for (i=0; i<maxd; i++) ketqua[i] = 0;
    //ketqua[0] = 0;

    for (i = 0; i < d2; i++) {
        //memset(temp, maxd * sizeof(uint), 0); // Thuc ra thi khong can dong nay
        dtemp = nhanhe10_9voi1so(a, temp, d1, b[i]);
        if (i != 0) {
                for (j=dtemp-1; j>=0; j--) temp[j+i] = temp[j];
                for (j=0; j<i; j++) temp[j] = 0;
                dtemp = dtemp + i;
        }

        dketqua = plus9(ketqua, ketqua, temp, max2(dtemp, dketqua));
    }

    return dketqua;
}

int main() {

    uint a[maxd];
    uint ketqua[maxd];
    int d = 1, dketqua;

    int n, k;

    cout << "Nhap a = "; cin >> n;
    a[0] = n;

    cout << "Nhap k = "; cin >> k;

    // Chuyen k sang he nhi phan
    uint x = k;
    stack<bool> V;
    while (x != 0) {
        V.push(x%2);
        x = x/2;
    }

    if (k == 0) {
        cout << n << "^" << k << " = " << 1;
        return 0;
    }

    // k != 0
    V.pop();
//    cout << "Ma nhi phan cua " << k << " la: ";
//    while (!V.empty()) {
//        cout << V.top();
//        V.pop();
//    }
//
//    cout << endl;

    int i, j;

    while (!V.empty()) {
        dketqua = nhan(a, a, ketqua, d, d);
        for (j=0; j<dketqua; j++) a[j] = ketqua[j];
        d = dketqua;

        if (V.top() == 1) {
            dketqua = nhanhe10_9voi1so(a, ketqua, d, n);
            for (j=0; j<dketqua; j++) a[j] = ketqua[j];
            d = dketqua;
        }

        V.pop();
    }

    printf("%d^%d = \n%u", n, k, ketqua[dketqua-1]);
    for (i=dketqua-2;i>=0; i--) printf(".%09u", ketqua[i]);

    getch();

    return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: