Reduce the Running Time

[karryli]

Hi, is there a way to make the following codes run much faster without changing too much? The goal is in the code.

[altenbach]

---

@karryli wrote:

Hi, is there a way to make the following codes run much faster without changing too much? The goal is in the code.

---

Yes, there is. Try the "Sieve of Eratosthenes".

My old prime code does it in less than 50ms on an old laptop. Is that fast enough?

[karryli]

I know but it's an assignment, so we are not allowed to use someone else's codes.

[karryli]

You are working in UCLA? I think I know who you are. Kyle mentioned you in our workshop before. Hope I can meet you in person!

[altenbach · Accepted solution]

OK, looking at the code, you seem to be using the sieve, but there are many very inefficient constructs.

Here are some ideas:

• To find the first nonzero number, there is no need to rattle over the entire array in a FOR loop just to look for the smallest index, just use search array and search for TRUE. No loop needed. You can start searching from the last found position, no need to search from position 0.
• Instead of squaring for the loop termination condition, do the square-root before the loop and compare without squaring
• There is a primitve for "+1"
• Don't autoidex on the loop boundary, you can carry the running sum in a shift register.
• Except for the 2, you can do the array with only odd numbers.
• You don't need to do searching in the inner loop. The indices to be set to zero can be calculated from first principles. even the number of replacements can be calculated, so you can use an inner FOR loop. It would be easiest to design the initial array so the value corresponds to the index.
• ...

[altenbach]

Yes, I know Kyle. 😄

[karryli]

Thanks so much, Christian.

[altenbach]

In order to compare code, you also need a good benchmarking procedure. How fast did you get so far? 😄

[karryli]

I actually submit a rather navie solution of mine for grades and it takes 0.6s. But I will still study your solution later for a deep understandning of prime numbers. Let me post my submitted soulution here.

[altenbach]

I have not verified the code, but here are some very general comments:

• Never maximize the front panel or block diagram window to fill the screen, especially if it does not contain much. That's very annoying.
• The upper shift register is not needed because you never use its output.
• If you would initialize the shift register with a U64 diagram constant, you would eliminate the coercion dot and eliminate the to U64 conversion inside the loop.
• You don't need U64. Do everything in 32 bits is sufficient. An input that requires U64 would take forever anyway (your code looks like O(N²)).
• N of a FOR loop is I32, so wiring a I64 does not give you anything useful (notice the coercion dot). In fact the code stops immediately using your default value (600851475143) of the control. If you need to iterate more than the range of I32, you need a while loop and your own I64 iteration counter.
• Don't wire the orange wire across the loop boundary. Convert the square root to I32 first.
• ...