Timing an Algorithm

[Peter.BoyWonder]

So heres the Deal.
I was just messing around and trying to implement a simple recursive function that calculates N! (n factorial). I was also going to write one that does it iteratively and I was going to time the two to figure out which was faster (No BIG O notation here). I have the function working, thats not the problem. The problem is that the Timing aspect doesn't unless I set breakpoints and debug very slowly. Surely there is no way that the algorithm runs so fast that the elapsed time can't be calculated....right? What am I doing wrong? It appears so simple!

Here is the

[SIZE=2][COLOR=#0000ff]Public[/COLOR][/SIZE][SIZE=2][COLOR=#0000ff]Class[/COLOR][/SIZE][SIZE=2] Form1[/SIZE]
 
[SIZE=2][COLOR=#0000ff]Private[/COLOR][/SIZE][SIZE=2][COLOR=#0000ff]Sub[/COLOR][/SIZE][SIZE=2] butCalculate_Click([/SIZE][SIZE=2][COLOR=#0000ff]ByVal[/COLOR][/SIZE][SIZE=2] sender [/SIZE][SIZE=2][COLOR=#0000ff]As[/COLOR][/SIZE][SIZE=2] System.Object, [/SIZE][SIZE=2][COLOR=#0000ff]ByVal[/COLOR][/SIZE][SIZE=2] e [/SIZE][SIZE=2][COLOR=#0000ff]As[/COLOR][/SIZE][SIZE=2] System.EventArgs) [/SIZE][SIZE=2][COLOR=#0000ff]Handles[/COLOR][/SIZE][SIZE=2] butCalculate.Click[/SIZE]
 
[SIZE=2][COLOR=#008000]'Input to calculate N![/COLOR][/SIZE]
[SIZE=2][COLOR=#0000ff]Dim[/COLOR][/SIZE][SIZE=2] n [/SIZE][SIZE=2][COLOR=#0000ff]As[/COLOR][/SIZE][SIZE=2][COLOR=#0000ff]Integer[/COLOR][/SIZE][SIZE=2] = [/SIZE][SIZE=2][COLOR=#0000ff]CInt[/COLOR][/SIZE][SIZE=2](TextBox1.Text)[/SIZE]
 
[SIZE=2][COLOR=#008000]'Capture the time right before the algorithm runs[/COLOR][/SIZE]
[SIZE=2][COLOR=#0000ff]Dim[/COLOR][/SIZE][SIZE=2] starttime [/SIZE][SIZE=2][COLOR=#0000ff]As[/COLOR][/SIZE][SIZE=2] DateTime = DateTime.Now()[/SIZE]
 
[SIZE=2][COLOR=#008000]'Run the N! algorithm[/COLOR][/SIZE]
[SIZE=2]TextBox2.Text = Nfactorial(n)[/SIZE]
 
[SIZE=2][COLOR=#008000]'Capture the time after the algorithm runs[/COLOR][/SIZE]
[SIZE=2][COLOR=#0000ff]Dim[/COLOR][/SIZE][SIZE=2] Endtime [/SIZE][SIZE=2][COLOR=#0000ff]As[/COLOR][/SIZE][SIZE=2] DateTime = DateTime.Now[/SIZE]
 
[SIZE=2][COLOR=#008000]'Calculate the elapsed time of the algorithm running[/COLOR][/SIZE]
[SIZE=2][COLOR=#0000ff]Dim[/COLOR][/SIZE][SIZE=2] span [/SIZE][SIZE=2][COLOR=#0000ff]As[/COLOR][/SIZE][SIZE=2] TimeSpan = Endtime.Subtract(starttime)[/SIZE]
 
[SIZE=2][COLOR=#008000]'Output the elapsed time[/COLOR][/SIZE]
[SIZE=2]MessageBox.Show(span.Milliseconds.ToString)[/SIZE]
[SIZE=2][COLOR=#0000ff]End[/COLOR][/SIZE][SIZE=2][COLOR=#0000ff]Sub[/COLOR][/SIZE]
 
[SIZE=2][COLOR=#0000ff]Private[/COLOR][/SIZE][SIZE=2][COLOR=#0000ff]Function[/COLOR][/SIZE][SIZE=2] Nfactorial([/SIZE][SIZE=2][COLOR=#0000ff]ByVal[/COLOR][/SIZE][SIZE=2] N [/SIZE][SIZE=2][COLOR=#0000ff]As[/COLOR][/SIZE][SIZE=2][COLOR=#0000ff]Integer[/COLOR][/SIZE][SIZE=2]) [/SIZE][SIZE=2][COLOR=#0000ff]As[/COLOR][/SIZE][SIZE=2][COLOR=#0000ff]String[/COLOR][/SIZE]
[SIZE=2][COLOR=#0000ff]If[/COLOR][/SIZE][SIZE=2] N > 1 [/SIZE][SIZE=2][COLOR=#0000ff]Then[/COLOR][/SIZE]
[SIZE=2]N = N * Nfactorial(N - 1)[/SIZE]
[SIZE=2][COLOR=#0000ff]End[/COLOR][/SIZE][SIZE=2][COLOR=#0000ff]If[/COLOR][/SIZE]
[SIZE=2][COLOR=#0000ff]Return[/COLOR][/SIZE][SIZE=2] N[/SIZE]
[SIZE=2][COLOR=#0000ff]End[/COLOR][/SIZE][SIZE=2][COLOR=#0000ff]Function[/COLOR][/SIZE]
 
 
[SIZE=2][COLOR=#0000ff]End[/COLOR][/SIZE][SIZE=2][COLOR=#0000ff]Class[/COLOR][/SIZE]

 

[JohnH]

If the duration is less than a millisecond totalmilliseconds will return 0, there don't exist more precise time measure than millisecond in .Net.

 

[Administrator]

Research the new StopWatch class in VB.NET

Yes, .NET can measure down to nanoseconds I believe, research the precision of the TICK

 

[jmcilhinney]

The TimeSpan has a Ticks property:

The smallest unit of time is the tick, which is equal to 100 nanoseconds. A tick can be negative or positive.

 

[Peter.BoyWonder]

Thanks so much. The stopwatch class works with the elapsedticks property. One question though. Any Idea why it would take almost four times as many ticks to execute the function that I wrote, the first time it is executed, compared to the second, third, fourth etc....?

Here is my code:

PrivateSub butCalculate_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles butCalculate.Click
 
'Input to calculate N!
Dim n AsLong = CInt(TextBox1.Text)
 
Dim StopWatch AsNew Stopwatch 
 
StopWatch.Start()
 
'Run the N! algorithm
TextBox2.Text = reNfactorial(n)
 
StopWatch.Stop()
 
 
'Output the elapsed time
Label4.Text = StopWatch.ElapsedTicks & " Ticks"
 
EndSub
 
PrivateFunction reNfactorial(ByVal N AsLong) AsString
If N > 1 Then
N = N * reNfactorial(N - 1)
EndIf
Return N
EndFunction

 

[JohnH]

This is really strange! First I am partly right, millisecond is the smallest timeunit for datetime/timespan/timer, except the ticks that allow you to calculate smaller units yourself.. StopWatch is one of the new wonders of .Net 2.0, very nice, at first I thought I'd never heard of it, but I think it skipped very fast my mind from a post here at the forum sometime! Anyway, here comes the strangeness, the datetime/timespan ticks is a constant representing 100 nanoseconds, ie 0.1 microseconds, for stopwatch the ticks is dependent of Frequency that tells ticks per second. I just found that my computer is defined 'high-resolution' with 3.579.545 ticks per second, which makes 279 nanoseconds per tick. When my computer is accurate only to 279ns how can the datetime/timespan claim 100ns precision??