Topic: fastest way in C to generate numbers (Read 336 times)

That's correct. Notice how astronomically small the minimum long double is. If you increment it by epsilon (the smallest possible increment in floating point numbers), it goes from e-4932 to e-19. That's lack of accuracy; tradeoff when working with 64 bits and real numbers.  

Another fun fact. The maximum long double number is 1.1897314954e+4932, as rightly said. This means that long doubles are 2^128 in total, in a range of [~0, ~10^4932]. The more you increase the wanted number, the more inaccurate it becomes.

test.cpp



./test
Enter the value of n: 40
Time taken for random method: 0.000012 seconds

This is a very demanding one.

This code will loop through all numbers from 1 to 2^n - 1   and increment by 1 (optionally print each number)

test.cpp

# ./test
Enter the value of n: 30
Time taken for random method: 6.051514 seconds

Try seq. 30 bit, or 1-1073741824, takes 13.7 seconds. I can't compile your code to compare processing time.
Try for yourself and compare:

For multiprocessing, start multiple instances and set lower and upper limits on each to spread the work.

That's right, 4 seconds. The code was just a self-challenge to explore some ideas using SIMD and C# spans.

It could be faster in C, although to be sure the same exact code in two languages (correctly populating a list of 1,073,741,824‬ ints with sequential values) has to run on the same exact hardware and then compared. Unfortunately I can't compile C (don't want to add more dev tools to my Visual Studio and take up more space) to do the comparison.

makes sense, I'll take care of it. Thanks


I just tested out the min/max values on my system:

Result:

Nice, thanks for sharing. You are on the bit space 2^30 and it took 4 seconds, right ?

We are much faster in C though using the bit shifting method and -O1 optimization flag:

Nice, thanks for sharing. You are on the bit space 2^30 and it took 4 seconds, right ?

We are much faster in C though using the bit shifting method and -O1 optimization flag:

Nice, thanks for sharing. You are on the bit space 2^30 and it took 4 seconds, right ?

We are much faster in C though using the bit shifting method and -O1 optimization flag:

Just for fun I wrote one using C#, quick, easy and clean using SIMD

On my ancient CPU

Here is a smaller version (0x00400000 or 2^22) that can run on the internet using sharplap

P.S. To write to disk all it takes is using BinaryWriter. To get bigger integers all it takes is to replace int with long (ulong for unsigned). To get any bigger than that a simple 256 bit struct can be defined to store the values and have an increment/add method

Sorry if I have confused you. What I meant is that whether you keep the bitwise operation in the expression or not, it won't make a big difference in terms of time, because it is inexpensive. On the other hand, pow is more computationally expensive, and you can notice the difference if you remove it from the expression.

Compilers like GCC have developed overtime and come with optimization options. There are quite a lot. I don't know them all obviously, but I've used -O1, -O2 and -O3.

I know, I'm not totally sure about what -O2 and -O3 do behind the scene, but due to them being more aggressive, I expect they ignore the empty loop.

Yes, but double is... not integer. A double can take up to 2¹²⁸ values (hereby, 128-bit), but it cannot represent all the numbers between 0 and 2¹²⁸, if that was your goal. Read about double-precision in here: https://en.wikipedia.org/wiki/Double-precision_floating-point_format.

that somehow contradicts the previous statement

From a logical point of view, I fully agree.

As I originally mentioned, I am completely new to C and therefore don't really know my way around. The -O1 option doesn't mean anything to me, I had to google it to find out what it means. Thanks for pointing out to that optimization mechanisms.


Yeah, I see. The -O1 optimization flag is pretty nice As you explained, the -O2 or -O3 will only have effect if using "real work" within the loop clause. Here the results I achieved for the bit shifting operations and the particular optimization levels...


Now coming back to the roots. What mechanism do you Pro's suggest to speed things up? How to implement parallelization, multi-threading, multi-processing, concurrent work load distribution, or/and even CUDA implementation ? Let's try to challenge the performance. Currently we're on n=32 but we should go to higher bit ranges and see how performance behaves within the different domains.

Removing the bitwise operation from the for loop expression won't have a significant difference in performance, because the bitwise operation is really computationally inexpensive. It has difference if you compare it with pow, if run for millions or billions of times. Nonetheless, it is good practice to not make operations in expressions.

Let's optimize during compiling. Append the usual command with -O1:
(might pop a warning about scanf, ignore it)

"After" program times without optimization:

