[mips/pythagorean-triplet] O(n^2) isn't enough to pass test

Programming MIPS Assembly
1

On MIPS track, simple loop a = from 2 to n: loop b = from a+1 until n-a-b>b: if a*a+b*b==c*c: add result isn’t fast enough; it took 3+min to complete entire test suit.

For reference, on C track, same approach was enough; it took 0.3 sec.

I assume there are better algorithm to solve this problem (maybe O(n)?). However, I think finding / implementing it would beyond “medium” difficulty.

2

We are running an emulator, and that emulator is written in Java. This might explain some of the difference in time.

We can certainly increase the difficulty to Hard. I’d like the track to have 5+ hard exercises so people can earn the “Difficult” trophy. Perhaps

  • all-your-base
  • connect
  • minesweeper
  • pythagorean-triplet
  • zebra-puzzle

Suggestions most welcome.