Working with large integers

• (2 Pages)
• 1
• 2

15 Replies - 10166 Views - Last Post: 30 June 2008 - 12:11 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=56091&amp;s=abd0756b2c80f204bb0241e1fcf34415&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 thompson03

Reputation: 1
• Posts: 23
• Joined: 12-June 08

Working with large integers

Posted 27 June 2008 - 08:07 PM

Hi,

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 pre-made 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!

Is This A Good Question/Topic? 0

Replies To: Working with large integers

#2 nirvanarupali

• D.I.C Stomach

Reputation: 14
• Posts: 1,120
• Joined: 01-August 07

Re: Working with large integers

Posted 27 June 2008 - 08:29 PM

Here are the basic thing you need to know in C++
```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.2e-38 to 3.4e38
double 			8 bytes 		2.2e-308 to 1.8e308

```

Good luck

#3 thompson03

Reputation: 1
• Posts: 23
• Joined: 12-June 08

Re: Working with large integers

Posted 27 June 2008 - 08:58 PM

That is exactly my problem.

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 Cerolobo

• D.I.C Regular

Reputation: 52
• Posts: 450
• Joined: 05-April 08

Re: Working with large integers

Posted 27 June 2008 - 09:16 PM

You can get a arbitrary-precision integer library from here.
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 arbitrary-precision library.

#5 thompson03

Reputation: 1
• Posts: 23
• Joined: 12-June 08

Re: Working with large integers

Posted 27 June 2008 - 09:53 PM

Thank you!

#6 NickDMax

Reputation: 2255
• Posts: 9,245
• Joined: 18-February 07

Re: Working with large integers

Posted 27 June 2008 - 09:59 PM

There are a number of libraries available to do arbitrary precision arithmetic.

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 thompson03

Reputation: 1
• Posts: 23
• Joined: 12-June 08

Re: Working with large integers

Posted 28 June 2008 - 06:24 PM

I want to thank you guys for your responses. I have looked at these packages and they look to be the perfect thing for what I want.

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 Cerolobo

• D.I.C Regular

Reputation: 52
• Posts: 450
• Joined: 05-April 08

Re: Working with large integers

Posted 28 June 2008 - 06:28 PM

Welcome to the Wide World of Open Source.

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 Cerolobo

• D.I.C Regular

Reputation: 52
• Posts: 450
• Joined: 05-April 08

Re: Working with large integers

Posted 28 June 2008 - 07:36 PM

Ok, I finally found one that will work for you.

https://sourceforge....lease_id=547633

download "bigint-2-0-src.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 thompson03

Reputation: 1
• Posts: 23
• Joined: 12-June 08

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 thompson03

Reputation: 1
• Posts: 23
• Joined: 12-June 08

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.

#12 Cerolobo

• D.I.C Regular

Reputation: 52
• Posts: 450
• Joined: 05-April 08

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

#13 Tom9729

• Segmentation fault

Reputation: 181
• Posts: 2,642
• Joined: 30-December 07

Re: Working with large integers

Posted 29 June 2008 - 12:26 PM

Here is some lecture notes on implementing a "big integer" datatype in C.

Note that searching for "c bigint" on Google provided many other results.

#14 thompson03

Reputation: 1
• Posts: 23
• Joined: 12-June 08

Re: Working with large integers

Posted 29 June 2008 - 06:46 PM

Thanks (advanced apologies if the math part is too boring )

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("primes-3517.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.

#15 thompson03

Reputation: 1
• Posts: 23
• Joined: 12-June 08

Re: Working with large integers

Posted 30 June 2008 - 11:39 AM

Thanks cerolobo,

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