Sign in to follow this  

Huge Numbers class

This topic is 4717 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

What would be the best way to go about writing a class that can contain 256 bits numbers and stuff? so far I'm reasoning like this: - Use a class with 8 unsigned ints in it and a flag to check for the sign - read the ints, store each individual number in array (eg. 230 would be char array = {2, 3, 0}) - add all the numbers in the same way you were taught when you were 8 - print all numbers of resulting array Is there a better way? and - since there probably is one - what is it? edit: i just realize I have no way of knwoing what to put in the integers this way. If I were to go "BigInt a = 555555555555555555" I'd need a way of knowing which part to store in int1, which part in int2,...

Share this post


Link to post
Share on other sites
If speed isn't important, you can make life easier by storing the "huge number" in a string and overload the *, /, +, -, ... operators, what is quite easy and self-explaining to implement.

Share this post


Link to post
Share on other sites
One way you could do it is treat the integers as if they were in binary. That way, the binary value of each integer could take up a part of a bigass binary number. You could then use your own custom routines to add / divide / whatever in binary.

I'm sure it's not the best way to do it, but it's what I came up with in 45 seconds.

Share this post


Link to post
Share on other sites
Quote:
Original post by b2b3
Maybe you can use arithmetic routines from Numerical recipes in C. There's one chapter about arbitrary precision math at the end of the book. You can modify code to work with your own class.

seems to be exactly what I'm looking for :)

Share this post


Link to post
Share on other sites
Quote:
Original post by hunta
If speed isn't important, you can make life easier by storing the "huge number" in a string and overload the *, /, +, -, ... operators, what is quite easy and self-explaining to implement.


Actually the huge number classes I usually see use this method - so I assume it is pretty fast as well as efficient. IMHO this idea is the best approach because you can theoretically have an unlimted number size - you would only be restricted with avaliable memory blocks. As for the opeators hunta's mentioned I've seen all of those impelemented - but I have no idea of how the * and / would work! Even if you had a struct with the 8 ints, performing * and / would be a challenge, but nevertheless it is possible. Feel free to choose what you want - but I think you will have the most flexibility and ease with the string method.

Quote:
Original post by b2b3
Maybe you can use arithmetic routines from Numerical recipes in C. There's one chapter about arbitrary precision math at the end of the book. You can modify code to work with your own class.


Rating++ for that great site!

- Drew

Share this post


Link to post
Share on other sites
(edit: I guess I'm not fast enough when I type code...)

Quote:
Original post by Shai
What would be the best way to go about writing a class that can contain 256 bits numbers and stuff?

so far I'm reasoning like this:

- Use a class with 8 unsigned ints in it and a flag to check for the sign
- read the ints, store each individual number in array (eg. 230 would be char array = {2, 3, 0})
- add all the numbers in the same way you were taught when you were 8
- print all numbers of resulting array

Is there a better way? and - since there probably is one - what is it?


Instead of a int256-to-char conversion, you should try to use larger integers. I'd go with ints (in the range 0..999,999,999) instead of chars (in the range 0..9). You can use a similar conversion code (256 bits in base 2 to n numbers in base 1,000,000,000)(*). Once you'll get that, The math won't change:


// a, b : positive
bigint r, a, b;
int carry = 0;
r.reserve(max(a.size(), b.size()));
for (size_t i=0; i<r.size(); i++) {
// each v[i] is in the range 0..999,999,999
// the [] operator should return 0 if i > size()
// if we want to be mathematically correct
r[i] = a[i] + b[i] + carry;
// therefore, there is an overflow when they
// go after 1,000,000,000
if (r[i] >= 1000000000) {
carry = 1;
} else {
carry = 0;
}
}
if (carry) throw bigint::exception::numberistoolarge;


Of course, this addition code is valid only for positive numbers. Managing negative numbers or substraction is not very hard - and is left as an exercise for the reader :)

Printing the resulting number is quite easy too:


std::cout << "number is: ";
for (size_t i=r.size(); i>=0; i--) {
std::cout << r[i];
}
std::cout << endl;


The thing is more complex when it comes to multiplication and divisions.



(*) the conversion code, while not very complex, is still not simple. I'm not even sure I got it right here (I did not test it).

int carry = 0;
for (size_t i=0; i<int256::maxindex; i++) {
__int64 v = __int64(i256[i]) + carry;
int i = int(v % __int64(1000000000));
r.push_back(i);
carry = int(v / __int64(1000000000));
}
if (carry) {
r.push_back(carry);
}


The code I wrote in this answer shows a strong resemblance between some classical stl container and the bigint class. This is intentionnal :) But take care to the [] operator - which needs to check the boundary and return 0 if the index is greater than the size of the number.

HTH,

Share this post


Link to post
Share on other sites
Drew_Benton: Thanks. I'm glad you like it [smile]

Shai: I think you can use bigger data type to store digits. You can use 32 bit integer - it will stil fit into 64 bit integer, if you multiply two 32 bit integers. I think this can speed up your class, because all modern processors work faster with 32 bit than smaller numbers.

Share this post


Link to post
Share on other sites

This topic is 4717 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this