C++, computing with huge numbers and booleans.

In this forum members can discuss topics about specific programming languages.
rr89
Posts: 4
Joined: Tue Jan 20, 2009 9:40 am

C++, computing with huge numbers and booleans.

Post by rr89 »

Hi, while attempting to solve some of the Euler-project problems ,as you know, you sometimes have to deal with huge numbers.
Im a C++ user, and when I compile my just implemented code for solving a problem, on relatively small numbers, it usually works well. But then, in order to give the correct solution, I often have to input some large number, so large that often the result won't be in the value range of "unsigned int" or "long long int". I looked for a solution on the internet, and found some files which I could include as directive, e.g. #include <...>. But when I tried to use these in a program for computing prime numbers, (by using an algorithm similar to the one of Eratosthenes' sieve, and using also boolean arrays, e.g. an array filled with values in {0,1} ), the compiler found an error, which raised from the uncompatibility of the included file, and the operator [] of the boolean array.
For instance I tried to fill the boolean array, bool Primes[n], with n being of the type specified by the included file,
in the following manner: for ("type of a_value being of the same type as n" a_value = 0; a_value < n; ++ a_value)
Primes [a_value] = false;

This should set all values of the array Primes[n] to false. But it didn't work, as described before because of that what I think to be an uncompatibility problem. The error found while trying to compile it, and the output message, was something like:
"No match for operator [] in...".

I'd be very grateful for help.

rr89

User avatar
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

Re: C++, computing with huge numbers and booleans.

Post by stijn263 »

without including any special files, you can declare the following:

Code: Select all

const int n = 1000;
bool primes[n];
After stating the above, if you want to do a simple sieve, you can use the following.

Code: Select all

for(int i = 0; i < n; ++i) primes[i] = true;

primes[0] = primes[1] = false;

for(int i = 0; i < n; ++i) {
  if( primes[i] == true ) {
    for(int j = 2*i; j < n; j = j + i) primes[j] = false;
  }
}
Now you'll have an array, primes, filled with true or false values, telling you wether any given number below 1000 is a prime.

About your question concerning large numbers, all numbers stay below 263 in 99% of the problems and thus fit within long long int.

rr89
Posts: 4
Joined: Tue Jan 20, 2009 9:40 am

Re: C++, computing with huge numbers and booleans.

Post by rr89 »

Hi,
first of all thanks for replying.
I already had implemented such a sieve, and the problem arose when I needed to get prime numbers (or other numbers) that were far beyond the maximum range of long long unsigned int.
(And also in one of the more simple problems, you were asked to find a sum, where you had to deal with numbers up to
1000^1000).

Do you know some useful file to be included, which could help me with this kind of problems, or maybe some other hint or recommendation?

Thank you very much.

rr89

User avatar
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

Re: C++, computing with huge numbers and booleans.

Post by stijn263 »

Well, doing a sieve up to something like 109 (which easily fits in normal ints) already takes way too long. So you need to use something else to find such large prime numbers.

About Problem 48 (View Problem). This problem only asks for the last 10 digits, so you need the answer mod 10^10.

Let's look at 7^4 mod 10. You could try to find 7^4, and then do the modding. Alternatively, you could do the modding every time:
7*7 mod 10 = 9
9*7 mod 10 = 3
3*7 mod 10 = 1 = 7^4 mod 10

This way, you'll never have an intermediate result above 7*9 = 63.

I hope this helps you out :-)

If you really want to use big numbers, you could switch to a language like java or python, or download a bignumber library like http://gmplib.org/. But it isn't necessary for project euler problems..

rr89
Posts: 4
Joined: Tue Jan 20, 2009 9:40 am

Re: C++, computing with huge numbers and booleans.

Post by rr89 »

Hi,
thanks again for replying.
Actually I already solved that problem, but I only solved it for that particular number and wanted to write a program which solves the problem for a given input, which could be much bigger. (I also wanted to find the last ten digits of the Mersenne prime 2^{43,112,609}-1...).
Writing such a function was not difficult, but as stated in the posts before I get in trouble when trying it on too large numbers.

I probably will search that bignumber file, as you recommended.

Thanks again.

rr89

User avatar
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

Re: C++, computing with huge numbers and booleans.

Post by stijn263 »

I probably will search that bignumber file, as you recommended.
I didn't recommended it. GNU MP is not easy to use.

I still don't see any problem though. This (inefficient) program computes (2^{43,112,609}-1) mod 10^10 = 6697152511 in less than a second :-)

Code: Select all

#include <iostream>
using namespace std;

int main() {
  long long int b, M, x;
  x = 1;
  b = 43112609;
  M = 10000000000ll;
  
  // compute 2^b mod M = x
  for(int i = 0; i < b; i++) {
    x *= 2;
    if( x > M ) x -= M;
  }
  
  x--;
  cout << x << endl;
  
  system("Pause");
  return 0;
}

User avatar
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

Re: C++, computing with huge numbers and booleans.

Post by stijn263 »

BjornEdstrom wrote:For a nice C++ library that can handle arbitrary precision integers and decimals, I can recommend NTL. It gives you two classes, ZZ for integers and RR for decimals. It's quite easy to use, for example:

Code: Select all

RR dec("0.123456789");
RR answ = dec * to_RR(10);


