3 ms·
Getting a Program Right (1)
- dragontamer 7y agoUnfortunately, I've seen this example before and already know the answer. It comes down to this: > To justif a yes answer we need to provide a credible argument that for every t and x the program sets Result as it should. Is there a "reasonable" t or x which breaks the program? We can write test cases all day and never really discover what "t" actually breaks the program. Now spoiler alert: here's the answer. Overflow when t is large, such as a 16GB array with 32-bit integers. At ~4-billion items, the m := (i + j) // 2 does NOT result in a binary-search step correctly. Lets say i is 2-billion, and j is 4-billion. m = 2-billion + 4 billion == 6-billion, but this overflows to ~2-billion or so. As a result, m = (2 billion + 4 billion) // 2, with 32-bit integer math, results in 1-billion. For all array sizes less than 2-billion numbers, I expect the code laid out in the example here to be correct. But in the obscure ~2+ Billion sized array case, you get overflow error. ------------------ Understanding this example is to understand bugs: how and why they form. A "bug" works in the exceptionally common case (say, all array sizes less than 2-billion), until decades later, 16GBs of RAM becomes common and people start to actually run into the bug in practice. Similarly, most of the code we write is implicitly fragile, even if well tested. There may be a time, sometime in the future, where the use case assumptions no longer hold (ie: it becomes reasonable to assume 4GBs or more of RAM on one computer) and suddenly the bug appears.
- Someone 7y agoThe specification of the problem doesn’t say anything about integer size, wrap-around, and the like, so we should assume that they mean ‘mathematical integer’ when they say ‘integer’ One can easily hit a bug in that code for small arrays, even for an array with only 2 elements. There also is an edge condition bug for an array of size zero.