ChatGPT fail: Sieve of Eratosthenes

AI
R
ChatGPT
data science

ChatGPT writes buggy R in a quick test

Author

Steve Linberg

Published

December 6, 2022

My flirtation with ChatGPT continues.

A few days ago I had some fun asking it to compose emotive sonnets about data science. That was entertaining, and I maintain that anyone who isn’t recognizing this moment as a major inflection point for authoring content of any kind isn’t paying attention. And yes, this extends to writing code. Some people are (rightly) fearful that AI will be able to write better code than humans very soon, for approximately a nothingth of the cost, and that we might actually be there now. Stackoverflow has temporarily banned ChatGPT, though how they’re going to police that remains a bit of a mystery to me.

There may be some divine symmetry to AI systems obsoleting the human programmers that spawned them, but I don’t think we’re quite there yet. I asked ChatGPT to implement a Sieve of Eratosthenes in R, and this was its confident response:

# Function to implement Sieve of Eratosthenes
sieve <- function(n) {
  # Create a boolean array "prime[0..n]" and
  # initialize all entries it as true.
  # A value in prime[i] will finally be
  # false if i is Not a prime, else true.
  prime <- rep(TRUE, n + 1)

  # Set entries for 0 and 1 to false as
  # they are not prime numbers
  prime[1] <- FALSE
  prime[2] <- TRUE

  # Loop through the array and set the
  # value of each element to false if
  # it is not a prime number.
  for (p in 2:n) {
    if (prime[p]) {
      # Update all multiples of p
      for (i in 2 * p:n) {
        prime[i] <- FALSE
      }
    }
  }

  # Return a vector of prime numbers
  return(which(prime))
}

Pretty impressive. Concise, clean, and commented (well, with a caps typo), with a paragraph of explanatory text below it describing how it works, it initially put a chill down my spine.

Until a few seconds later, when I noticed some obvious issues:

  # Set entries for 0 and 1 to false as
  # they are not prime numbers
  prime[1] <- FALSE
  prime[2] <- TRUE

There are at least 2 bugs here. The first is that R vectors are one-based, not zero-based, and the code uses the numbers being tested as primes as the index for the vector; the code is actually OK, but the comment is wrong. The second is even with the off-by-one index, the code doesn’t do what the comment describes (set two values to false). Also, the second line is redundant because the entire vector has already been initialized to TRUE. And finally, of course, when run, this code produces incorrect output:

> sieve(100)
 [1]   2   3   5   7   9  11  13  15  17  19  21  23  25  27  29  31  33  35  37  39  41  43  45
[24]  47  49  51  53  55  57  59  61  63  65  67  69  71  73  75  77  79  81  83  85  87  89  91
[47]  93  95  97  99 101

Starts off OK, but then 9 appears, and it goes downhill rapidly after that.

It’s easy enough to fix:

  • start the array with FALSE for 1, since 1 is not prime (logic error)
  • use the rounded square root of n for the upper boundary, not n (logic error)
  • use a seq function iterating by p, starting at p^2, to mark the composites; the R code for (i in 2 * p:n) doesn’t do that (language error).
sieve <- function(n) {
  # Create a boolean array "prime[1..n]" and
  # initialize all entries it as true, except
  # for prime[1] = FALSE.
  # A value in prime[i] will finally be
  # false if i is not a prime, else true.
  # 1 is not a prime number; initialize it to FALSE.
  prime <- c(FALSE, rep(TRUE, n - 1))
  
  # Loop through the array and set the
  # value of each element to false if
  # it is not a prime number.
  for (p in 2:floor(sqrt(n))) {
    if (prime[p]) {
      # Update all multiples of p not exceeding n, starting at p^2
      for (i in seq(p ^ 2, n, by = p)) {
        prime[i] <- FALSE
      }
    }
  }
  
  # Return a vector of prime numbers
  return(which(prime))
}

The point of this isn’t to flex on first-year computer-science R; the point is that the code is presented authoritatively by the AI (even with their general disclaimers that things may be wrong), and since a lot of what passes for programming these days seems to be blindly copying and pasting code fragments from Stackoverflow, this is another vector where that could happen.

So: it’s impressive that it got as close as it did; what worries me is how authoritatively it presented its buggy code. People are going to trust these systems, even if they shouldn’t, and since it’s likely to be used by people who aren’t experts, errors like those described above aren’t likely to be easily caught. I’m sure the quality will improve in time – these are the early days – but where is this all leading? The bot was so confident in its assertion that C is a dynamically-typed language the other day that it made me doubt myself after decades of C at the center of my brain’s programming-language orientation. I hadn’t studied it formally in school; had I been wrong about it all along?

Interestingly, the python code the bot produced for the sieve was just fine (I just changed the limit for output comparison):

# MAX_PRIMES = 100000  # maximum number of prime numbers to find
MAX_PRIMES = 100  # maximum number of prime numbers to find

# Sieve of Eratosthenes
# Finds all prime numbers up to MAX_PRIMES using the Sieve of Eratosthenes algorithm
def sieve_of_eratosthenes():
  primes = [True] * MAX_PRIMES  # list to store prime numbers

  # 1 is not a prime number
  primes[1] = False

  # sieve algorithm
  for i in range(2, int(MAX_PRIMES ** 0.5) + 1):
    if primes[i]:
      for j in range(i ** 2, MAX_PRIMES, i):
        primes[j] = False

  # print the prime numbers
  for i in range(1, MAX_PRIMES):
    if primes[i]:
      print(i)

sieve_of_eratosthenes()
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

Exciting times. This technology is amazingly promising, and it’s going to change the world. But the flaws are as dangerous as the strengths are thrilling. Here we go.

Reuse

https://creativecommons.org/licenses/by/4.0/

Citation

BibTeX citation:
@online{linberg2022,
  author = {Steve Linberg},
  title = {ChatGPT Fail: {Sieve} of {Eratosthenes}},
  date = {2022-12-06},
  url = {https://slinberg.net/posts/2022-12-06-chatgpt-sieve},
  langid = {en}
}
For attribution, please cite this work as:
Steve Linberg. 2022. “ChatGPT Fail: Sieve of Eratosthenes.” December 6, 2022. https://slinberg.net/posts/2022-12-06-chatgpt-sieve.