Minimum time reqd. in calculation ??

[A!]

Hi all,
I am writing an application in VB.NET to calculate the first 1000 prime
numbers.
The issue is the performance.....I want the time taken to be minimum !
I can achieve this in around 15 milliseconds now.
Is there any way I can cut down this limit to less than a millisecond ?
Please suggest.
TIA.

 

[Morten Wennevik]

Hi A!,

There is no way we can tell you how to optimize your code when you don't show us the code
There is no way we can compare 15 ms to any of our own code either since you don't tell us what system you are running on.

 

[One Handed Man \( OHM - Terry Burns \)]

Post your code is a good start

--

OHM ( Terry Burns )
. . . One-Handed-Man . . .
If U Need My Email ,Ask Me

Time flies when you don't know what you're doing

 

[A!]

Thanks both of you.
Here's my code :
*****************************

Imports System.Math

Private Sub Button3_Click(ByVal sender As System.Object, ByVal e As
System.EventArgs) Handles Button3.Click

Me.SuspendLayout()

Dim i As Int16 = 3

Dim intCounter As Int16 = 2

Dim intDivider As Int16

Dim intRunner As Int16

Dim bolIsPrime As Boolean

Dim arrPrimes(999) As String

arrPrimes(0) = 2

arrPrimes(1) = 3

Dim sw As New StopWatch


Do While Not intCounter > 999

intDivider = Ceiling(Sqrt(i))

If intDivider > 1 Then

For intRunner = 3 To intDivider Step 2

If (i Mod intRunner) = 0 Then

bolIsPrime = False

Exit For

End If

bolIsPrime = True

Next

If bolIsPrime Then

arrPrimes(intCounter) = i

intCounter += 1

End If

End If

i += 2

Loop

'Comment these three lines out when measuring speed of the algo only

ListBox1.BeginUpdate()

ListBox1.Items.AddRange(arrPrimes)

ListBox1.EndUpdate()

Label1.Text = (sw.Peek() / 10).ToString 'Time elapsed.

Me.ResumeLayout()

End Sub




Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As
System.EventArgs) Handles Button1.Click

ListBox1.Items.Clear()

End Sub

*****************************

Also, I am running this on a P-4, 512 RAM, 40 GB HDD.

Thanks.

 

[Morten Wennevik]

Well, I tried translating your code to C# and I got 218ms (on a Celeron 1.7Ghz) when filling the ListBox and less than 100ns when not filling (ie too small a value for TimeSpan), so the time is spent on filling the ListBox, which I don't think you can speed up.

I had to make a couple of adjustments to your code, so it may not be correct. I also had to guess the contents of StopWatch, but it shouldn't affect speed.
Any C# people may want to try to optimize it (or spot errors in the translation).

public class Form1 : Form
{
public Form1()
{
InitializeComponent();
}

private void button1_Click(object sender, EventArgs e)
{
this.SuspendLayout();
short i = 3;
short intCounter = 2;
short intDivider;
short intRunner;
bool boolIsPrime = false;
object[] arrPrimes = new object[1000];
arrPrimes[0] = 2;
arrPrimes[1] = 3;

StopWatch sw = new StopWatch();

while(intCounter < 1000)
{
intDivider = (short)Math.Ceiling(Math.Sqrt(i));
if(intDivider > 1)
{
for(intRunner = 3; intRunner <= intDivider; intRunner += 2)
{
if((i % intRunner) == 0)
{
boolIsPrime = false;
break;
}

boolIsPrime = true;
}

if(boolIsPrime)
{
arrPrimes[intCounter] = i;
intCounter++;
}
}

i += 2;
}

listBox1.BeginUpdate();
listBox1.Items.AddRange(arrPrimes);
listBox1.EndUpdate();
label1.Text = sw.Peek().ToString();
this.ResumeLayout();
}
}

class StopWatch
{
private DateTime start;
public StopWatch()
{
start = DateTime.Now;
}

public double Peek()
{
TimeSpan s = DateTime.Now - start;
return (double)(s.Ticks) / 10000;
}
}

 

[Niki Estner]

Google for "sieve of erathostenes". I think that should be a lot faster.

Niki

 

[One Handed Man \( OHM - Terry Burns \)]

Whats StopWatch, is this your code ?, if so post it

--

OHM ( Terry Burns )
. . . One-Handed-Man . . .
If U Need My Email ,Ask Me

Time flies when you don't know what you're doing