Large integers in C++

[AxessTerminated]

How do programs in C++ allow lengthy integers? __int64 is only 64-bit, any way of getting a larger one without creating my own number class?

some sort of example:


__int64 number;
cout << "Enter number: ";
cin >> number;




i want the variable "key" to be able to accept larger integers than what's allowed by int64.
thanks.

A_T

[The Duck]

Well, I'm still very new to C++ but have you tried the "long int" and/or "signed long int" ranges?

[AxessTerminated]

yes, __int64 is the largest that i know of, duck.
unsigned long is next to last in the integer market, thanks for trying though.



A_T

[albn]

This may help you:

http://www.shoup.net/ntl/

It is under the GPL, and supports arbitrary length integers. From the site:

http://www.shoup.net/ntl/doc/tour-ex1.html

There are many other routines. Here is a brief summary:

GCD -- computes greatest common divisor of two integers
XGCD -- extended Euclidean algorithm
AddMod, SubMod, NegateMod, MulMod, SqrMod, InvMod, PowerMod -- routines for modular arithmetic, including inversion and exponentiation
NumBits -- length of binary representation
bit -- extract a bit
ZZFromBytes, BytesFromZZ -- convert between octet strings and ZZs
RandomBnd, RandomBits, RandomLen -- routines for generating pseudo-random numbers
GenPrime, ProbPrime -- routines for generating primes and testing primality
power -- (non-modular) exponentiation
SqrRoot -- integer part of square root
Jacobi, SqrRootMod -- Jacobi symbol and modular square root
Most of these functions also have pure long versions as well, and as usual, there are both functional and procedural variants.

Another you might want to try:

http://www.swox.com/gmp/

Hope this helps.

[The Duck]

so it's next to last!? So basically "_int64" is the largest in the integer market? I'm reading this book and so far it hasn't even mentioned _int64, I guess I should just keep on reading...

[Travish]

Since you're in C++, I think it's best to create your own large integer class (e.g. CVeryLargeInt). The CVeryLargeInt can daisy chain several int64 encapsulated in a class conatining an ibt64 and a int position, which will be the position in the number. The daisychaining is done through aggregation.
The very big downside to this solution is that you will have to do some serious (operator overloading) implementation on all operations you want to do on these very large ints (e.g. overload the +, -, *, ...., off course you can write overloads using other overloads, e.g. write a * using the +).

What do you need these large numbers for anyway? And how important is precision in your large numbers? I would go for floats, if possible, since it's very rare that precision is important using such large numbers.

[slarty]

Isn't there the Gnu arbritary precision maths library?

By which I mean, it can handle ints as big as you have enough memory for (and do operations on them)

Slarty

[cacosapo]

As a basic support, languages use to support only structures that can be represented directed on hardware. Thats why you can see only those format. To represent a large integer (lets say 1000 digits with precision of 1000) you need to simulate it. You can see this "simulation" on math libs or a direct look on some prime number generator routines.
Look for "RSA" routines and you will see large prime generators ---

[AxessTerminated]

To quench your curiosity, this is all related to RSA..
Also, Duck, I have found that the Intel Compiler supports 128-bit integers natively. Also, very few newbie books (you seem like your new to C++) say anything about __int64, because it isn't a standard in C++...It was first a VC++ thing, but now many other compilers support some sort of 64-bit integer. The Intel Compiler has i64,and i128...or something similar, but it has both 64-bit an 128-bit.

I'm still relatively new to C++ as well. I've written quite a few useful apps, but I learn everything on the fly, so I'm still very shaky on classes, and have no clue how to overload and all that good stuff. I was looking for an "easy way out", because my friend has begun to write his own integer class that will accept up to 4096-bit integers...yes, he is, in fact, insane.

A_T

[SerpentSin]

Well, even if there is a built-in way of declaring integers larger than __int64, if you're dealing with bignums, you'll eventually run into a problem where you'll need something larger than 128bits, or say, your friend's 4096-bit integer class. That's where the power of C++ kicks in, once you dominate all the class-bulding techniques you'll have no limits to the size of your ints.
I suggest you get to learn about classes and operator overloading now, because, eventually you'll have to learn it anyway. Of course, you can always google for a pre-built large-integer class, if you don't want to build one yourself or dig into the deep C++ details. Anyway, in my opinion the best place to get to learn gory C++ details is in Bjarne Stroustrup - The C++ Proggraming Language 3rd edition. Bjarne Stroustrup is the author of C++.