1

I wrote a program to calculate (adding) 2 positive big integer using vector to store the numbers.

#include <cstdlib> #include <cstdio> // sd sprintf() #include <iostream> #include <vector>// sd vector typedef short TYPE;// alias void input(); void makeArray(); void display(const std::vector<TYPE> Ar); TYPE convertChar2T( char * ch); void add(); static std::string num1;//store big integer as string static std::string num2; static std::vector<TYPE> Arr1;//store as vector static std::vector<TYPE> Arr2; static std::vector<TYPE> result; int main(int argc, char** argv) { input(); makeArray(); display(Arr1); display(Arr2); add(); display(result); return 0; } //input 2 big integer number void input(){ std::cout << "Enter 1st number : " ; if (! std::getline(std::cin , num1) ) std::cerr << "Not OK\n"; std::cout << "Enter 2nd number : "; if (! std::getline(std::cin , num2) ) std::cerr << "Not OK\n"; } //grab into 2 arrays void makeArray(){ for (std::size_t i = 0; i < num1.size(); i++){ char temp1[2] = { num1[i], '\0'}; //use array-of-char as it need '\0' Arr1.push_back( convertChar2T(temp1) ); //push what is converted } for (std::size_t i = 0; i < num2.size(); i++){ char temp2[2] = { num2[i], '\0'}; Arr2.push_back( convertChar2T(temp2) ); } } //convert char -> TYPE by using sscanf() TYPE convertChar2T( char * ch){ TYPE numb ; sscanf( ch, "%d", &numb );//NGUOC LAI SPRINTF return numb; } //display array void display(const std::vector<TYPE> Ar){ for (std::size_t i = 0; i < Ar.size(); i++) std::cout << Ar.at(i) << '\t'; std::cout << '\n'; } void add(){ std::size_t i = Arr1.size(); // NEVER COMES TO ZERO ( 1 AT LEAST ) std::size_t j = Arr2.size(); //check original one and later one //3 cases : 1 - original one , not yet processed // 2 - original # one, not yet processed // -1 - original # one or one, processed //NOTE: at first only value 1 or 2 ( not process ) short check_one[2] = { ( i == 1 ) ? 1 : 2, ( j == 1 ) ? 1 : 2, }; bool boost = 0; bool Arr1_isgood = true;// whether count to 1 or not bool Arr2_isgood = true;// good -> not yet 1 short temp_result = 0;//temporary result to push into vector while ( Arr1_isgood || Arr2_isgood ){// while not all comes to 1 // i == j : 2 cases // 1st: both 1 now - 3 cases // 1.1 #1+not process original and processed // 1.2 processed and #1+not processed // 1.3 both 1 original + not processed // 2nd: both # 1 if ( i == j ) { if ( check_one[0] == 2 && check_one[1] == -1 ){//#1+not process original and processed temp_result = Arr1[i-1] + boost; check_one[0] == -1; } else if ( check_one[0] == -1 && check_one[1] == 2 ){//processed and #1+not processed temp_result = Arr2[j-1] + boost; check_one[1] = -1; } else//both 1 original + not processed OR both # 1 temp_result = Arr1[i-1] + Arr2[j-1] + boost; //check result >= 10 or < 10 if ( temp_result >= 10 ){ temp_result = temp_result - 10 ; boost = 1; } else boost = 0; //result.begin() return iterator at beginning result.insert( result.begin() ,temp_result ); //update info if ( i == j && i == 1){ // NOTE : NEU SD i==j==1 -> sai (vi luon true) Arr1_isgood = Arr2_isgood = false; continue; } else if ( i == j && i != 1){ // i == j # 1 i--; j--; } } if (i != j){ //check to set flag ( if one of two die ) if ( i == 1 && j > 1 ) Arr1_isgood = false; else if ( i > 1 && j == 1 ) Arr2_isgood = false; // i die && j live OR vice versa if ( (!Arr1_isgood && Arr2_isgood) || (Arr1_isgood && !Arr2_isgood ) ){ if (!Arr1_isgood && Arr2_isgood ){ //1st case if ( check_one[0] == 1 || check_one[0] == 2){//not yet processed as SET FLAG ABOVE first temp_result = Arr1[i-1] + Arr2[j-1] + boost; check_one[0] = -1 ; } else temp_result = Arr2[j-1] + boost; j--; } else if ( Arr1_isgood && !Arr2_isgood ){ //2nd case if ( check_one[1] == 1 || check_one[1] == 2 ){//not yet processed as SET FLAG ABOVE first temp_result = Arr1[i-1] + Arr2[j-1] + boost; check_one[1] = -1 ; } else temp_result = Arr1[i-1] + boost; i--; } } else {// both is good temp_result = Arr1[i-1] + Arr2[j-1] + boost; i--; j--; } //check result >= 10 or < 10 if (temp_result >= 10) { temp_result -= 10; boost = 1; } else boost = 0; result.insert( result.begin() ,temp_result ); } } //insert boost (if any exists) if (boost == 1) result.insert( result.begin(), boost); }

