Public Group

Huge Numbers class

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

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 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 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 on other sites
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.

Share on other sites
Quote:
 Original post by b2b3Maybe 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 on other sites
Quote:
 Original post by huntaIf 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 b2b3Maybe 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 on other sites
(edit: I guess I'm not fast enough when I type code...)

Quote:
 Original post by ShaiWhat 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 arrayIs 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 : positivebigint r, a, b;int carry = 0;r.reserve(max(a.size(), b.size()));for (size_t i=0; i<r.size(); i++) {  // each v is in the range 0..999,999,999  // the [] operator should return 0 if i > size()  // if we want to be mathematically correct  r = a + b + carry;  // therefore, there is an overflow when they   // go after 1,000,000,000  if (r >= 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; }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) + 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 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.

1. 1
Rutin
26
2. 2
3. 3
4. 4
JoeJ
18
5. 5

• 14
• 21
• 11
• 11
• 9
• Forum Statistics

• Total Topics
631763
• Total Posts
3002188
×