How to implement a big int in C ++

Question

I would like to implement a large int class in C ++ as an exercise for programming - a class that can handle numbers larger than long int. I know that there are already several open source versions, but I would like to write my own. I am trying to understand what the correct approach is.

I understand that the general strategy is to get the number as a string, and then split it into smaller numbers (for example, single digits) and put them in an array. At this point, it should be relatively simple to implement various comparison operators. My main problem is how I will implement things like addition and multiplication.

I am looking for a general approach and recommendations, not the actual working code.

Answer 1

Things to consider for a large int class:

• Mathematical operators: +, -, /, *,% Do not forget that your class can be on either side of the operator, that the operators can be in a chain, that one of the operands can be int, float, double, etc.

• I / O operators: →, <<This is where you find out how to correctly create your class from user input and how to format it for output.

• Conversions / roles: deduce what types / classes your large int class should be converted to how to properly handle the conversion. Quick lists include double and float, and can include int (with appropriate bounds to check) and complex (provided that this can handle the range).

Answer 2

A fascinating task. :)

I assume you need integers of arbitrary length. I propose the following approach:

Consider the binary character of type "int". Think about how to use simple binary operations to emulate what circuits do on your CPU when they add things. If you are interested in more detail, consider reading this wikipedia article on semi-qualifiers and incremental adders . You will do something similar to this, but you can go to such a low level, but being lazy I thought that I would simply refuse and find an even simpler solution.

But before going into any algorithmic details about adding, subtracting, multiplying, we find some data structure. An easy way, of course, is to store things in std :: vector.

template< class BaseType > class BigInt { typedef typename BaseType BT; protected: std::vector< BaseType > value_; }; 

You might want to consider whether you want to make a vector of a fixed size and if it pre-selects it. The reason is that for various operations you have to go through each element of the vector - O (n). You might want to know how complicated the operation is, and fixed n does just that.

But now to some algorithms for working by numbers. You can do this at a logical level, but we will use this magic power of the processor to calculate the results. But what we take from the logical illustration of Half- and FullAdders is how it relates to hyphenation. As an example, consider how to implement the + = operator. For each number in BigInt <> :: value_, you must add them and see if the result leads to some form of transfer. We will not do this in different ways, but rely on the nature of our BaseType (whether it be long or int or short or any other): it overflows.

