# Big number implementation.

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 04-06-2006
apacz
Big number implementation.
Hi,
I have to implement a class to represent the integer numbers which can be 30 digits long. I though about representing them as a 2 integers of long long, like for example:
Code:

```class bn { public:         long long      a,                         b; };```
and then just to read the number from the input as a string, check if it is > 15 digits long, if it is, then transform first 15 digits by atoi() to the 'a' and then the rest of the numbers to the 'b'. But I have the problem with leading zeros with the rest of the strings (for example to number 10^30 - in the 'a' there will be stored 10^15 and in the 'b' 0), I don't know how to deal with them. Of course I can remember in a variable the number of leading zeros but it would be slow. Only thing which I need in them is the fast comparison of big numbers. Can anyone help with solving this problem with a good efficiency ?
--
Regards,
apacz
• 04-06-2006
laserlight
Quote:

I don't know how to deal with them. Of course I can remember in a variable the number of leading zeros but it would be slow.
You only need to care when printing, so at that point you find out just how many digits it would occupy in base 10, and then pad with leading zeros.

Have you considered just using GMP?
• 04-06-2006
apacz
Well, not only with printing but also with comparison and that's the problem. I need to do this as fast as it is possible. Because I need only 30 digits long numbers to remember, and I will only have to compare them, without any arithmetical calculations I want to it to code it on my own :).
--
Regards,
apacz
• 04-06-2006
laserlight
Quote:

Because I need only 30 digits long numbers to remember, and I will only have to compare them, without any arithmetical calculations I want to it to code it on my own
I dont see a problem. Your internal representation is in long long (non-standard in C++, if I remember correctly), so there are no leading zeros to speak of (unlike if you use say, a string).
• 04-06-2006
apacz
Let's say we have a number 10^30. in the 'a' there will be 10^15 and in the 'b' there should be stored something like 15 zeros. But they can not be because it's hard to keep 15 '0' in the number type (in 'b' will have the value 0 so the whole number will be 10^16).
--
Regards,
apacz
• 04-06-2006
n3v
there's another clever little system you can use. it's called a 'letter array'. put the number into a char array, but with a really high uh.. whats the word.. ah, a really high number base. for example, our normal counting has base 10, and hexidecimal has 15, and binary has 1. that means, when the amount of the number gets to that point, it adds on another place holder. for example, here's some numbers written with different bases:

normal: 11
binary: 1011
hex: B

hexidecimal, as you probably know, after the number 9, uses letters A-F, going to 15. after 15, it adds a new place holder.

anyway, the idea of a letter array is to convert the number into a number system with a base of 30 or so, using letters like in hex. you could use 0-9, then after that, extend it with a-z, or even other symbols, as long as you tell the computer what number each symbol represents. it's all the same to the computer; computers read hex just fine. this way you could stick a very very large number into the c string. lets say you make a number base of 30. 15 digits in this system could hold up to the number 14348907000000000000000, a 23-digit number. you could make your character array have a base of 40 or even 95 if you used other symbols like ä and ö, and distinguished between capitol and lower-case letters.

coincidentally, 15 digits in a base 95 numeric system can hold 30 digits, up to the number 463291230159753366058349609375. the number of digits in the base 95 numeric system don't really matter though, cause it'll be an array, and more than 15 won't hurt an array.

this works great implemented as a class, and you can do all kinds of mathematical equations on the huge numbers that way. also, if this is for some class, your program will work the most efficiently, and your teacher will probably give you some 1337 points.
• 04-06-2006
laserlight
Quote:

Let's say we have a number 10^30. in the 'a' there will be 10^15 and in the 'b' there should be stored something like 15 zeros. But they can not be because it's hard to keep 15 '0' in the number type (in 'b' will have the value 0 so the whole number will be 10^16).
That's not true. Let's work with base 100 instead.

If you want to convert "1" to base 100, you get [0][1]
If you want to convert "20" to base 100, you get [0][20]
If you want to convert "300" to base 100, you get [3][0]
If you want to convert "4000" to base 100, you get [40][0]
If you want to convert "5060" to base 100, you get [50][60]

In your case, you are working with base 1E16, i.e. the largest value you can have in a single 'limb' (e.g. a or b) is 10^16-1. That number is 15 digits long.

Quote:

there's another clever little system you can use. it's called a 'letter array'. put the number into a char array, but with a really high uh.. whats the word.. ah, a really high number base. for example, our normal counting has base 10, and hexidecimal has 15, and binary has 1.
n3v, apacz is doing almost the same thing, but much a much larger base.