The de facto bigint library is of course GNU MP, but NTL is often good enough and it's usuable without reading a manual first.

rr89
Posts: 4
Joined: Tue Jan 20, 2009 9:40 am

Re: C++, computing with huge numbers and booleans.

Post by rr89 »

Thank you very much for your help. After having given a glance at the GNU MP website, it seemed to me indeed a bit complicated. The one you recommended looks way more simple.

rr89

User avatar
rayfil
Administrator
Posts: 1405
Joined: Sun Mar 26, 2006 5:30 am
Location: Quebec, Canada
Contact:

Re: C++, computing with huge numbers and booleans.

Post by rayfil »

for(int i = 0; i < b; i++) {
x *= 2;
if( x > M ) x -= M;
}
Unless your compiler is extremely efficient for optimization, you can improve the speed of that algo by a factor of 15-40. Multiplications being much slower than additions, specially for longlong ints on 32-bit processors, adding a number to itself is thus significantly faster than multiplying by 2.

for(int i = 0; i < b; i++) {
x = x+x;
if( x > M ) x -= M;
}
When you assume something, you risk being wrong half the time.

User avatar
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

Re: C++, computing with huge numbers and booleans.

Post by stijn263 »

That takes exactly the same amount of time on my pc. I think a multiplication by 2 is automatically replaced by a bit shift, because this:
for(int i = 0; i < b; i++) {
x <<= 1;
if( x > M ) x -= M;
}

Also takes about 500ms..

User avatar
rayfil
Administrator
Posts: 1405
Joined: Sun Mar 26, 2006 5:30 am
Location: Quebec, Canada
Contact:

Re: C++, computing with huge numbers and booleans.

Post by rayfil »

a multiplication by 2 is automatically replaced by a bit shift
A bit shift by 1 could be 2-4 times slower than an addition for doubling a number. Some processors are worse than others.

Have you tested that snippet with an addition instead?
When you assume something, you risk being wrong half the time.

User avatar
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

Re: C++, computing with huge numbers and booleans.

Post by stijn263 »

Yup, also takes about 500ms

User avatar
hk
Administrator
Posts: 10889
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: C++, computing with huge numbers and booleans.

Post by hk »

To do benchmarks is a tricky thing.
Presumably because the calculated values of x are never used the compiler skips the whole thing.
You should add the calculated values of x to some variable and output the sum.
Moreover the if statement could be more time consuming then the doubling of x.
Image

User avatar
uws8505
Posts: 58
Joined: Tue Sep 30, 2008 3:13 pm
Location: South Korea

Measuring timing in C++

Post by uws8505 »

I use both C++ and Mathematica for solving PE problems.
In Mathematica, there are several methods to measure elapsed time, using Timing[] function or package Utilities-ShowTime.
But I do not know anything about timing in C++.
Can someone teach me how to do such a thing in C++?
Math and Programming are complements

User avatar
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

Re: C++, computing with huge numbers and booleans.

Post by stijn263 »

Code: Select all

#include <ctime>
#include <iostream>
using namespace std;

int main() {
  double dt = clock();
  
  /* do some things */
  
  cout << "Elapsed time: " << clock() - dt << "ms" << endl;
  system( "Pause" );
  return 0;
}
If you have any more questions, feel free to ask them :-)

User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: C++, computing with huge numbers and booleans.

Post by daniel.is.fischer »

If the elapsed time is not a good measure (because your programme runs long enough for the scheduler to switch tasks in between), you can use the times function (man -S 2 times, or if you're using a funny OS, whatever is the equivalent query) to get the CPU-time used by your programme.
Il faut respecter la montagne -- c'est pourquoi les gypa&egrave;tes sont l&agrave;.

pzhon
Posts: 20
Joined: Wed Feb 25, 2009 1:16 am

Re: C++, computing with huge numbers and booleans.

Post by pzhon »

Within the .Net 3.5 framework, you can use the System.Diagnostics.Stopwatch class to get timing information which is much more precise than the millisecond, and often more accurate. This was introduced relatively recently.

C#

Code: Select all

using System.Diagnostics;

Stopwatch mySW = new Stopwatch();
mySW.Start();
// do stuff here
myLabel1.Text = "Ticks: " + mySW.ElapsedTicks.ToString();
myLabel2.Text = "Time: " + mySW.Elapsed.ToString();
This can be translated to C++, of course.

User avatar
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

Re: C++, computing with huge numbers and booleans.

Post by stijn263 »

Does anyone know a good and free C++ compiler for 64 bit processors? I'm using dev-c++ now, but I think dev-c++ isn't optimized to work on 64-bit processors..

quilan
Posts: 182
Joined: Fri Aug 03, 2007 11:08 pm

Re: C++, computing with huge numbers and booleans.

Post by quilan »

stijn263 wrote:Does anyone know a good and free C++ compiler for 64 bit processors? I'm using dev-c++ now, but I think dev-c++ isn't optimized to work on 64-bit processors..
gcc doesn't do 64-bit?
ex ~100%'er... until the gf came along.
Image

User avatar
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

Re: C++, computing with huge numbers and booleans.

Post by stijn263 »

The executable runs as a 32bit program when I check the processes in the task manager. So I'd say it's not 64 bit?

Post Reply