Click here to Skip to main content
15,845,436 members
Please Sign up or sign in to vote.
5.00/5 (1 vote)
Hello,

I wrote this program to measure the speed at which different algorithms could determine if a number is prime or not. I do this by looking at how many ticks it takes each algorithm to do this, and then comparing them.

Whether or not this is the best or most reliable way is not really the issue; instead, the problem is that of the two algorithms I wrote, one of them always returns zero -- and so far, it has always been the last one used ("IsPrime2", as you'll see in a moment), which should be giving me some idea what's wrong with my code, but I just can't find whatever it is.

I also had trouble with a earlier and only slightly different version of this code: it returned a negative result during some runs, but only sometimes. Sometimes both values would be positive, or they could both be negative, or one of each. Anyway, enough talk. Here is the code:

C#
using System;

class Program
{
    static long h,  j;
    static DateTime start, end;
    static TimeSpan span { get { return new TimeSpan(end.Ticks - start.Ticks); } }
    static long ticks { get { return end.Subtract(TimeSpan.FromTicks(start.Ticks)).Ticks; } }

    static bool IsPrime1(int p) {
        start = DateTime.Now;
        h = start.Ticks;
        for (int i = 3, n = (int)Math.Sqrt(p); i <= n; i++) {
            if ((p % i) == 0) { end = DateTime.Now; return false; }
        }
        end = DateTime.Now;
        j = end.Ticks;
        return true;
    }

    static bool IsPrime2(int p) {
        start = DateTime.Now;
        if (((p - 1) % 6) != 0 && ((p + 1) % 6) != 0) { end = DateTime.Now; return false; }
        for (int i = 3, n = (int)Math.Sqrt(p); i <= n; i++) {
            if ((p % i) == 0) { end = DateTime.Now; return false; }
        }
        end = DateTime.Now;
        return true;
    }
    
    static void Main(string[] args)
    {
        int p = int.MaxValue;
        while (true) {
            Console.WriteLine("IsPrime1: {0} is {1}a prime ({2}) ({3}, {4})", p, IsPrime1(p) ? "" : "not ", ticks,
                start.Ticks, end.Ticks);
            Console.WriteLine("IsPrime2: {0} is {1}a prime ({2}) ({3}, {4})", p, IsPrime2(p) ? "" : "not ", (end-start).Ticks,
                start.Ticks, end.Ticks);    // ticks instead of (end-start).Ticks still result in 0
            Console.ReadKey(true);
        }
    }
}


It's also a real head scratcher why an earlier date subtracted from a later one, as was the case in the first version of my program, would produce a negative result in terms of ticks.

What I have tried:

See how IsPrime1 & 2 share start and end, but never use them at the same time? I tried putting DateTime.Now in places like the span and ticks properties, but have since replaced it with end.

I tried delaying the IsPrime2 call by putting a ReadKey() between the two calls.
I tried calling IsPrime2 first, but then it's IsPrime1 that returns 0.
I tried creating two new DateTime's: start2 and end2, and a ticks2 property that does end2.Subtract(start2), and using them in IsPrime2 instead of start and end.
Posted
Updated 19-Oct-21 8:10am

No no.
That is not OK.

You can't accurately measure time intervals below one microsecond like that; first of all the system clock doesn't have that fine a resolution, then getting DateTime.Now has a cost involved, and finally there is no guarantee your code will not be interrupted by the OS.

You really must create a loop that executes the same thing many times, and
time the overall loop, then divide. And yes, this makes it more likely to catch some system event, however it will give better real-life values.

I tend to loop for many milliseconds, then use TimeSpan.TotalMilliSeconds.
I avoid using Ticks, those are computer units that may vary by hardware and/or OS.
Even when ticks have a resolution of one tenth of a microsecond, that does not imply the
tick count will be incremented by one every tenth of a microsecond. It may well be incremented by a larger number at a lower frequency.
My very first and old article[^] here on CodeProject discussed some of such timer behavior.


So remove everything time related from your code under test, then create a loop and surround that with your time measurement stuff.

I'm not sure what goes wrong in your isPrime2 time measurement, your code is rather convoluted.

When I run similar tests on my machine, I'm getting 2000 msec twice for 10000 iterations (both in Debug and Release mode); the difference between tests 1 and 2 is negligible, and certainly less than the timing inaccuracy for the given test case. With random values, isPrime2 will be faster of course.

This is part of the code I ran:
static bool test1(int p) {
    bool isPrime = false;
    DateTime start = DateTime.Now;
    for (int i = 0; i < 10000; i++) {
        isPrime = IsPrime1(p);
    }
    DateTime end = DateTime.Now;
    TimeSpan span = end - start;
    Console.WriteLine("IsPrime1: {0} is {1}a prime ({2} ms) ", p, isPrime ? "" : "not ", span.TotalMilliseconds);
    return isPrime;
}

PS: you have an i++ in your for loop; as you start with 3, you'd better use i+=2 skipping all even candidate divisors. (isPrime1 should report 2 being prime though, which it currently does not).

ADDED:

This code helps in understanding how Ticks work:

static void observeTicks() {
    Console.WriteLine("What is the typical increment of Ticks?");
    for (int i = 0; i < 10; i++) {
        long ticks0 = DateTime.Now.Ticks;
        while (true) {
            long tickStep = DateTime.Now.Ticks - ticks0;
            if (tickStep != 0) {
                Console.WriteLine("tickStep=" + tickStep);
                break;
            }
        }
    }
    Console.WriteLine("What is the absolute value of 1,000,000 Ticks?");
    DateTime start = DateTime.Now;
    long weWillExitAt = start.Ticks+1000000;
    DateTime end = DateTime.Now;
    while (true) {
        end = DateTime.Now;
        if (end.Ticks >= weWillExitAt) break;
    }
    TimeSpan span = end - start;
    Console.WriteLine("1,000,000 Ticks = {0} msec", span.TotalMilliseconds);
}

On my system, ticks correspond to a tenth of a microsecond, and tickStep typically is around 10000, i.e. 1 msec. Your isPrime test case takes about 0.2 msec, meaning you have 80% probability of measuring zero time and 20% of measuring 1 msec. Now whenever your program somehow synchronizes to the system clock, specific parts of it may tend to fall early or late in a tick, resulting in a lower or higher probability to yield a non-zero time measurement.
Synchronization might occur at program launch, at every Console operation, at many I/O operations, etc.

If you were to execute something like
Thread.Sleep(1);
...isPrime1(p)...
Thread.Sleep(1);
...isPrime2(p)...
Thread.Sleep(1);
...isPrime1(p)...
Thread.Sleep(1);
...isPrime2(p)...

I expect you'll get many more zero times.
 
Share this answer
 
v4
Comments
BillWoodruff 18-Oct-21 17:43pm    
+5 nice to see you here again, Luc !
Luc Pattyn 18-Oct-21 17:48pm    
Hi Bill, I never stopped visiting the site, however I only occasionally participate as the words fail me to politely describe the average quality and involvement of the questions posted.

:)
BillWoodruff 18-Oct-21 18:10pm    
Hi, "as the words fail me" reminds me of one of my favorite poems "In Broken Images:" by Robert Graves :)