"After" program times with optimization:
("Before" program takes a little bit more with optimization, but it isn't always true; it can take less time sometimes)

If you put something inside the for loop, then you could use -O2 or -O3 for more aggressive optimization.

You are so right. Thank you very much for pointing this out and correcting the performance error. I have understood this and can fully comprehend it. Lesson learned

However, after trying it out myself, I am now even more confused. I have implemented this change and it seems to me that this change has worsened performance.

Before:

After:

As you can clearly see, the initial (BEFORE:) code I used with the expression in the for loop is faster. But I lack any justification for this.
/puzzled

First of all, I just saw your code, and you're adding an extra burden for no reason. This is how you've defined the for loop:
This is what I get:

Seems like the fastest, or equally fast with the program above.

I tried the method with complex numbers you suggested and compared it to the time needed when using the bit shifting method. Latter one is faster, I get better results with the bit shifting method.
I'm using MAX=32768 which represents 2^15. That means the program iterated through 2^30 numbers.

You mean long long int, right? So it means that the technical limitation of the default data types in C would be 2^64 for the for loop, regardless of whether you use the bit shifting method or another one? What about the data type "long double", shouldn't this support up to 2^128 ?

You'll have to use specialized libraries, like GMP (GNU Multiple Precision Arithmetic Library). I just wrote a small program for you to play with.


If you run this, it will start printing all 256-bit numbers, from the start (0) to finish (2²⁵⁶-1). It will obviously never finish, because 2²⁵⁶-1 is astronomically huge.

However, for the sake of simplicity, I suggest you use complex numbers instead of this. C supports 64-bit as a maximum integer, so a complex x + y*i, with x, y ∈(0, 2^64-1) can take up to (2⁶⁴)² = 2¹²⁸ values. That's enough for our purposes:

You can define MAX to smaller values (like 2¹⁰=1024) to see it finishing. If the last number printed is 1024 + 1024*i, then you can be certain it is the 2²⁰th.

In order to make the program and the challenge even simpler, we can, for all I care, neglect the file output. Then we have one less link in the process chain.
So let's concentrate on the number generation. The limit of 2^64 is too small, it must be compatible up to 2^256 and thus with very large numbers.


that was a very good tip, thank you very much! the bit shifting method achieves an enormous speed advantage, as I have discovered through this comparison.

The user didn't mention random number generators.

In fact, your idea will not improve performance. In the original scenario, OP runs a for loop and prints each number to the file. In your scenario, you create an array and then you do the exact same thing, looping the array.

pow returns a double, not an int. You should rather utilize bitwise operator <<.

Writing to the disk is going to slow this down. Why don't you just use printf? It will display the numbers in the terminal at faster rate than fprintf will write them in disk.

Also, apogio is correct about overflows. C permits you to declaring up to 64 bit integers (unsigned long long int is the largest it can get, up to 2^64 - 1).

The fastest way to generate numbers would be to use a pre-allocated array. An array is a data structure that stores a collection of elements in a contiguous block of memory. You could then use a simple for loop to access the elements in the array, which would be faster than using a random number generator function. For example, you could use the following code to generate a sequence of numbers from 0 to 100:

Yes, it has to be in C due to the performance requirement. I guess we'll have to stick to GMP according to many other C program and tools out there in Bitcoin community. Just think of VanitySearch or BitCrack and tools like that. They all handle big numbers as well some of them even come with CUDA capabilities.

This is a good challenge in fact, I will try to make it work fast and I will let you know. There are still 2 questions  though. Is it mandatory to use C ? If yes, then how will we solve the issue with the buffer overflow? We can't go higher than 30 bits using an int.

I thank you for every objective comment, no matter how helpful it is. After all, we are all learning, even the successors who will read here. And that's what it's all about, the added value for the entire community.

The approach you describe (with the batches) is what I've been using in Python so far. I am also aware that the file operations are very cost-intensive and yes, I am aware that everything runs much faster in RAM.

After all, this is just a simple program, I'm looking for a basis. The final program will look completely different anyway. I have provided a template so that we have a benchmark. Based on this, everyone can try to generate as many numbers as possible, write them to the output file and then compare the time needed for the operations. Goal is to achieve the fastest way. All techniques are allowed, the faster the better

Hello, let me share my comments and perhaps we can construct something good.

First of all, I will not comment anything on CUDA because I am not very competent with it and I don't want to mislead you.

Now, my comments:

1. You basically want to generate numbers from 1 to 2^n where 1 <= n <= 100. But, I can assure you that printing them on the file requires much more time than just generating them on the RAM. If you measure how much time it takes to fprintf all the numbers on the file, versus the time it takes to fprintf only the last number (which will happen when the program terminates), the time elapsed will differ dramatically. But, I believe you want to print all the numbers, so my comment isn't very accurate.

2.Writing on the file, requires consecutive disk I/Os which are very time consuming. A work-around would be to print the numbers in batches. But the problem with C is that you cannot print the numbers without using recursion or loops. So you could add the numbers to an array in RAM (let's say the size of the array is 10,000). Then every 10,000 numbers, you would need to print to the file in batch. But, as I said, batch writing is not possible in C. You still need to loop the array and print one-by-one so you will technically add an overhead to your whole experiment which will not improve the time needed. However, the concept could be applied in other programming languages.

3. You assign numbers to an integer (int). In C, an int can take values from -2,147,483,648 to 2,147,483,647. The latter is equal to 2^31 + 1, which means that you cannot put any number larger than 30. So if you put n=100, then you will get a buffer overflow. Try it, just for fun.

Disclaimer: My last C program was written 10 years ago, so please be nice with me  

Hi folks.

I'm trying to achieve the highest possible throughput for number generation and am making my first attempts in C. Unfortunately I can't manage to work with multithreading, all my attempts failed. The goal is to simply generate numbers from 1 to 2^n and measure the time needed to do so in order to work as efficiently as possible. My current simple program looks like this:

The user can enter an integer number from 1-100 and then the program starts and generates all numbers starting from 1 up to 2^n. It writes the result into the output.txt file. At the end of the program it displays the required time.


Here are some benchmark results on my machine for this simple program:


I would like to be able to use multithreading or multiprocessing so that the program runs not only on one thread/core but optionally on several or all cores available to the system. The load would have to be shared, similar to Python with concurrent feautures with which I had the best experience.

The very best would of course be the use of CUDA, but I have absolutely no idea how to write the kernel for this.A typical sequence of operations for a CUDA C program is:

Declare and allocate host and device memory.
Initialize host data.
Transfer data from the host to the device.
Execute one or more kernels.
Transfer results from the device to the host.

If anyone could assists with a simple basic structure as a template, that would help me a lot. I am very grateful for any tips.