How to lower program execution time?

Question

How do I reduce the following program execution time:

using System;
using System.Diagnostics;
class LeastMM
{
    static void Main()
    {
        Stopwatch sw = new Stopwatch();
        sw.Start();
        byte[] nums = new byte[5];
        for (byte i = 0; i < nums.Length; i++)
        {
            nums[i] = byte.Parse(Console.ReadLine());
        }
        short? lmm = null;
        //uint currentI = 1;
        byte divisors = 0;
        //for (uint i = 1; i < nums.Length; i++) Console.WriteLine("{0} {1} ", i, nums[i]);
        for (short i = 1; ; i++)
        {
            divisors = 0;
            for (byte j = 0; j < nums.Length; j++)
            {
                if (i % nums[j] == 0) divisors++;
            }
            if (divisors >= 3) 
            {
                lmm = i;
                break;
            }
        }
        Console.WriteLine(lmm);
        sw.Stop();
        Console.WriteLine();
        Console.WriteLine(sw.Elapsed.Seconds + " or " +"0."+sw.Elapsed.Milliseconds);
    }
}

Execution time has to be < 0.25 seconds. I tried not to use loops but four different variables - a, b, c, d, e, also tried to use the smallest decimal type possible. None of these worked. The purpose of this program is to find the least majority divisor between at least 3 of the provided numbers. i.e. the least majority divisor of 1, 2, 3, 4, 5 is 4 because it is divisable by 4, 2, and 1. The numbers are in the range of 1 to 100 inclusive.

The first step would be to start the stop watch *after* the user entered the information, so just before `short? lmm = null`. That way you only calculate the time the computation takes. — Thorsten Dittmar, Dec 13 '12 at 12:56
Profile the code. See what lines are the ones where time is spent. Optimize those - measure to see if you make a difference (may have slowed things down). — Oded, Dec 13 '12 at 13:01
Hi, thanks for the prompt response. Seems like it should be doing it, but when I put it in an online test system it says that it goes over the time limit. — Dex, Dec 13 '12 at 13:03
One more thing: I think you want to use `Elapsed.TotalMilliseconds` instead of `Elapsed.Milliseconds` in your last `Console.WriteLine` — Cristian Lupascu, Dec 13 '12 at 13:06
Or just `sw.Elapsed` -- let `TimeSpan` do the formatting for you. — Jon B, Dec 13 '12 at 13:07
Try to use int instead of byte or short. It might get You some performance increase. Please read this thread to know more: http://stackoverflow.com/questions/2594013/int-short-byte-performance-in-back-to-back-for-loops — Grzegorz Sławecki, Dec 13 '12 at 13:09
What online test system are you using? How can it handle `Console.ReadLine`? — Cristian Lupascu, Dec 13 '12 at 13:11
Just for FYI..instead of calculating num.length for each time use a constant..It may save some time.. — AkshayP, Dec 13 '12 at 13:16
from an informatics view i would question the whole c# approach, c# isn`t exactly the fastest language out there, since it doesn`t even get compiled (only msil`ed). from a mathematicians view one could question your algorithm. say, do you want us to think about a better algorithm? and then there is the thing about the time, where do those arbitrary .24 seconds come from? you know this is machine-dependant? — efkah, Dec 13 '12 at 13:40

Jon B · Answer 1 · 2012-12-13T13:20:47.870

1

When I run this I get 0.0024ms execution time for input = 1,2,3,4,5 -- if I move the timing code to after the ReadLine loop. My PC might be a lot faster than yours, but I can't imagine getting > 0.25 seconds even if you run this on a Speak-n-Spell.

Timing the user input is just plain crazy. If this is being timed by something external, are you sure the inputs are supposed to be read line-by-line, and not passed in via the command line?

edited Dec 13 '12 at 13:20

answered Dec 13 '12 at 13:13

Jon B

51,025
31
133
161

Hello, yes this is a test exam and this is the way the data has to be passed to the console - line by line. Anyway It seems the test system might be bugos, thank you all for the answers. – Dex Dec 13 '12 at 13:32
okay the system is not bugos, it seems that I had to use a bigger integer type .Thanks all for the suggestions – Dex Dec 13 '12 at 20:51

How to lower program execution time?

1 Answers1