2015/10/09

Big integer add, multiply operations in C++

64 бит хэмжээнээс хэтрэх, натурал тоонуудыг нэмэх, үржих үйлдлүүдийг C++ дээр бичив. Жишээ кодонд тооны факториал олох програмыг хавсаргав.

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
int n, s;

string add(string a, string b){
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    //cout << a << " + " << b << endl;
    string sum = "";
    int a_len = a.length();
    int b_len = b.length();
    int max_len = max(a_len, b_len);
    int carry = 0;
    //cout << a << endl << b << endl;
    for(int k = 0; k < max_len ; k++){
        int digit_a = (k < a_len ? a[k] - '0' : 0);
        int digit_b = (k < b_len ? b[k] - '0' : 0);
        sum += ((digit_a + digit_b + carry) % 10) + '0';
        carry = (digit_a + digit_b + carry) / 10;
        
    }
    if(carry) sum += "1";
    //cout << sum << endl;
    reverse(sum.begin(), sum.end());
    return sum.length() == 0 ? "0" : sum;
}
string multiply(string a, string b){
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    string product = "";
    int a_len = a.length();
    int b_len = b.length();
    int max_len = max(a_len, b_len);
    
    string offset = "";
    for(int i = 0; i < a_len; i++){
        int carry = 0;
        string temp_product = offset;
        for(int j = 0; j < b_len; j++){
            temp_product += (a[i]-'0')*(b[j]-'0')%10 + carry + '0';
            carry = (a[i]-'0')*(b[j]-'0')/10;
        }
        if(carry) temp_product += carry + '0';
        
        reverse(temp_product.begin(), temp_product.end());
        product = add(product, temp_product);
        offset += "0";
    }
   
    return product[0] != '0' ? product : "0";
}
int main(){
    string result = "1";
    cin >> n;
    for(int i = 1; i <= n; i++ ){
        result = multiply(result, to_string(i));
    }
    cout << result << endl;
    return 0;
}

No comments:

Post a Comment

Миний бичсэн бичлэг танд өчүүхэн ч болтугай хэрэг болсон бол сэтгэгдлээ бичиж үлдээхийг хүсье. Баярлалаа :)