what if I want to represent a huge number such as 2^100 to a two's complement, an int definitely can't handle this....
Printable View
what if I want to represent a huge number such as 2^100 to a two's complement, an int definitely can't handle this....
There are a lot of large number libraries out there. Some open source ones, and lots of people have their own home made ones.
My own one is one that stores the binary data in exactly the same way a processor that could handle that number size would, if that's what you're asking.
I need to implement my own using a vector, and then store digits.... is there any implementation out there that does this?
I read one in a book once that used a vector. It's really just a matter of deciding what base you're gonna use and then getting started.
What operations do you need to support? It may seem hard at first, but once you get started you'll find that addition at least isn't so hard.
Just make sure you store things least significant value first, that way you can extend it using a simple push_back rather than having to manually resize and move the contents.
Operations are +, - and * and bit shifting.. I guess the bit shifting would be easy as it is just shifting elements/bits in the vector... my only problem right now is how to convert those very long string (which is a rep. of a very large integer) to it's two's complement form in bits... or do you guys have any other ways of representing large integer besides a string?
I already have a constructor that takes an int and int64 and convert those to two's complement form (store it as bits in my vector)... but what if I want to go with a larger number than an int64? use a string? or what? I would really like to avoid storing my base 10 digits (0-9) in my vector... I would like to store bits (1/0) in two's complement as it's easier to do the operations with that form
You just store it like a long number with more than 64 bits. For instance:
Now for a real implementation you will use a resizable vector of ints or longs, but the idea is the same.Code:char array[2] = {'\0xFC', '\0xFF'}; //represents FFFC which is -4
Creating a constructor may be tricky, because you need to decide how a user may specify a large number without using you large number class. But you can just implement a stream reading operator, and not worry about it.
basically what I want to do is the following:
example:
52 to result in
00110100
not
00000101 00000010
where 52 is a string here ("52"), not an int... so that I can do this for arbitrary long string
To store a stringified number in there, you just need to
- Start with the value of 0
- Multiply by 10
- Add the next digit
- If there are any more digits, repeat from step 2
So it turns out that you probably need the multiplication function anyway. That's the funny thing about large number libraries, several of the operations build themselves upon other operations. In fact they almost didn't need to tell you to implement the bitshifts either, because you'd most likely have implemented them anyway for use within the multiplication function.
You could implement the multipliction by 10 as a special case if you wanted. It' eqivalent to (x<<3) + (x<<1) which is particularly useful if you didn't need to also implement multiplication.
If you have to convert the number back into a string then it gets harder because then you're forced to implement division as well.
I wrote a simple large num lib that used strings and just wrote methods that employ traditional arithmetical (long addition, long division, etc).
I used stringstream and atoi to translate between chars/ints for the algorithms.
For example, the algorithm for addition looked like this;
Carry + A + B = C.
I would determine what to store and carry from C by turning the int in to a string (stringstream).
Where M = length of the string;
Store C[M-1], Carry C[0,M-2] (I would translate the Carry back to an int with atoi(string.c_str())).
So 123 + 678 would look like this;
0 + 8 + 3 = 11 -> Store 1, Carry 1
1 + 7 + 2 = 10 -> Store 0, Carry 1
1 + 6 + 1 = 8 -> Store 8, Carry 0
> (Reverse the string chars)
123 + 678
Result = 801