I'm torn between the use of "Arr1_isgood" bool variable and the check_one variable, it seems that they can be combined into one variable ? I tried to do it and it takes a lot of time without correct result. Can the digit be store in some kind of smaller data structure rather than "short" type ? as "short" takes more than needed bits.
Another thing is : it seems that std::size_t only reach up to 4 billion in size, as when size_t reach 1, I decreased it several times and it comes to 4 billion ? Isn't it? I wonder if these codes somehow can be optimized more?

Improve this question
9
  • 1
    Are you writing this code to solve a problem or to learn? If the former, I recommend using an existing bigint library, e.g., GMP. Note: GMP is LGPL . Other bigint libraries have other licensing restrictions. Commented May 2, 2011 at 16:44
  • @Brian: yeah, I did it for learning purpose Commented May 2, 2011 at 16:47
  • 1
    At least from glancing at it, it looks to me like it can be optimized. In particular, instead of storing each digit as an element, you normally want to store the largest elements supported by the hardware. On 64-bit hardware, each item in the array will be 64 bits, and all but the first will be unsigned. This is a place that assembly language also helps (the carry flag is very useful, but not available from C or C++). Commented May 2, 2011 at 16:51
  • Voted to close a "off topic." This question is a better fit at Code Review. Commented May 2, 2011 at 17:40
  • 1
    <<I thought that short is for short int>> TRUE. <<and it's format specifier is "%d">> FALSE. short int and int are different types. Format specifier "%d" is for int, "%ld" for long int, "%hd" for short int, "%hhd" for signed char (as number - not as character), "%lld" for long long int. Commented May 3, 2011 at 7:34

2 Answers 2

Reset to default
1

If you want to manipulate big integers, you should use a big-integer library, e.g. GMP.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

In your machine has 32-bit ints, suppose you represent each number (unsigned) as an array of 31-bit signed ints, starting from the least significant. Then maybe you could do something like this:

// do c = a + b int a[n], b[n], c[n]; int carry = 0; for (i = 0; i < n; i++){ // do the addition with carry c[i] = a[i] + b[i] + carry; // if the addition carried into the sign bit carry = (c[i] < 0); // detect it and remove it from the sum if (carry){ c[i] &= 0x7fffffff; } }

Then you could figure out how to handle negatives.

Improve this answer

4 Comments

can you explain more ? is this manipulating bits ? that's seems strange to me. what is 0x7fffffff ?
@silentbang: I'm using each int in the array to hold a 31-bit quantity, so the high-order bit should be 0. If you add two 31-bit numbers (plus carry) you get a 32-bit number, of which the high-order bit is the new carry bit. So you get that bit into carry, and clear it in the result. c[i] &= 0x7fffffff; clears the 32nd bit (the sign bit). I could have said c[i] &= ~(1<<31);.
if using this way, I need to convert decimal to binary number. how do we convert BIGINTEGER as there is nothing enable multiply/divide/plus/substract operations?
@silentbang: OK, pick whatever base you want. If you want to stick to 1 byte per decimal digit, and do the entire thing in base 10, go right ahead. It's the same concept. It will take longer, of course. BTW that's how the IBM 1620 and 360 did decimal arithmetic, and why the Intel x8x processors have the ADC instruction.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.