https://ace.home.xs4all.nl/Literaria/Poem-Graves.html
deXo-fan 19-Oct-21 11:22am    
Hi Luc,
I greatly appreciate your answer, but my question is not really about how precise my measurements are. As the title indicates, and as I said in my question, the whole issue here is why IsPrime2 always returns 0.

I'm glad you explained that ticks aren't a good way, and why they aren't reliable. That's very useful information. And I know I might as well have written += 2 instead of ++, but the goal here is also not to optimize my algorithms to determine whether a number is prime or not. I'm simply looking for an explanation as to why the second function I run, be it IsPrime1 or IsPrime2, returns 0. I'm pretty sure that if I run IsPrime2 before IsPrime1, then IsPrime1 will return 0. I think that's what I saw yesterday.

Anyway, thank you for your quick and detailed reply!
Luc Pattyn 19-Oct-21 12:13pm    
I've added some info at the end of my "solution 1" above
i think you need to study the resources listed here, and revise your current strategy. Just solving why your current code doesn't work may mean you end up with working code that is inaccurate. Any serious C# timing should be using GC.Collect, and warm-up runs to factor out JIT costs.

1) Jon Skeet;s benchmarking technique; [^]

2) Steve Parker's articles on benchmarking: [^]

3) explore what BenchMarkDotNet offers: [^], [^]

Andrey Akinshin of JetBrains (imho, a genius), the maintainer of BenchMarkDotNet [^], has written a good book: [^] if you want to "dive deeper."
 
Share this answer
 
v2
Comments
Luc Pattyn 19-Oct-21 13:32pm    
Hmm.
"Any serious C# timing should be using GC.Collect, and warm-up runs to factor out JIT costs."
That may be very true for complex applications, however for the problem at hand it is not IMO, as the code is highly numeric and only a handful of objects are created at all (a few strings reporting results).
BillWoodruff 19-Oct-21 13:38pm    
Good point ! Is there anything in my post you think is valid, or valuable for this OP, or, for future CP members ?
Luc Pattyn 19-Oct-21 14:12pm    
the links are OK, what they refer to is valid in general, however IMO not relevant to the question at hand.
I don't know any future CP member, do you? :D

:)
BillWoodruff 19-Oct-21 14:31pm    
The future users appear in my dreams, voting solutions i have not posted yet to questions they have not asked yet ... #5's :)

imho, the current poster needs an overview of benchmarking; based on awareness of techniques, they can, in the future, make appropriate choices for implementation. Using 'DateTime is a sign to me of lack of knowledge which you address in your post.
deXo-fan 21-Oct-21 6:12am    
I decided to accept Bill's solution as well, I thought it'd be rude not to, and you both gave me some great pointers. Luc, I read the part you added to your answer and you explain it very well! So thank you.

To Bill: I've never used GC.Collect, at least not that I can remember. But I will definitely read up on those articles you posted links to, and your observation that my use of DateTime here is a lack of knowledge is spot on. Thank you to you as well.

You have both been of great help! Have a nice day :)

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900