Share On Twitter Facebook Google+ LinkedIn Pinterest Tumblr Reddit
Question

What kind of data type can be used to store an infinitely large integer in C++?

Tags: C (programming language) Data Structures C++ (programming language) Integers Data Types
Date:
Status:Resolved
Question Id:61
Answer
Date:
Correct:No

There is no such thing as infinite.

If you want integers larger than the C++ implementation supports with built in types, use an arbitrary precision library. Then you can make integers limited only by memory.

 

Introduction - 1.62.0
The Multiprecision Library provides integer , rational and floating-point types in C++ that have more range and precision than C++'s ordinary built-in types. The big number types in Multiprecision can be used with a wide selection of basic mathematical operations, elementary transcendental functions as well as the functions in Boost.Math. The Multiprecision types can also interoperate with the built-in types in C++ using clearly defined conversion rules. This allows Boost.Multiprecision to be used for all kinds of mathematical calculations involving integer, rational and floating-point types requiring extended range and precision. Multiprecision consists of a generic interface to the mathematics of large numbers as well as a selection of big number back ends, with support for integer, rational and floating-point types. Boost.Multiprecision provides a selection of back ends provided off-the-rack in including interfaces to GMP, MPFR, MPIR, TomMath as well as its own collection of Boost-licensed, header-only back ends for integers, rationals and floats. In addition, user-defined back ends can be created and used with the interface of Multiprecision, provided the class implementation adheres to the necessary concepts . Depending upon the number type, precision may be arbitrarily large (limited only by available memory), fixed at compile time (for example 50 or 100 decimal digits), or a variable controlled at run-time by member functions. The types are expression-template-enabled for better performance than naive user-defined types. The Multiprecision library comes in two distinct parts: An expression-template-enabled front-end number that handles all the operator overloading, expression evaluation optimization, and code reduction. A selection of back-ends that implement the actual arithmetic operations, and need conform only to the reduced interface requirements of the front-end. Separation of front-end and back-end allows use of highly refined, but restricted license libraries where possible, but provides Boost license alternatives for users who must have a portable unconstrained license. Which is to say some back-ends rely on 3rd party libraries, but a header-only Boost license version is always available (if somewhat slower). Should you just wish to cut to the chase and use a fully Boost-licensed number type, then skip to cpp_int for multiprecision integers, cpp_dec_float for multiprecision floating-point types and cpp_rational for rational types. The library is often used via one of the predefined typedefs: for example if you wanted an arbitrary precision integer type using GMP as the underlying implementation then you could use: #include < boost / multiprecision / gmp . hpp > // Defines the wrappers around the GMP library's types boost :: multiprecision :: mpz_int myint ;
Answer
Date:
Correct:No

A “byte” is a great data type for this task.

Why? Because it’s easy to buy memory modules that are 4 gigabyte or 16 gigabyte or whatever.

Obviously “infinite” is a big requirement - whatever computer you build, you would quickly run out of “infinite” memory.

But if you shrink your “infinite” demand into “damn big integer” then there are quite a number of big number libraries out there that does their work by using arrays of bytes or arrays of uint32_t or whatever they decided to use as base unit.

Your decimal integers are just a sequence of digits, each taking a value between 0 and 9.

But convert to base 256 and each digit would have a value between 0 and 255 - just exactly the same as you can fit in a byte.
So uint8_t num[128] can store a 128-digit integer in base 256.

And uint8_t num[1000000000] can store a 1 billon digit integer in base 256.

Answer
Date:
Correct:No

An infinitely large integer does not exist, as it would take infinitely large space to store and infinitely long time to write. Thus your question does not make sense.

Answer
Date:
Correct:No

Infinetetly integers do not exist. Every integer number is finite.

I guess that you mean arbitrary large integers. Ultimately the best method is an integer array. It may be wrapped by a class, but it still is an integer array. You may declase it char or byte arrays, but these are also sort of integers.

Answer
Date:
Correct:No

In Java “java.util.BigInteger” is an int[] that is as big as is necessary to perform the Knuth arbitrary integer precision math.. (using 64bit intermediate math stages). Similarly there is a “BigDecimal” for floating point.

Python has a very common version of the above through a C++ library. numpy or something like that.

Rust has a couple competing libraries for when I’ve needed the above..

I’ve never needed it for C++, but I’m sure you can find a header-only library on github if you search.

For me, the biggest issue was in saving/restoring.. In Java, for example, if you use byte[], then it has to marshal/unmarshal the datablock.. You can instead use int[] ins and outs, but they can’t directly mem-map to a file - ideally it would have used IntBuffer as it’s native representation.

Python, I’m sure has similar issues with serializing/deserializing.. A 1GB integer is very expensive to save/restore - ideally you’d have mem-map capability.

A peculiar reason why the above might matter is an arithmatically encoded bitmap. You rarely perform a multiply/divide on a 1 million digit number, but then need bit-offsets at read time.. It sucks to have to read in 4MB just to read in 1 bit (or rather a single 4096byte block-cache-line).

