time estimate

[snakeeyes1000]

about how much time would it take to save the first million or so prime numbers to a file using VB?(Finding them as well)

[Destined Soul]

Some rudamentary math:

Say you want to find prime numbers up to 1,000,000. Half of these are composite (not prime), so you're down to 500,000 numbers possible. When checking to see if a number is prime, you'll only have to check up to that number's square root. If nothing divided it by that number, then it's prime. So sqrt(1000000) is 1,000. Of these numbers, it's best just to check the list of prime numbers you've already created, so (again) only half of these could be prime.

So we have up to 500 numbers as reference numbers to see if a number's prime, and have to cycle through 500,000 numbers. At MOST, this would be 250 million comparisons (modulo math).

How long does it take vb to do this many computations? Remember, though, that this is a worst case.

I think it'd be less time than it'd take to write the code to check this. Other than that, though, I don't know.

[edit]:I'm curious, would it be faster to use vb's mod function or to write your own?

Destined

[snakeeyes1000]

I'm just asking, I have written a program that get's the a bunch of primes(about a million) and writes them to a file. It takes twenty-thirty minutes;I wanted to know if I should improve my code.

[Destined Soul]

I guess then your question shouldn't be how long does it take, since you've already figured out. What you should ask yourself is if you're doing it in the most efficient way?

The biggest improvement that I know of from brute-force (on all numbers) is to only check previously found prime numbers to see if any of those divide the number in question.

Other methods are to minimize computations done each repetition. A few cycles in each "isPrime" function adds up over a million calls.

I'm curious - have you tried porting your code to C++? It would be interesting to see the difference between the two.

As for seeing if it's worth improving, I guess you have to ask how often the code will be called to generate the list. (Might be easier just to distribute the file once it's created.)

Destined

[snakeeyes1000]

I do the prime number thing like you said; I have optimized it in that form well enough. I will try porting it; I am curious too. It takes about 10-15 minutes if it skips the saving part. thanks.

[Destined Soul]

Wow! 5-10 minutes to save the file? Very interesting.

Sadly, I don't know quite enough about vb to know what the quickest method of writing data is...

Destined

[bugzpodder]

in C++, I suspect it takes <15 seconds. 60 seconds tops.

[Destined Soul]

Actually, I remember there being a thread on this - I think C++ was 10 - 100 times faster. I wonder if I can find that thread...

Destined

[Destined Soul]

I'm not absolutely sure if my code is absolutely correct, but I did 1,000,000 numbers using VB and it ran in less than 40 seconds on my PII 350MHz. (I did a quick'n dirty code creation, but verified that up to 100, it found all of the primes.)

So I'm beginning to wonder, what machine are you using?

Oh, here's a second run:

Find primes: 40.080 seconds
Display to textbox (one LONG string then to text): way too long

Third run: 38.445 seconds
Time to dump data to file: 0.040 seconds

(Dump was:

Dim fileNo As Integer
fileNo = FreeFile
Open "c:\testprime.dat" For Binary Access Write As fileNo
    Put #fileNo, , primeList
Close fileNo

Total size of the file was 306 kb.

Unless, of course, I'm amazingly wrong with my isPrime() code.

Destined

[Destined Soul]

Okay, maybe I'm not fully understanding this:

Are you saying that you take a million numbers and find the primes, or take some large number of, uh, numbers, and get roughly a million primes from that list?

I just set my code to generate the list up to 10 million. Of course, there's no do events or anything, so I can't check the progress until it's done.

Destined

[Destined Soul]

Okay, some results for those who like it:

Find primes in set [2, 10,000,000]:

Found: 664579 primes
Time to find: 9.83 minutes (590 seconds)
Time to dump to file: 0.521 seconds

Times were checked using the GetTickCount API.

This is, assuming, that my code finds all primes and only primes.

If the current progress goes the way it is, to find a million primes would take about 18-22 minutes.

Gonna try this at home on my 1.2GHz w/512 RAM (this only has 128MB on the PII 350.) Then I'll try it in C++.

Destined

[bugzpodder]

no way!! VB is that slow? let me try!

[Destined Soul]

At home, same code:
(AMD 1.2GHz, 512MB PC133, VB6 Enter SP5, WinXP Pro)
(Work: VB6 Pro SP5, Win2k)

time to find primes: 199.667 seconds (3.33 minutes)
time to dump file: 0.811 seconds. (Strange...)
[Edit]: Oh, much better second time, 0.200 seconds to dump

I'm gonna look over the code again.

Destined

[Destined Soul]

Ah, almost identical code in C++, and MUCH better.

Time for numbers up to 10 million: 15.092 seconds
Up to 25 million: 51.824 seconds

(Note 10 million found exact same # primes as VB code, 25 million found 1,565,927 primes)

However, I found that I had to create (dynamically) an array the same size as the number of, uh, numbers I was checking. If C++ constantly made a slightly bigger array each time, it took quite a while (was too lazy). To give vb a fighting chance, I also made its array a large constant size (redim), and shaved off about 20 seconds:

Run 1 (vb) @ 10 million: 178.307 seconds
Run 2 (ditto): 176.204 seconds

Run 3 (vb) @ 25 million (yikes): 524.544 seconds

So, snakeeyes, unless you're running a low level PII or slower, yes, I think the code could be a bit quicker. Out of curiousity, how are you writing the numbers to a file? Does it matter how?

Destined

[DavidHooper]

Yeh, what CPU are you using?

If we're not careful, Keda will wade in here and lecture us that we shouldn't use VB for speed related stuff!

I'm guessing a coupla minutes with output to a file with optimised code in VB.

Or another note, does anyone know the relative performance of VB regular and VB.NET?

[bugzpodder]

I have both on two seperate machines maybe I'll run a test. wanna send me the code?

[snakeeyes1000]

the reason I asked this is because at one time I had a MASM version that ran for the first million or so prime numbers in 5-10 seconds. I was asking because I doubted that a speed difference could be that great; I knew there was a considerable difference, but 10 minutes? ouch. Thanks all.

[DavidHooper]

I have both on two seperate machines maybe I'll run a test. wanna send me the code?

Hi bugz, that would be great. I'll start a new thread tomorrow sometime. We should code it so the test code uses mostly mathematical operations (after all, that's what this forum is lol).

[Alphanos]

Run a search on this forum for code to find prime numbers, I remember that quite a while back Nucleus posted a very nice algorithm. I'm wondering how it compares to the ones you guys are running.