DoubleMark (Prime Benchmark) - Open Source - Page 5 - Overclock.net

Licht · 02-26-08

Quote:

Originally Posted by shinya

I dunno what algorithms you're using to check primality (i didn't see the code), but a lot of research has been done on such stuff.

Since your objective is stressing the system for benchmarking purposes, maybe you've no actual interest in efficiency - which eventually add complexity. But maybe you might wanna consider some cleaver stuff for future releases.

The "standard" algorithm to find prime numbers from 2 up to N is called Sieve of Eratosthenes. http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
It's easy to implement with a single core, but i have no idea how to adapt it for multiple cores! It sounds hard!

Other than that, you might be aware of the mersenne prime search http://www.mersenne.org (which found only mersenne primes, which is a prime in the form 2^p - 1, where p is a prime number), and the math behind it http://www.mersenne.org/math.htm

Hope it helps! Happy coding!

I detect a prime number in a single line of code. I divide it by a number and if it comes out without any decimals places it is not a prime number. If it does not come out even then i proceed to increase the number again and again until it either detects it as not a prime number or the divisor reaches half the value of the number in question in which case we go to the next number 2 numbers up. Well in single threaded thats how it works. In multithreading it increases the number by 2 times the number of threads so that all threads continually check different numbers and in the end add their results together. I'm quite proud of how efficient the code is.

Code:

while (Continue == true) // ///////////////////////Benching loop
            {
                if (CurrentDivisor > (CurrentNumber / 2)) // ///////Skip if larger then half
                {
                    CurrentNumber += RelInc;
                    CurrentDivisor = 2;
                    ThisPrimes += 1;
                }
                if (CurrentNumber > (TestLength - 1))
                {
                    if (ThreadCount == 1)
                    {
                        FoundPrimes += ThisPrimes;
                        Time2 = (Convert.ToDecimal(DateTime.Now.Millisecond)
                            + (Convert.ToDecimal(DateTime.Now.Second) * 1000)
                            + (Convert.ToDecimal(DateTime.Now.Minute) * 60000)
                            + (Convert.ToDecimal(DateTime.Now.Hour) * 3600000)) - Time;
                        MessageBox.Show("Time to complete : "
                            + Convert.ToString(Time2)
                            + "ms - Prime Numbers found : "
                            + Convert.ToString(FoundPrimes));
                        Rad1.Enabled = true;
                        Rad2.Enabled = true;
                        Rad3.Enabled = true;
                        Rad4.Enabled = true;
                        Rad5.Enabled = true;
                        Rad6.Enabled = true;
                        Rad7.Enabled = true;
                        Rad8.Enabled = true;
                        Rad9.Enabled = true;
                        Rad10.Enabled = true;
                        Rad11.Enabled = true;
                        Rad12.Enabled = true;
                        Rad13.Enabled = true;
                        Rad14.Enabled = true;
                        Rad15.Enabled = true;
                        Btn2.Enabled = true;
                        Btn1.Text = "Benchmark";
                        Btn1.Enabled = true;
                        FoundPrimes = 1;
                        progressBar1.Value = 0;
                        ThreadsFinished = 0;
                        Continue = false;
                        Thread.CurrentThread.Abort();
                    }
                    else
                    {
                        if (ThreadsFinished == (ThreadCount - 1))
                        {
                            FoundPrimes += ThisPrimes;
                            Time2 = (Convert.ToDecimal(DateTime.Now.Millisecond)
                                + (Convert.ToDecimal(DateTime.Now.Second) * 1000)
                                + (Convert.ToDecimal(DateTime.Now.Minute) * 60000)
                                + (Convert.ToDecimal(DateTime.Now.Hour) * 3600000)) - Time;
                            MessageBox.Show("Time to complete : " 
                                + Convert.ToString(Time2) 
                                + "ms - Prime Numbers found : " 
                                + Convert.ToString(FoundPrimes));
                            Rad1.Enabled = true;
                            Rad2.Enabled = true;
                            Rad3.Enabled = true;
                            Rad4.Enabled = true;
                            Rad5.Enabled = true;
                            Rad6.Enabled = true;
                            Rad7.Enabled = true;
                            Rad8.Enabled = true;
                            Rad9.Enabled = true;
                            Rad10.Enabled = true;
                            Rad11.Enabled = true;
                            Rad12.Enabled = true;
                            Rad13.Enabled = true;
                            Rad14.Enabled = true;
                            Rad15.Enabled = true;
                            Btn2.Enabled = true;
                            Btn1.Text = "Benchmark";
                            Btn1.Enabled = true;
                            FoundPrimes = 1;
                            progressBar1.Value = 0;
                            ThreadsFinished = 0;
                            Continue = false;
                            Thread.CurrentThread.Abort();
                        }
                        else
                        {
                            FoundPrimes += ThisPrimes;
                            ThreadsFinished += 1;
                            Continue = false;
                            Thread.CurrentThread.Abort();
                        }
                    }
                }
                if (Decimal.Round(CurrentNumber / CurrentDivisor, 0) == (CurrentNumber / CurrentDivisor)
                    | Decimal.Round(CurrentNumber / CurrentDivisor, 0) - 1 == (CurrentNumber / CurrentDivisor))
                {
                    CurrentDivisor = 2;
                    CurrentNumber += RelInc;
                    if (Convert.ToDecimal(ThreadNumber) == 1)
                    {
                        progressBar1.Value = Convert.ToInt32((CurrentNumber / TestLength) * 100); //
                    }
                }
                else
                {
                    CurrentDivisor += 1;
                }
            }

