Click here to Skip to main content
15,885,919 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
Is there any way in c++ or c to write a data type which accepts unlimited range of value?
if yes
please tell me how in detail?
e.g a UnlimitedType a;
a=(1024*1024*1024*1024*(Factorial(100000));
Posted

Hi,
The answer is yes, it can be built. One of the ways is storing the integer signature in a linked-list of bits, thus adding dynamically new bit as the number increases. Operation on this types are performed using bit math, thus you'll have to implement primitive addition, subtraction, multiplication, division, pretty much how it is done on assembly level (see implementing look ahead carry adder - http://cppgm.blogspot.com/2008/01/c-program-look-ahead-carry-adder.html[^]. Of course simple math on big numbers will increase processing time greatly, so I would really think of reviewing this kind of specifications.
Regards
 
Share this answer
 
Comments
Vijay Vishwakarmar 26-Apr-11 10:16am    
Thanks!
it looks to be good way of writing such kind of data type.
But I would like to know the use of int_64 keyword to write such data type
Albert Holguin 26-Apr-11 10:28am    
int64 is a 64 bit integer, it is limited like any other data type... in order to build a "limitless type" you would have to make a class to handle that, because you would most certainly have to override the operators.
Sergey Alexandrovich Kryukov 26-Apr-11 12:41pm    
I don't see where Ciumac offered using Int64. The answer is about linked list of bits (and it can be implemented using linked list of Int64 values for internal representation).

My 5 for this answer.
--SA
Albert Holguin 26-Apr-11 12:48pm    
My reply wasn't for ciumac, it was a reply to vijay...
Sergey Alexandrovich Kryukov 26-Apr-11 19:40pm    
I got it now, sorry for confusion. Anyway, as I say "a linked list of Int64" can do the job, but the idea of Stefan must be better, how do you think?
--SA
Basically, what you need to do is define a class that contains some kind of representation for your number, and then a set of math operators that let you do actual calculations with operands of this class, or mixed calculations between standard types and operands of this class.

For your representation, the above suggestion to use some kind of bit-array seems inefficient IMHO. You'll probably get faster code using std::vector<unsigned int>.

Here's a quick hack showing what I have in mind - there's a lot missing, but I hope you get the idea:
class CBigInt {
private:
   int sign;
   std::vector<unsigned int> mantisse;
   void expand(std::size_t size) { // expand mantisse to new size
      if (size > mantisse.size()) {
         std::size_t old_size = mantisse.size();
         mantisse.resize(size);
         for (std::size_t i = old_size; i < size; ++i)
            mantisse[i] = 0;
      }
   }
public:
   CBigInt(int i) : mantisse(1) { // initialize mantisse at length 1
      mantisse[0] = iabs(i);
      sign = (i>0 ? 1 : (i<0 ? -1 : 0)); // added redundand braces for sake of readability
   }
   CBigInt(const CBigInt& other) : mantisse(other.mantisse), sign(other.sign) {
      // copy constructor
   }
   CBigInt& operator+=(const CBigInt& other) {
      // initialize temporary to hold result
      CBigInt newValue(0);

      // estimate required size for result
      std::size_t size(mantisse.size());
      if (other.mantisse.size() > size) {
         size = other.mantisse.size();
      }
      if (other.sign == sign)
      newValue.expand(size);

      // calculate new value, using carryover temporary
      unsigned int carry(0);
      if (sign == other.sign) {
         newValue.sign = sign;
         ++size; // carryover may require to increase the size by 1 digit
         for (std::size_t i = 0; i < size-1; ++i) {
            // add carryover
            if (UINT_MAX-mantisse[i] < carry) { // does carry+mantisse[i] exceed UINT_MAX?
               // new digit = carry + mantisse - (UINT_MAX + 1)
               newValue.mantisse[i] = (carry - (UINT_MAX - mantisse)) - 1; // stay within the bounds of UINT
               carry = 1;
            }
            else {
               newValue.mantisse[i] = mantisse[i] + carry;
               carry = 0;
            }
            // add digit from second number
            if (UINT_MAX-newValue.mantisse < other.mantisse[i]) { // does addition exceed UINT_MAX?
               newValue.mantisse[i] = (other.mantisse[i] - (UINT_MAX - newValue.mantisse[i])) - 1;
               ++carry;
            }
            else {
               newValue.mantisse[i] += other.mantisse[i];
            }
         }
         if (carry > 0) {
            newValue.mantisse[size] = carry;
         }
         else {
            --size; // highest order digit not required
         }
      }
      else {
         // different signs
         // TODO: subtract values
         // ...
      }

      // copy results
      sign = newValue.sign;
      mantisse.resize(size);
      for (std::size_t i = 0; i < size; ++i) {
         mantisse[i] = newValue.mantisse[i];
      }
   }
};
CBigInt operator+(const CBigInt& op1, const CBigInt& op2) {
   return CBigInt(op1) += op2;
}

As you can see, even a simple operator can be tricky to implement, especially when you deal with digits containing more than just a single bit. And I'm not even sure I covered all cases - I didn't try to compile this, much less test this code.
 
Share this answer
 
v3
Comments
Sergey Alexandrovich Kryukov 26-Apr-11 12:47pm    
I did not test it, but it looks reasonable (and impressive). My 5, anyway.
Also, std:vector is probably better than "linked list of bits" (suggested by Ciumac) in terms of performance.
--SA
Vijay Vishwakarmar 26-Apr-11 23:44pm    
It works well.
thank you
Sergey Alexandrovich Kryukov 27-Apr-11 0:02am    
Good. Would you formally accept Stefan's answer then? (A green button.)

Hi, Stefan! Good job!
--SA
Albert Holguin 27-Apr-11 0:37am    
I believe the performance enhancements in vector come from allocating data ahead of time, so its intended to improve on allocation time, the performance improvement would only be noticeable if this "infinite number class" is constantly changing size... just a thought...
Sergey Alexandrovich Kryukov 27-Apr-11 1:18am    
Such considerations should really depend on the usage pattern. High-volume calculations with typically fast growth of the size of such numeric object is one thing (remember the question -- factorial is the example) is one thing, long calculation circulated mostly in the same range of object sizes -- another.
--SA
 
Share this answer
 
Comments
Vijay Vishwakarmar 26-Apr-11 10:09am    
Ya, I Have checked and found useful but I want to know it how to write these type of data types
Sergey Alexandrovich Kryukov 26-Apr-11 12:45pm    
My 4. These methods are for large numbers still limited at the time of construction. They can be re-worked in unlimited using some wrappers re-constructing them on demand -- not very easy or effective. At the same time, the problem is solvable. Look at .NET Framework 4.0 System.Numerics.BitInteger -- it is truly unlimited (limited only by available system memory).
--SA
Vijay Vishwakarmar wrote:
Is there any way in c++ or c to write a data type which accepts unlimited range of value?

Of course you CANNOT do that on a real (finite) computer: you should accept a kind of trade-off on your 'unlimited range' definition.
:-)
 
Share this answer
 
Use System.Numerics.BigInteger
 
Share this answer
 
Comments
Cyrus Neah 26-Apr-11 19:54pm    
SAKryukov already gave this answer. Sorry!
Albert Holguin 26-Apr-11 23:22pm    
he's fast! :)

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900