Thread: Big number implementation.

  1. #1
    Registered User
    Join Date
    May 2005
    Posts
    76

    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

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    May 2005
    Posts
    76
    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

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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).
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    May 2005
    Posts
    76
    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

  6. #6
    irregularly symmetrical n3v's Avatar
    Join Date
    Mar 2006
    Location
    Finland
    Posts
    67
    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.
    Last edited by n3v; 04-06-2006 at 06:58 AM.

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.

    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.

    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.

    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.

    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    irregularly symmetrical n3v's Avatar
    Join Date
    Mar 2006
    Location
    Finland
    Posts
    67
    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:

    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?
    Last edited by n3v; 04-06-2006 at 09:46 AM.

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.

    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:
    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?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    irregularly symmetrical n3v's Avatar
    Join Date
    Mar 2006
    Location
    Finland
    Posts
    67
    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.

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.

    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.

    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    irregularly symmetrical n3v's Avatar
    Join Date
    Mar 2006
    Location
    Finland
    Posts
    67
    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?

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    i still don't really see how yours would work.
    Roughly the same ideas as from the GMP, though far less sophisticated.

    can you explain how the input number would be converted?
    How would you convert with yours? The same ideas can be applied.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    Registered User
    Join Date
    May 2005
    Posts
    76
    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

  15. #15
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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>
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 11-23-2007, 01:48 PM
  2. Stone Age Rumble
    By KONI in forum Contests Board
    Replies: 30
    Last Post: 04-02-2007, 09:53 PM
  3. Big number question
    By C of Green in forum C++ Programming
    Replies: 4
    Last Post: 01-11-2007, 12:06 PM
  4. Perfect number...
    By Argo_Jeude in forum C++ Programming
    Replies: 8
    Last Post: 07-12-2005, 01:53 PM
  5. Big help for big program
    By Mahesh in forum C Programming
    Replies: 1
    Last Post: 05-04-2005, 10:02 AM