But that’s probably a rare use-case. And any uint32_t[] or even uint16_t[] based library should be good enough in C++.

Answer
Date:
Correct:No

C++ doesn’t have a specific data type built-in so relies upon libraries for anything outside of the defined language (to keep it smallish). There are an abundant supply of arbitrary precision class libraries available (free online or for purchase); I’ve personally leveraged Apfloat (source code for C++ and Java), Boost and the speedy GMP . For basic math functions, modern processors readily support multi-word integer or fixed-point arithmetic so implementation is not difficult.

The floating point standard actually has a constant defined to represent infinity. This technique can also be emulated with multi-precision integers by reserving a bit pattern/number at the extreme end of its allowable range (i.e. all one bits with or without the sign, all zeros except the sign bit) or an external flag. The data type used is often an unsigned int vector or char array or dynamic string on the heap or another variety depending upon the ultimate goal (e.g. supported math functions). What’s more interesting is whether the internal representation will be binary or decimal or some other base; it all depends on what’s planned for your very large numbers. It’s up to you whether an existing library helps or you decide to roll your own for a special purpose.

Is your next question what’s the data type for complex numbers? How about C++ support for linear algebra or symbolic equation evaluation or statistical functions?

Answer
Date:
Correct:No

Re “What kind of data type can be used to store an infinitely large integer in C++?”: None, in C++ or any other language. Storing an infinite amount of data would require an infinitely-large universe. But our universe is finite, so it can hold only a finite amount of data.

Don’t get me wrong, I’m not saying our universe is small; it istn’t! The part of our universe which we can observe is a sphere about 100 billion light years wide. The total universe is estimated to be about 250 times larger, a sphere about 25 trillion light years wide. So the volume of this universe is approximately 1.5x10^40 cubic light years. That’s pretty darn huge! But compared to “infinite”, it’s infinitely tiny.

If you meant to ask, “What kind of data type in C++ can store integers larger than 2^64?”, perhaps the best answer is the Boost extended-precision library, as others here have pointed out.

However, that’s not what I use. I use the Gnu Multi-Precision (GMP) library, because I like it’s interface better. It was intended to be used with C, but can also be used with C++. And while its main interfaces are C-style function calls, it also has some C++-style interfaces as well (though I haven’t yet used those). You can get GMP here: GMP

Answer
Date:
Correct:No

There is no built in type that supports that.

It would be either a string or some form of array/vector of multiple elements, with the appropriate custom operators.

And infinitely large probably also means you need infinite amount of memory, but I guess you just meant “as large as possible within the range of RAM available in the machine”.

Answer
Date:
Correct:No

The long long data type is overkill for just about every application, but C/C++ will let you use it anyway. It's capable of storing at least −9,223,372,036,854,775,807 to 9,223,372,036,854,775,807. I hope this helps.

Answer
Date:
Correct:No

Implement a class that supports the operations needed, I presume for integers, but that checks for your flagged infinite value that to handle it as required.

Answer
Date:
Correct:Yes

None, there is nothing on an actual computer that allows you to store an ininitelly large integer on any computer language known today. And I doubt that will ever exist.

now lets do an experiment.

lets assume your computer and OS and your program can run with 1 GB

your computer RAM has 4 GB, and your hard drive has 1TB

and lets assume this means 1028 Gb of memory in total but you used 1 for the program so that will be 1027 GB that is 1027 * 1024 * 1024 * 1024 * 8 in bits.

that is rather big number right? even that number is just 8821862825984. (quite long but not infinite and that is the number of bits your entire computer can have, with the hardware i said, the rest it needs it to run the program to set this large integer).

so now lets see using ALL that memory what is the max integer you can hold from 0 clearly.

and it is quite easy it is just 2^8821862825984

yes you can have ANY number from 0 to that amount.

which is equivalent on decimal (more or less) to 10^3^882186282599 (rounding up)

which in term is 10^2646558847797

so the MAX number from 0 as an integer you can hold with the ENTIRE memory+drive of that computer is no more than 10^2646558847797

clearly is a very big number but it is not even near from infinite than 0.

even so if you consider things in scale and we compare that the minimal scale is a neutrino

an electroni is in the scale of 10^−18 (of meter) and the neutrino is said to be millons of time smaller, so lets assume 10^-27 (not saying this values are ok).

now lets see the size of the observable universe.

8.8 × 10^26, so no more than 10^27

why i am calculating this because, if we say our “unit” of measure is a neutrino.

means the longest number we will ever need to measure ANYTHING on the observable universe, should be about 10^27/10^-27 (wonder why this values give the same exponent) and that is 10^54

so you can hold a number a lot of times bigger (and a lot really) than the size of the observable universe measured in neutrino, why you will need such a big number for?

and clearly you cannot do anything with it as, you do not have enough space to store a different one.

so as you see is not possible

Your Answer

Review Your Answer