1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Huge Number

Discussion in 'C++' started by techinspiration, Mar 25, 2010.

  1. techinspiration

    techinspiration New Member

    Joined:
    Feb 14, 2010
    Messages:
    54
    Likes Received:
    0
    Trophy Points:
    0
    I want to handle an extremely huge number in C++, in the order of more than 1000 digits. I know this is huge, but I am sure it can be done, but I don't know how Sad

    Do you guys know of any way I can do this? I have tried something else aswell, I converted the number into BCD (binary-coded digit) format, and I was wondering if there might be a way to convert that into pure binary form if the 1000+ digit thing doesn't work.

    Thanks
     
  2. creative

    creative New Member

    Joined:
    Feb 15, 2010
    Messages:
    87
    Likes Received:
    0
    Trophy Points:
    0
    Is BCD just a normal Base2 number system? Then it is basically pure binary anyway. It's just not binary with natibe hardware support.

    There are pre-written libraries out there that can handle LARGE numbers, but I've never had an actual need for them.


    Can you elaborate on what you want to do with these numbers?
     
  3. meyup

    meyup New Member

    Joined:
    Feb 15, 2010
    Messages:
    102
    Likes Received:
    0
    Trophy Points:
    0
    It depends on what precision you need. Floats can store very big values, but not with the precision of 128bit integers. If you don't need the precision, then use floats (or doubles) which will be simple to implement. Otherwise, as already suggested, find a big integer library. There are plenty of them floating around :D
     
  4. techinspiration

    techinspiration New Member

    Joined:
    Feb 14, 2010
    Messages:
    54
    Likes Received:
    0
    Trophy Points:
    0
    Thanks for all the help. Basically what I want to do is convert a 1401 digit number into pure binary. BCD isn't pure binary because it stores each character in a 8 bit binary string, for example:

    0 = 00000000
    1 = 00000001
    2 = 00000010

    etc...

    So if you were to write 12 in BCD, it would be 0000000100000010, there are packed versions of BCD so that you can store 2 digits into a 8bit string, but I don't need that.



    It was suggested by a friend of mine, that I handle the number as a string and do long division on it.

    And of course this has to be a precision operation, so a float or double wouldn't work.
     
  5. meyup

    meyup New Member

    Joined:
    Feb 15, 2010
    Messages:
    102
    Likes Received:
    0
    Trophy Points:
    0
    Is your ultimate objective then to find these really long primes? Or maybe to find DVD codes? If it is to find DVD codes, there is an easy way - ask and all will be revealed ...

    If you want to find primes, then I'd think that the way you represent the numbers depends on your algorithm. Otherwise you can just write your own library that uses strings to represent numbers and write functions that will add, subtract, multiply and divide strings.

    I would not really recommend using such a string library though for finding primes, as it would be extremely slow where you really want some code that will run really fast.
     
  6. techinspiration

    techinspiration New Member

    Joined:
    Feb 14, 2010
    Messages:
    54
    Likes Received:
    0
    Trophy Points:
    0
    Well, this is just a challenge for me, I have learnt that I can learn a new language much better by getting some sort of challenge and then working on it. And since I am already a proficient PHP coder and VB programmer, I have found that this is the best way for me to learn C++.

    Basically I want to change that prime number into its binary form, and then save it as a .gz file, then the contents of that file would be the source code of the program they show. I am not going to use it, I just think it is an interesting project.

    I have written a small function that uses a string representation of a number, and then divides it. But I can't figure out how to make the function return an array, like in PHP you would simply say
    Code:
    $avar['1'] = 4;
    $avar['2'] = 3;
    return $avar
    
    but I don't know how to do something similar in C++, if I can, then it would cut the execution time of my code in half.
     
  7. techinspiration

    techinspiration New Member

    Joined:
    Feb 14, 2010
    Messages:
    54
    Likes Received:
    0
    Trophy Points:
    0
    Ohh, here is the function btw.
    Code:
    string longDiv(string input, int divisor) {
       
       int i = 0;
       string part;
       int partof;
       int a,b,c = 0;
       string answer = "";
       string partansw;
       string newdiv = "";
    
       newdiv = input.substr(0,1);
    
       for (i = 1; i <= input.length(); i++) {
          part = input.substr(i,1);
          a = convertToInteger(newdiv) / divisor;
          b = a * divisor;
          c = convertToInteger(newdiv) - b;
          newdiv = stringify(c) + part;
          answer += stringify(a);
       }
       return answer;
    
    } 
    When that loop is done, then 'answer' contains the divided number in a string, and 'newdiv' would contain the remainder, now I would like to return the answer, 'newdiv' and the length of the answer in an array. How would I do that, and how would I get the vars from the main program when the results are returned. I know the declaration of the function will have to change Razz

    It divides the number by means of long division btw.
     
  8. meyup

    meyup New Member

    Joined:
    Feb 15, 2010
    Messages:
    102
    Likes Received:
    0
    Trophy Points:
    0
    Have you declared type string? If not, just use "char *" instead of string.

    void longDiv(string *result, string input, int divisor)

    I've set the return type as void. Change this to int if you maybe want to return an int. For strings, I just find it best to work with passing by reference (google the term!).

    Then, at the end, copy the result stored in your answer variable into "*result". It's important that result be passed as a pointer otherwise you won't see the result outside of the function.

    Any other variables that you want returned can also be returned by passing a pointer as parameter to the function. You may also change the "void" to "int" to return an int result like maybe your result's length.

    Please excuse if the above doesn't make sense! It's been a looooong day.
     
  9. techinspiration

    techinspiration New Member

    Joined:
    Feb 14, 2010
    Messages:
    54
    Likes Received:
    0
    Trophy Points:
    0
    I understand what you are saying, I learned some C++ a long time ago, but I got stuck at pointers Embarassed
    But after doing some VB programming I understand what you mean by pass by reference.
    I did declare it as a string, which do you think is better, char * or string?

    btw I found this place
    further down the page you will see problems. These problems can be solved with either, C, C++, Pascal or Java. The problems are very interesting, and you can submit your code to the site for immediate evaluation by some script. The script is pretty accurate, but one suggestion is that you use
    'using namespace std'
    because it doesn't like the std:: prefix to all functions, and it also doesn't like it when you include unnessecary libraries.
    It also judges your code on the execution time and memory used, my solution to the first problem executes in 5 seconds and uses 440 bytes of memory, I have seen other people that execute the program in almost no time at all and use 64 bytes of memory, and I am too new to C++ to be able to optimise my code, so I am going to move on to the other problems and see what I can do Cool

    Thanks for all your help, I appreciate it a lot
     

Share This Page