That code is actually bad anymore looking at it. The new code i am working on should be monstrously more efficient. Theres really too many checks involved there... the big issue is multi threading which adds quite a bit of code.

Quote:

What kind of help do you need? I'm in a class now that's entirely about the line between hardware and software, and I would be very interested in applying what I'm learning

If you want to get involved my messengers are.

YIM/MSN : dager332@yahoo.com
Xfire : dekustars

We can talk more there. Or over PM (not preferred) if you don't have any messengers. I do need help working on an algorithm at the moment... quite complex...

rabidgnome229 · 02-26-08

That really only tests the floating point divide performance, which is an extremely slow and relatively uncommon instruction. I hate to say it so bluntly, but that's a pretty bad benchmark. Is that the entire thing?

Licht · 02-26-08

Quote:

Originally Posted by rabidgnome229

That really only tests the floating point divide performance, which is an extremely slow and relatively uncommon instruction. I hate to say it so bluntly, but that's a pretty bad benchmark. Is that the entire thing?

I'm adding more tests next build. For the most part of the code that is it. You can of course change the division to multiplication. Quite easily actually. I was not aware that division was a complicated instruction for the CPU to carry out. That and the fact its a floating point instruction gives AMD a massive advantage if i remember correctly... Hm. Anyways might as well spill it i'm working on multi-threaded pi calculation among other things.

rabidgnome229 · 02-26-08

Quote:

Originally Posted by Licht

I'm adding more tests next build. For the most part of the code that is it. You can of course change the division to multiplication. Quite easily actually. I was not aware that division was a complicated instruction for the CPU to carry out. That and the fact its a floating point instruction gives AMD a massive advantage if i remember correctly... Hm. Anyways might as well spill it i'm working on multi-threaded pi calculation among other things.

Floating point is slower than integer, and divide is as slow as it gets. As an example, a PIII can perform an integer add in 1 clock cycle, integer multiply in 4, and integer divide in 36. Floating point numbers are 3, 5, and 38.

Licht · 02-26-08

Quote:

Originally Posted by rabidgnome229

Floating point is slower than integer, and divide is as slow as it gets. As an example, a PIII can perform an integer add in 1 clock cycle, integer multiply in 4, and integer divide in 36. Floating point numbers are 3, 5, and 38.

Very interesting information. So turn division into multiplication (simple enough) and avoid numbers 3, 5, and 38 and you should notice decent-great performance gains?

The Bartender Paradox · 02-26-08

Just a few nitpicks on the algorithm, you only need to check up to the square root of the number in question, not half the number. Also, If you wanted to keep the calculations in integers you can use the remainder function to see if a number evenly divides (remainder = 0)

Licht · 02-26-08

Quote:

Originally Posted by The Bartender Paradox

Just a few nitpicks on the algorithm, you only need to check up to the square root of the number in question, not half the number. Also, If you wanted to keep the calculations in integers you can use the remainder function to see if a number evenly divides (remainder = 0)

Ah, very handy. Decimals are slower then Integers aren't they? (Meaning i think so but i am not sure.)

rabidgnome229 · 02-26-08

Quote:

Originally Posted by Licht

Very interesting information. So turn division into multiplication (simple enough) and avoid numbers 3, 5, and 38 and you should notice decent-great performance gains?

The numbers 3 5 and 38 are the clock cycles per floating point add, multiply and divide respectively.

The focus isn't be getting it to run as fast as possible. A good benchmark should try to test common instructions, weighted by how common they are. The instructions you test would depend on what kind of benchmark you want. Real-world apps tend to use different instructions than multimedia apps or scientific apps, for example

Quote:

Originally Posted by Licht

Ah, very handy. Decimals are slower then Integers aren't they? (Meaning i think so but i am not sure.)

Anything with a decimal is stored as a floating point number. Floating point instructions are generally a good bit slower than integer

Licht · 02-26-08

Quote:

The numbers 3 5 and 38 are the clock cycles per floating point add, multiply and divide respectively.

The focus isn't be getting it to run as fast as possible. A good benchmark should try to test common instructions, weighted by how common they are. The instructions you test would depend on what kind of benchmark you want. Real-world apps tend to use different instructions than multimedia apps or scientific apps, for example

Ok ok i see what you are talking about.

Quote:

Anything with a decimal is stored as a floating point number. Floating point instructions are generally a good bit slower than integer

Ok so ditch everything decimal and move to integers and multiplication in every possible situation. Ok will be simple enough to work with the new engine. (I haven't started on pi, i am working on Prime Numerization now and it won't take long, should be done with that much today. Then i will start researching on pi and probably conquer some other things while im at it.)

rabidgnome229 · 02-26-08

Quote:

Originally Posted by Licht

Ok ok i see what you are talking about.

Ok so ditch everything decimal and move to integers and multiplication in every possible situation. Ok will be simple enough to work with the new engine. (I haven't started on pi, i am working on Prime Numerization now and it won't take long, should be done with that much today. Then i will start researching on pi and probably conquer some other things while im at it.)

You should still test floating point and still test division, because both are important. You just shouldn't only test fp division

		Overclock.net - Overclocking.net > Software, Programming and Coding > Coding and Programming
DoubleMark (Prime Benchmark) - Open Source

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)