I haven’t tried their example with Copilot, but as written their blog post is a great advert for not using their product. The isPrime implementation that it generates is spectacularly bad. When I was 10, I wrote a much better one in QBASIC, so this is badness on the level of handing your keyboard to a small child and asking them to act as an autocomplete function.
It tries to determine if a number is prime by attempting to divide it by every single number between 2 and the number itself and checking that they’re all 0. If that’s the approach that you want to take (rather than building a Sieve of Eratosthenes, which I leaned about in school aged 8, or something more clever) then there are two trivial things that you can do to improve performance:
Don’t test every number. Test only odd numbers. If the number is not divisible by 2, it is not divisible by any multiple of 2. This observation is the thing that leads to a Sieve of Eratosthenes, but you rapidly hit diminishing returns. Skipping even numbers halves your search space. Subsequently skipping multiples of 3 is less of a win, then skipping multiples of 5 is less, and so on.
Stop at sqrt(n) (rounded up). If A % (sqrt(A) + M) == 0 then A / (sqrt(A) + M) < sqrt(A), and so you’ve already found a stopping point. This dramatically reduces your search space.
Just applying a couple of small tweaks to the code will give something vastly faster than the original. Again, these are things that I did in the QBASIC implementation that I wrote when I was 10, using only the mathematical knowledge that I’d gained from school at that age. This isn’t degree-level number theory, it’s just a few obvious hacks to aggressively prune the search space.
I guess if you’re a company that makes money from selling compute time, you’ve got a good incentive to encourage people to write inefficient code, so maybe they view that as a feature, not a bug.
The outer loop is much worse because, if you actually want to compute all prime numbers from 0-100 then you really want a sieve of Sieve of Eratosthenes. It reduces the algorithmic complexity of the problem, whereas my previous hacks just reduce the constant factors.
This is a problem that can be solved efficiently with pre-teen mathematics, yet CodeWhisperer does it very badly. I dread to think how it would fare if you’re trying to solve a difficult problem.
Of course Amazon needed a Copilot competitor…
I haven’t tried their example with Copilot, but as written their blog post is a great advert for not using their product. The
isPrimeimplementation that it generates is spectacularly bad. When I was 10, I wrote a much better one in QBASIC, so this is badness on the level of handing your keyboard to a small child and asking them to act as an autocomplete function.It tries to determine if a number is prime by attempting to divide it by every single number between 2 and the number itself and checking that they’re all 0. If that’s the approach that you want to take (rather than building a Sieve of Eratosthenes, which I leaned about in school aged 8, or something more clever) then there are two trivial things that you can do to improve performance:
sqrt(n)(rounded up). IfA % (sqrt(A) + M) == 0thenA / (sqrt(A) + M) < sqrt(A), and so you’ve already found a stopping point. This dramatically reduces your search space.Just applying a couple of small tweaks to the code will give something vastly faster than the original. Again, these are things that I did in the QBASIC implementation that I wrote when I was 10, using only the mathematical knowledge that I’d gained from school at that age. This isn’t degree-level number theory, it’s just a few obvious hacks to aggressively prune the search space.
I guess if you’re a company that makes money from selling compute time, you’ve got a good incentive to encourage people to write inefficient code, so maybe they view that as a feature, not a bug.
The outer loop is much worse because, if you actually want to compute all prime numbers from 0-100 then you really want a sieve of Sieve of Eratosthenes. It reduces the algorithmic complexity of the problem, whereas my previous hacks just reduce the constant factors.
This is a problem that can be solved efficiently with pre-teen mathematics, yet CodeWhisperer does it very badly. I dread to think how it would fare if you’re trying to solve a difficult problem.