Of course, if you add two numbers, the result should be more than more than one of these numbers, right? If it is not, the result overflows.

 template< class BaseType > BigInt< BaseType >& BigInt< BaseType >::operator += (BigInt< BaseType > const& operand) { BT count, carry = 0; for (count = 0; count < std::max(value_.size(), operand.value_.size(); count++) { BT op0 = count < value_.size() ? value_.at(count) : 0, op1 = count < operand.value_.size() ? operand.value_.at(count) : 0; BT digits_result = op0 + op1 + carry; if (digits_result-carry < std::max(op0, op1) { BT carry_old = carry; carry = digits_result; digits_result = (op0 + op1 + carry) >> sizeof(BT)*8; // NOTE [1] } else carry = 0; } return *this; } // NOTE 1: I did not test this code. And I am not sure if this will work; if it does // not, then you must restrict BaseType to be the second biggest type // available, ie a 32-bit int when you have a 64-bit long. Then use // a temporary or a cast to the mightier type and retrieve the upper bits. // Or you do it bitwise. ;-) 

Another arithmetic operation is similar. Hell, you could even use stl-functors std :: plus and std :: minus, std :: times and std :: dives, ... but remember to carry over. :) You can also implement multiplication and division using its pros and cons, but it’s very slow, because it will recount the results that you already calculated in previous calls plus and minus at each iteration. There are many good algorithms for this simple task, use wikipedia or the Internet.

And, of course, you must implement standard operators such as operator<< (just shift each value in value_.size()-1 to the left for n bits, starting with value_.size()-1 ... oh and remember the transfer :), operator< - you can even optimize a bit here by checking the rough number of size() digits first. And so on. Then make your class useful by making friends with std :: ostream operator<< .

We hope that this approach will be useful!

Answer 3

There is a complete section: [The Art of Programming, Volume 2: Seven-Dimensional Algorithms, Section 4.3. Multiple-Point Arithmetic, p. 265-318 (ed. 3)]. You can find other interesting material in Chapter 4, Arithmetic.

If you really do not want to look at another implementation, do you think it is that you need to learn? There are countless mistakes to be made, and their disclosure is instructive as well as dangerous. There are also problems in identifying important computing economies and having appropriate storage structures to prevent serious performance problems.

The question for you is: how do you intend to test your implementation and how do you propose to demonstrate the correctness of its arithmetic?

You may need to test another implementation (without looking at how it works), but it may take more to do this so as not to analyze the excrutiating test level. Do not forget to consider failure modes (due to memory problems, from the stack, work too long, etc.).

Good luck

Answer 4

addition probably should be done in the standard linear time algorithm
but for multiplication you can try http://en.wikipedia.org/wiki/Karatsuba_algorithm

Answer 5

Once you have the digits of the numbers in the array, you can do addition and multiplication in the same way as you would do them with difficulty.

Answer 6

Interestingly, I just watched a video about this before I saw your question. Here is the link . Courtesy of the Chaos Communications Congress.

Answer 7

Do not forget that you do not need to limit yourself to 0-9 digits, i.e. use bytes in the form of numbers (0-255), and you can still perform long manual arithmetic in the same way as for decimal digits. You can even use an array of long ones.

Answer 8

I'm not sure if using a string is the right way - although I never wrote the code myself, I think that using an array of a basic numeric type might be the best solution. The idea is that you simply expand what you already have, as the processor expands one bit to an integer.

For example, if you have a structure

 typedef struct { int high, low; } BiggerInt; 

Then you can manually perform your own operations on each of the “numbers” (in this case, high and low), remembering the overflow conditions:

 BiggerInt add( const BiggerInt *lhs, const BiggerInt *rhs ) { BiggerInt ret; /* Ideally, you'd want a better way to check for overflow conditions */ if ( rhs->high < INT_MAX - lhs->high ) { /* With a variable-length (a real) BigInt, you'd allocate some more room here */ } ret.high = lhs->high + rhs->high; if ( rhs->low < INT_MAX - lhs->low ) { /* No overflow */ ret.low = lhs->low + rhs->low; } else { /* Overflow */ ret.high += 1; ret.low = lhs->low - ( INT_MAX - rhs->low ); /* Right? */ } return ret; } 

This is a slightly simplified example, but it should be fairly obvious how to get to a structure that has a variable number of any base number class that you use.

Answer 9

Like others, do it all the way to the old-fashioned long way, but avoid doing it all in base 10. I would suggest doing it all in base 65536 and store things in a lot of lengths.

Answer 10

Check here to find out how GMP implements its algorithms.

Answer 11

Use the algorithms that you learned from 1st through 4th grade.
Start with a column, then tens, etc.

Answer 12

If your target architecture supports BCD (binary coded decimal) representation of numbers, you can get some hardware support for multiplying / adding the long finger you need to do. Getting the compiler to retrieve the BCD instruction is what you will need to read ...

Motorola 68K chips had that. Not that I'm bitter or anything else.

Answer 13

My beginning would be to have an array of arbitrary integer sizes, using 31 bits and 32n'd as an overflow.

The starter op will be ADD and then MAKE-NEGATIVE using 2 add-ons. After that, subtraction proceeds trivially, and as soon as you have add / sub, everything else is doable.

There are probably more complex approaches. But that would be a naive approach from digital logic.

Answer 14

You can try to implement something like this:

http://www.docjar.org/html/api/java/math/BigInteger.java.html

You only need 4 bits for a single digit 0 - 9

Thus, the Int value must contain up to 8 digits. I decided that I would stick with an array of characters, so I use dual memory, but for me it is used only once.

Also, when storing all the digits in a single int, this complicates it and possibly even slows it down.

I don't have speed tests, but looking at the java version of BigInteger, it looks like it is doing a lot of work.

For me I do below

 //Number = 100,000.00, Number Digits = 32, Decimal Digits = 2. BigDecimal *decimal = new BigDecimal("100000.00", 32, 2); decimal += "1000.99"; cout << decimal->GetValue(0x1 | 0x2) << endl; //Format and show decimals. //Prints: 101,000.99 

Answer 15

a bit late answer, you can find various bigint in c ++ here:

https://github.com/topics/bigint

Answer 16

subtract 48 from your string and type to get the big digit number. then do the basic math operation. otherwise, I will provide a complete solution.

Answer 17

C ++ class BigInt, which allows the user to work with integer integers. http://sourceforge.net/projects/cpp-bigint/