I decided (about two hours ago) that GJSieve 2.0 was going to calculate the Proth number in a separate thread.
So, I implemented that. In retrospect, I don't really know why. Turns out that the reason GJSieve (for Windows, at least) took so long to "calculate" huge numbers was not due to the calculation at all - it was the printing of the number to the box!
So now, I am faced with a choice - find a way to incrementally print the calculated number to the box that does not involve a single giant string, or else severely limit the size of the numbers the user can test (rendering the application essentially useless).
Currently, if I were to calculate a number 3 million digits in length, it takes 0.003 seconds. However, the time taken to print it to the display box is seemingly (and inconveniently) infinite. I cannot quite tell if the thread is actually hanging or working (as CPU and memory usage remain quite high), but I'm willing to bet that writing a 3 million digit number to what is essentially an array with 3 million slots, followed by performing the necessary conversion to a wide-character array (also 3 million in length) is a generally terrible idea.
In C++, array length is virtually unlimited, yet physically highly limited. The first limit is obviously stack size, which I increased all the way to 25MB (which is admittedly small) before stopping to head off to work. I wasn't getting overflows...yet. The second limit is physically installed memory, of which I must rather hesitantly admit I have only 4GB - yes, even on my custom-built, highly optimized NCS Northwave machine.
The solution which first came to mind is using a vector to cycle through the number's digits and essentially print them one at a time, pushing and popping Assembly-style as necessary. This is not exactly possible, nor would it be much fun to write.
The other idea I had is to use gmp_snprintf() instead of mpz_get_str(). This should fill up, but not exceed, the buffer initialized with the size of the Proth number. sprintf() has no protection against this. Oops!
At any rate, I will have to try all that at some other time...
So, I implemented that. In retrospect, I don't really know why. Turns out that the reason GJSieve (for Windows, at least) took so long to "calculate" huge numbers was not due to the calculation at all - it was the printing of the number to the box!
So now, I am faced with a choice - find a way to incrementally print the calculated number to the box that does not involve a single giant string, or else severely limit the size of the numbers the user can test (rendering the application essentially useless).
Currently, if I were to calculate a number 3 million digits in length, it takes 0.003 seconds. However, the time taken to print it to the display box is seemingly (and inconveniently) infinite. I cannot quite tell if the thread is actually hanging or working (as CPU and memory usage remain quite high), but I'm willing to bet that writing a 3 million digit number to what is essentially an array with 3 million slots, followed by performing the necessary conversion to a wide-character array (also 3 million in length) is a generally terrible idea.
In C++, array length is virtually unlimited, yet physically highly limited. The first limit is obviously stack size, which I increased all the way to 25MB (which is admittedly small) before stopping to head off to work. I wasn't getting overflows...yet. The second limit is physically installed memory, of which I must rather hesitantly admit I have only 4GB - yes, even on my custom-built, highly optimized NCS Northwave machine.
The solution which first came to mind is using a vector to cycle through the number's digits and essentially print them one at a time, pushing and popping Assembly-style as necessary. This is not exactly possible, nor would it be much fun to write.
The other idea I had is to use gmp_snprintf() instead of mpz_get_str(). This should fill up, but not exceed, the buffer initialized with the size of the Proth number. sprintf() has no protection against this. Oops!
At any rate, I will have to try all that at some other time...
No comments:
Post a Comment