CPU and / or RAM performance when dealing with large integers

Question

Yesterday I solved one exam problem when I found something very interesting (at least for me). The program is designed for factorials (very large), and as a result, the number of zeros at the end of the number (in some cases 2500 zeros ..). Therefore, I did everything I could, but found that when entering a type number 100 000 , exactly 1;30 - 1;33min is required to display the result. I thought this was due to my processor (this is not very fast). I sent .exe to some of my friends to try because they have very good PCs when we talk about performance - exactly the same result ( 1;33min ).

My question is why it is time to solve the problem in the same way. I know that there are better ways to write your own kernel, so it will not take much time, but it is very important for me, as for a novice programmer. So here is my code:

 static void Main() { int num = int.Parse(Console.ReadLine()), zeroCounter = 0; BigInteger fact = 1; var startTime = DateTime.Now; Console.WriteLine(); for (int i = 1; i <= num; i++) { fact *= i; Console.Write("\r{0}", DateTime.Now - startTime); } BigInteger factTarget = fact; while (factTarget % 10 == 0) { factTarget /= 10; zeroCounter++; Console.Write("\r{0}", DateTime.Now - startTime); } Console.WriteLine(); Console.WriteLine("Result is number with {0} zeros.", zeroCounter); Console.WriteLine(); Console.WriteLine("Finished for: {0}", DateTime.Now - startTime); Console.WriteLine(); Console.WriteLine("\nPres any key to exit..."); Console.ReadKey(); } 

I'm sorry. If this is the wrong place to ask, I did my best to find what I was looking for before publishing it.

Answer 1

What I immediately noticed about your code is that you included the Console.WriteLine() statements in your computational cycles.

The fact is that I / O is much slower for a computer than for computing, even under ideal conditions. And I would not say that the Windows console window is a particularly efficient implementation of this particular type of I / O. In addition, I / O operations tend to be less dependent on differences between the processor and memory from machine to machine.

In other words, it seems very likely to me that you are primarily measuring I / O throughput, not computing throughput, and therefore it is not surprising to see consistent results between machines.

What is it worth when I run your example on my laptop, if I turn off the output, I can finish the calculation in about a minute. I get something closer to your 1:30 time if I use the code as is.

EDIT: I also recommend a response from Hans Passant. The I / O memory is still I / O and, as I described above, is much less changed from machine to machine than processor speed. I hope the general description above gives ideas on where the difference might be (without access to each of the machines in question, there really is no way to know exactly what the reason is), but Hans' answer gives very good information about the input problem - memory output in particular and is very worth reading.

Answer 2

Now is the time 00: 01: 23.5856140

The speed of this program is determined by the bandwidth of RAM on your computer. This is a permanent design and is not related to processor speed. RAM plays a role here due to the very large number of digits in the factorial, they no longer fit the processor caches. And the BigInteger multiplication memory access pattern is very unfriendly, all digits must multiply the number.

Your program takes 57 seconds on my laptop, I know that it has PC3-12800 RAM. Which has a maximum transfer rate of 12800 MB / s, gives or takes CAS latency (I do not know). Thus, we can calculate the speed of RAM on your and your machine:

1:23 = 83 s, 57/83 x 12800 = 8790 MB / s.

Which is a pretty close match for the PC3-8500. The frequency of RAM is very common on white-box machines that you received from a manufacturer like Dell. Your friend, fast PC, a little toaster, gently lay it out :)

---

Fwiw, why a highly-supported post doesn’t have a big effect on speed can also use an explanation. The console window used by your program belongs to a different process. Conhost.exe, you can see it on the Processes tab of Taskman.exe. He takes care of scrolling and painting the window, under the hood, your program uses the interaction process to tell him to refresh the window.

This happens when your program is running in a different thread, so your program only gets bogged down when it launches Conhost.exe, sending updates faster than it can handle. So, at the beginning of your program, you are still fast and bogged down. But not when the number of digits begins to increase, and your multiplications begin to slow down. In general, the slowdown is not so great.

Answer 3

What happens is that on the core or processor, the computer has a fixed size of internal buses that store data. The speed of RAM is 10-1000 times slower than the CPU. There's also something called Cache memory, but the cache size is small. So, what is the large amount of RAM that you have on your PC, it will still be slow and take time. Coz, when he reaches High Numbers, the numbers take time to read and write to and from memory.

Plus, I write every time I eat some time on the screen.