Quote:

that means, when the amount of the number gets to that point, it adds on another place holder.
apacz only needs fixed precision, not arbitrary precision.

Quote:

coincidentally, 15 digits in a base 95 numeric system can hold 30 digits, up to the number 463291230159753366058349609375. the number of digits in the base 95 numeric system don't really matter though, cause it'll be an array, and more than 15 won't hurt an array.
apacz's current implementation uses just 2 digits.

Quote:

this works great implemented as a class, and you can do all kinds of mathematical equations on the huge numbers that way. also, if this is for some class, your program will work the most efficiently
With the same algorithms, apacz's current implementation is likely to be (much) more efficient than yours.
• 04-06-2006
n3v
Quote:

With the same algorithms, apacz's current implementation is likely to be (much) more efficient than yours.
i kinda doubt that. he was originally thinking about using two long numbers.

also, i have some misunderstandings about your current implementation. your base 100 situation seems to be able to hold only a limited amount of numbers. i'm kinda confused about the way you presented it as well.
would it be implemented as a two-dimensional matrix or two seperate matricies or what? i just dont see how it would really work.

edit:

Quote:

Quote:

coincidentally, 15 digits in a base 95 numeric system can hold 30 digits, up to the number 463291230159753366058349609375. the number of digits in the base 95 numeric system don't really matter though, cause it'll be an array, and more than 15 won't hurt an array.

apacz's current implementation uses just 2 digits.
how exactly would two digits hold the value of 463291230159753366058349609375?
• 04-06-2006
laserlight
Quote:

your base 100 situation seems to be able to hold only a limited amount of numbers.
Yep, if we were to use only 2 limbs/'digits', then the range would be [0,1000). Of course, we could remove the restriction on just 2 limbs, but then apacz doesnt want to implement arbitrary precision arithmetic, apparently.

Quote:

would it be implemented as a two-dimensional matrix or two seperate matricies or what?
Just 2 integers, or perhaps a vector of integers if arbitrary precision is required.

EDIT:
Quote:

how exactly would two digits hold the value of 463291230159753366058349609375?
If we worked in base 463291230159753366058349609376, just one 'digit' is needed.
After all, in base 10, how exactly would two digits hold the value of ten?
• 04-06-2006
n3v
ah, i get what you mean. so, you're saying that my system was too robust for what he needed? granted, if all he wants to do is compare big numbers, he doesn't need to bother in the process of figuring out a way to convert the numbers quickly into some odd base number.

my system works pretty well for finding the greatest prime factor in huge numbers though. problem is, when the number gets really big, it could take thousands of years to get a result though. literally.
• 04-06-2006
laserlight
Quote:

so, you're saying that my system was too robust for what he needed?
Your 'system' is a variant of the one I described, except that it is restricted to a smaller number base, and isnt very efficient at all.

Quote:

granted, if all he wants to do is compare big numbers, he doesn't need to bother in the process of figuring out a way to convert the numbers quickly into some odd base number.
Well, it depends. With only two 'digits' comparison of the number requires the comparison of just two integers... but it comes at the cost of conversion, so presumably there is some reason why apacz wants to implement it this way. If only comparing is needed, then the solution would be not to convert at all, but to compare the numeric strings immediately.

Quote:

my system works pretty well for finding the greatest prime factor in huge numbers though. problem is, when the number gets really big, it could take thousands of years to get a result though.
Try the GMP, but of course it too is limited by physical constraints.
• 04-06-2006
n3v
yeah, i've seen the gmp, i've done something similar once, but gave up when i figured out that they probably did it way better than i did.

you said my previously mentioned idea wasn't very effective. i still don't really see how yours would work. can you explain how the input number would be converted?
• 04-06-2006
laserlight
Quote:

i still don't really see how yours would work.
Roughly the same ideas as from the GMP, though far less sophisticated.

Quote:

can you explain how the input number would be converted?
How would you convert with yours? The same ideas can be applied.
• 04-06-2006
apacz
Quote:

Originally Posted by laserlight
If you want to convert "4000" to base 100, you get [40][0]

Yes. And that's the problem I see. You have in first variable 40 and in the second 0. So now your number is 400. You've lost the leading zero. How to handle it ?
--
Regards,
apacz
• 04-06-2006
laserlight
Quote:

You have in first variable 40 and in the second 0. So now your number is 400. You've lost the leading zero. How to handle it ?
Pad the output of the second variable with leading zeros. Should be no problem with <iomanip>
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last