CODEWITHSUNDEEP
c++types32bit-64bitunsigned-long-long-int
Abrar
Abrar

Reputation: 7232

What should be the data type for numbers in between the range of 10^10 - 10^11?

Suppose I have the following code to loop over numbers as follows: 

 int p;
 cin>>p;
 for(unsigned long long int i=3*pow(10,p);i<6*pow(10,p);i++){

              //some code goes here
 }

Now, based on certain condition checks I need to print a i in between the range : 3*pow(10,p)<= i <6*pow(10,p)

The code works fine upto p=8, then it becomes pretty sluggish and the compiler seems to get stuck for p=9,10,11 and onwards. I am guessing the problem lies in using the correct data type. What should be the correct data type to be used here ?

The purpose of this loop is to find the decent numbers in between the range. Decent numbers conditions as follows: 1) 3, 5, or both as its digits. No other digit is allowed. 2) Number of times 3 appears is divisible by 5. 3) Number of times 5 appears is divisible by 3.

NOTE: I used unsigned long long int here (0 to 18,446,744,073,709,551,615) . I am running on a 32-bit machine.

Upvotes: 0

Views: 288

Answers (1)

Basile Starynkevitch
Basile Starynkevitch

Reputation: 1

You could use <cstdint> and its int64_t (which is guaranteed to have 64 bits) and you should compute the power outside of the loop; and long long has at least 64 bits in recent C or C++ standards.

But, as mentioned in a comment by 1201ProgramAlarm, 3e11 (i.e. 300 billions) loops is a lot, even on our fast machines. It could take minutes or hours: an elementary operation is needing a nanosecond (or half of it). 3e9 operations need several seconds; 3e11 operations need several minutes. Your loop body could do several thousands (or even more) elementary operations (i.e. machine code instructions).

It is not the compiler which is stuck: compiling your code is easy and quick (as long as the program has a reasonable size, e.g. less than ten thousand lines of code, without weird preprocessor or template expansion tricks expanding them pathologically). It is the computer running the compiled executable.

If you benchmark your code, don't forget to enable optimizations in your compiler (e.g. compiling with g++ -Wall -O2 -arch=native if using GCC...)

You should think a lot more on your problem and reformulate it to have a smaller search space.

Actually, your decent numbers might more be thought as strings of digits representing them; after all, a number does not have digits (in particular a number expressed in binary or ternary notation cannot have 3 as its digit), only some representation of a number have digits.

Then you should only consider the strings of 3 or 5 which are shorter than 12 characters, and you have much less of them (less than 10000, and probably less than 213 i.e. 8192); iterating ten thousand times should be quick. So generate every string smaller than e.g. 15 characters with only 3 and 5 in it, and test if it is decent.

Upvotes: 2

Related Questions