Working with large integers
I want to do basic computations with arbitrarily large numbers
15 Replies  6901 Views  Last Post: 30 June 2008  12:11 PM
#1
Working with large integers
Posted 27 June 2008  08:07 PM
My apologies if this question is phrased in a way that is not specific enough.
I am learning c++ to write short programs that I can use to analyze numbers (in particular large primes)
My question is in two parts.
1. How do I get around the 2^31 power limit of integer operations in c++?
2. Is there a way to do exponents with integers, because with float, I loose even more precision, getting only 6 digits after converting back to integer.
I want to work with arbitrarily large numbers (i realize all computers have limits that grow exponentially as numbers get larger), but 2^256 at a minimum (2^1024 would be really nice).
I just want to make sure that i'm learning the correct language in the first place.
Should I be learning java instead?
Is there a simple command, or premade function that allows you declare an integer to be a larger size.
I know you can "teach" a computer to work with numbers larger than it is supposed to handle, but I have no desire to reinvent the wheel if there is already a nice command for this job.
I have searched, but can't seem to find anything to directly answer my question.
Signed,
Math is fun, programing sucks!
Replies To: Working with large integers
#2
Re: Working with large integers
Posted 27 June 2008  08:29 PM
Type Size Values unsigned short int 2 bytes 0 to 65,535 short int 2 bytes 32,768 to 32,767 unsigned long int 4 bytes 0 to 4,294,967,295 long int 4 bytes 2,147,483,648 to 2,147,483,647 int (16 bit) 2 bytes 32,768 to 32,767 int (32 bit) 4 bytes 2,147,483,648 to 2,147,483,647 unsigned int (16 bit) 2 bytes 0 to 65,535 unsigned int (32 bit) 2 bytes 0 to 4,294,967,295 char 1 byte 256 character values float 4 bytes 1.2e38 to 3.4e38 double 8 bytes 2.2e308 to 1.8e308
Good luck
#3
Re: Working with large integers
Posted 27 June 2008  08:58 PM
2^31 which is 2,147,483,647(is not large enough).
and even though float allows 1.8x10^308, it only gives you 6 digits of precision. In other words, it truncates everything after 6 digits, which means you cannot do any arithmetic on the numbers (with accuracy).
I am looking for a work around, a way to get passed these limits.
else, use a better programing language.
#4
Re: Working with large integers
Posted 27 June 2008  09:16 PM
http://en.wikipedia....cision_software
Regardless of the language you choose, if you want to deal with numbers that big, you will have to use a arbitraryprecision library.
#6
Re: Working with large integers
Posted 27 June 2008  09:59 PM
First few google results:
GMP
MAPM
MPFRCPP
Oh there are a ton of other ones. This is vary popular graduate work at universities apparently. Heck pick your favorite major university and I bet they have a version (or are associated with a version).
#7
Re: Working with large integers
Posted 28 June 2008  06:24 PM
Now, at the risk of being a complete idiot, i must now ask how the heck do I install them. Ive been following links and reading all day, but have made no progress
You would think (well, hope at least) that a quick search on the MS visual c++ 2008 studio help page would explain something as simple as adding a new library. But then wait, this is the same company that introduced VISTA, what can I be thinking!
I followed links from Nickdmax, and the the web page explained that if you are using msvc++ then you need GMP and MPFR which i downloaded. But I don't know where to put them. (a search on msvc++ gave "0" results for gmp and mpfr)
Is this really this difficult? Am i really this stupid? Now i remember why i avoided programing for the past 20yrs.
Perhaps there is a better compiler to learn on.
I'm running VISTA basic on a laptop, I went with MSVC++ because it was free.
Thanks again
#8
Re: Working with large integers
Posted 28 June 2008  06:28 PM
Personally, I hate the common opne source model. The basics behind it, is you are suposed to type
./configure
make
make install
but there are so many things wrong with doing this.
Give me a few minutes, and I'll see if I can convert a library to a easy to use form...
#9
Re: Working with large integers
Posted 28 June 2008  07:36 PM
https://sourceforge....lease_id=547633
download "bigint20src.zip". Upzip them, and throw them into your Visual Studio Project. Example of how to use the class are in the included main.cpp.
There is a bug though. Open up bigint.cpp, and put this at line 1247 (in the function RossiBigInt& RossiBigInt::operator= (const RossiBigInt& arg_i)_
if(arg_i.units_.size() <= i) while(arg_i.units_.size() <= i) ((RossiBigInt&)arg_i).units_.push_back(0);
after prevdigit = units_[i]; and before units_[i] = units_[i]  arg_i.units_[i]  borrow;
Edit: You gotta love how some open source projects "require" 100s of files, while others only need 1 source file and a header...
This post has been edited by Cerolobo: 28 June 2008  07:39 PM
#10
Re: Working with large integers
Posted 28 June 2008  07:42 PM
I will work on this.
It will probably take me some time, but i'll let you know how it goes.
thanks
#11
Re: Working with large integers
Posted 28 June 2008  11:10 PM
I guess this is just beyond me.
I opened a project and put bigint.h in theheader files folder
And bigint.cpp and main.cpp in the source files filder, and made the recommended changes and then
did "build project" it compiled with no errors. I ran the file and it scrolled by tonnes of stuff in a dos window,
but I dont know how to make it allow bigintegers in MY code. IF the directions are in that stuff that scrolls by in the dos window, it is not possible to read them, and the dos window only allows you to scroll back a few lines, the rest are lost, thrown away by the computer.
i modified the main file, to test :::::: here it is
#include <iostream>
#include <fstream>
using namespace std;
// ===============
#include "bigint.h"
// ===============
// 
int main ()
{
int x;
x=2100000000;
cout<<x*x;
return 0;
the output was a regular integer 2^31 in value.
i tried bigint x; instead of int x; , but it did not accept that.
I guess i thought that if you put some files in the correct directory, you would just do #include <mynewlibrary> and get some new functions.
Thanks again for your help.
#12
Re: Working with large integers
Posted 29 June 2008  11:11 AM
Unfortunately, the class does not support some operations that would make it's integration seamless.
To do what you want, you will have to do this
// =============== #include "bigint.h" // =============== int main () { RossiBigInt x; x = x + 2100000000; cout << x * x; return 0; }
or
// =============== #include "bigint.h" // =============== int main () { RossiBigInt x(2100000000); cout << x * x; return 0; }
The supported operations are as follows:
explicit RossiBigInt(); explicit RossiBigInt(unsigned long unit_i); explicit RossiBigInt(const string& arg_i, unsigned long digit_base_i); explicit RossiBigInt(const VinBigInt& arg_i); //  General purpose mathematical methods  RossiBigInt operator+ (const RossiBigInt& arg_i); RossiBigInt operator+ (unsigned long arg_i); RossiBigInt operator* (RossiBigInt arg_i) const; RossiBigInt operator* (unsigned long arg_i) const; RossiBigInt operator/ (const RossiBigInt& arg_i) const; RossiBigInt operator% (const RossiBigInt& arg_i) const; RossiBigInt Divide(const RossiBigInt& dividend_i, const RossiBigInt& divisor_i, RossiBigInt* remainder_o) const; RossiBigInt& operator+= (const RossiBigInt& arg_i); RossiBigInt operator++ (int); // Post increment operator RossiBigInt& operator++ (); // Pre increment operator RossiBigInt operator (const RossiBigInt& arg_i); RossiBigInt operator (); RossiBigInt operator (int); // Post decrement operator RossiBigInt& operator (); // Pre decrement operator RossiBigInt& operator= (const RossiBigInt& arg_i); RossiBigInt sqrt(); //  Bitwise boolean operators  RossiBigInt operator& (const RossiBigInt& arg_i); RossiBigInt operator (const RossiBigInt& arg_i); RossiBigInt operator^ (const RossiBigInt& arg_i); RossiBigInt& operator&= (const RossiBigInt& arg_i); RossiBigInt& operator= (const RossiBigInt& arg_i); RossiBigInt& operator^= (const RossiBigInt& arg_i); RossiBigInt operator~ (); RossiBigInt operator>> (unsigned long shift_i); RossiBigInt operator<< (unsigned long shift_i); RossiBigInt& operator>>= (unsigned long shift_i); RossiBigInt& operator<<= (unsigned long shift_i); //  Comparison operators  bool operator== (const RossiBigInt& arg_i) const; bool operator!= (const RossiBigInt& arg_i) const; bool operator< (const RossiBigInt& arg_i) const; bool operator> (const RossiBigInt& arg_i) const; bool operator<= (const RossiBigInt& arg_i) const; bool operator>= (const RossiBigInt& arg_i) const;
So basically, you'll have to create a RossiBigInt for most of your operations.
For the most part, this is kinda logical, since you can't initialize a a variable to a number beyond what the CPU allows. IE, you can't do RossiBigInt integer = 1000000000000000000000;
This post has been edited by Cerolobo: 29 June 2008  11:12 AM
#14
Re: Working with large integers
Posted 29 June 2008  06:46 PM
I will try some more. I'm ok with the algorithmic aspect of programing (my math background compensates)
its how the extra stuff fits together. IF the code is all in one file, i'm cool, but I dont understand how to fit
multiple files (and headers and librarys etc etc,, there don't seem to be good explanations of all this)
Was very frustrated yesterday
I went ahead and wrote my program (just limited to 2^20), if your interested in seeing it i'll include it. Along with
a necessary file (contains a small list of primes, the first 3500 or so)
Essentially the program tests wether 2^k+c is prime, where c = x*y. I kept x and y down to odds, 1 through 25 just to
get a feel for the program. Until k gets very large , x,y don't have to be very big.
The output is a comma delimeted txt file that can be opened in excel.
keep in mind, i just started reading a c++ book beginning of the month, so its not efficient or pretty, but it works
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
int ppow(int mypower);//return the power of 2 without using float
int isprime(int c); // return whether value is prime or not
int globalcount; // global
int testvalue; // global
int p[3600]; // global
int main()
{
int x;
int xx;
int y;
int n;
int powresult;
ifstream in("primes3517.txt"); //loads first 3517 primes into p[x], enough to do the job
if (!in) {
cout << "cannot open file. \n";
return 1;
}
for (x=0;x<=3516;x++) in >> p[x];
// for (x=0;x<=3516;x++) cout << p[x]; check to see if primes are really going in
in.close();
// *testing to make sure works so far* for (x=0;x<=3516;x++) cout << p[x]<<",";
// open a file for the output
ofstream out("matrixstuff.txt");
if(!out)
{ cout << "Cannot open file.\n";
return 1;
}
for (n=1;n<=20;n++)
{
out<<" ,1,3,5,7,9,11,13,15,17,19,21,23,25,\n";
globalcount=n;
for (y=1;y<=25;y=y+2)
{
out<<y<<",";
for (xx=1;xx<=25;xx=xx+2)
{
powresult=ppow(globalcount); // the function's return value from 2pow is assigned to powresult
testvalue=powresult + xx*y;
out << isprime(testvalue)<<","; // calls function isprime, 0 or 1 is returned
//not real comforatble with bool, so stuck with int
if (xx>=25) out << "\n";
if ((y>=25)&&(xx>=25)) out << "\n";
}
}
}
return 0;
}
//This function returns powers of 2 withouth using float
int ppow(int globalcount)
{
int k;
int m;
m=1;
for (k=1;k<=globalcount;k++) m=2*m;
//cout << k;
return m;
}
//This function returns wether the numbers are prime or not
int isprime(int testvalue)
{
int x;
float testv;
int sqrrttestv;
float expy=0.5;
testv = testvalue;
sqrrttestv = pow(testv,expy); //not comfortable with float, returned to int
//perhaps there is a better way
for (x=0; x<=sqrrttestv; x++)
{
//cout << testvalue << "," << x << "," << p[x]<< ","; just checking because i had some problems here
if ((testvalue%p[x])==0&&testvalue>p[x]) return 0; // found the 'and' was necessary, because p%p returns zero
}
return 1;
}
// The ouput file is a matrix (in this case a set of 20 matrices) which can be
// opened in excel as a comma delimeted txt file,
// the matrices tell you which numbers of the form 2^k + x*y are prime and which are not.
// 1's mean prime, zeros are not. k= 1 to 20 (because of current limitations)
// the goal as that there may be some matrix or group operations to systematically move from
// one matrix to the next, thus allowing for some halfharted prediction to a
// number c such that 2^k+c will be prime.
//
// The future goal, is to be able to work with arbitraily factored numbers, not just
// powers of 2.
Attached File(s)

primes_3517.txt (22.65K)
Number of downloads: 84
#15
Re: Working with large integers
Posted 30 June 2008  11:39 AM
I'm making some progress.
I am able to "grow" some big numbers now!
#include "bigint.h" int main () { int y; RossiBigInt x(0); for (y=1;y<=100;y++) { x=x+100000; x++; cout << x <<"\n"; cout << x*x <<"\n"; cout << x*x*x << "\n"; } return 0;
will give pleasing results.
But if you try to define it as a larger than 2^31 int, it gives random values for x,
ex. RossiBigInt x(123456789101112)
cout << x
gives 2249144888, but thats ok, I've got enough to work on now. I can use loops and "grow" my numbers.
The hardest part was knowing where to put the bigint.cpp and bigint.h files and to call the program i'm working on main.cpp.
Is that a standard thing to do?
Anyway, thanks so much
