C++, computing with huge numbers and booleans.
C++, computing with huge numbers and booleans.
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
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
Re: C++, computing with huge numbers and booleans.
without including any special files, you can declare the following:
After stating the above, if you want to do a simple sieve, you can use the following.
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.
Code: Select all
const int n = 1000;
bool primes[n];
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;
}
}
About your question concerning large numbers, all numbers stay below 263 in 99% of the problems and thus fit within long long int.
Re: C++, computing with huge numbers and booleans.
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
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
Re: C++, computing with huge numbers and booleans.
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..
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..
Re: C++, computing with huge numbers and booleans.
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
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
Re: C++, computing with huge numbers and booleans.
I didn't recommended it. GNU MP is not easy to use.I probably will search that bignumber file, as you recommended.
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;
}
Re: C++, computing with huge numbers and booleans.
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.
Re: C++, computing with huge numbers and booleans.
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
rr89
Re: C++, computing with huge numbers and booleans.
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 *= 2;
if( x > M ) x -= M;
}
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.
Re: C++, computing with huge numbers and booleans.
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..
for(int i = 0; i < b; i++) {
x <<= 1;
if( x > M ) x -= M;
}
Also takes about 500ms..
Re: C++, computing with huge numbers and booleans.
A bit shift by 1 could be 2-4 times slower than an addition for doubling a number. Some processors are worse than others.a multiplication by 2 is automatically replaced by a bit shift
Have you tested that snippet with an addition instead?
When you assume something, you risk being wrong half the time.
Re: C++, computing with huge numbers and booleans.
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.
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.
War ruins the life and health of untold numbers of innocent children.
Measuring timing in C++
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++?
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
Re: C++, computing with huge numbers and booleans.
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;
}
- daniel.is.fischer
- Posts: 2400
- Joined: Sun Sep 02, 2007 11:15 pm
- Location: Bremen, Germany
Re: C++, computing with huge numbers and booleans.
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ètes sont là.
Re: C++, computing with huge numbers and booleans.
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#
This can be translated to C++, of course.
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();
Re: C++, computing with huge numbers and booleans.
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..
Re: C++, computing with huge numbers and booleans.
gcc doesn't do 64-bit?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..
ex ~100%'er... until the gf came along.
Re: C++, computing with huge numbers and booleans.
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?