4 ms·

Nearly all binary searches and mergesorts are broken in languages with bounded integers.

by borntyping 2y ago

perching_aix 2y ago
And on machines with finite memory, right? Which would be every actual computer ever built?
- socksy 2y ago
  Well I would posit that it would be hard to get to this code in a language with unbounded integers where (low n + high n) causes an OOM error, because in order to run this code, you first need an array n units wide. You could argue that the array itself could take up most of the space leaving no room for the indices, but that's hardly a fault with the algorithm, as now you've got a computer that basically can't do anything due to overloading. Whereas overflowing a 32 bit integer is a much more likely occurrence that arguably the algorithm should account for.
  - chowells 2y ago
    Why does everyone talk about binary search in terms of arrays? Binary search works with any monotonic function. Looking up a value in a sorted array is just a special case of a monotonic function.
    - LegionMammal978 2y ago
      Because the 'bug' as presented in the article applies to binary search over an array that has a natural maximum length. If you weren't using an array, there'd be nothing constraining the magnitude of the indices, so you might as well go straight to bigints.
      - chowells 2y ago
        Of course there's a natural constraint: the type of the function. You can't pass a bigint to a function that expects an int. And if you are just blind casting, it turns out you have a similar bug: you are calling the function with different arguments than you think you are. It's the same underlying problem with a different expression in some cases.
dietr1ch 2y ago
Doing any math with bounded integers considered harmful. At some point during my undergrad I realized this and tried to be really careful when implementing algorithms, but it's stupidly hard to do in a tidy way, at least in old C. It's not practical and people just rather close their eyes and live in blissful avoidance.

Nearly all binary searches and mergesorts are broken in languages with bounded integers.

perching_aix 2y ago

And on machines with finite memory, right? Which would be every actual computer ever built?

socksy 2y ago
Well I would posit that it would be hard to get to this code in a language with unbounded integers where (low n + high n) causes an OOM error, because in order to run this code, you first need an array n units wide. You could argue that the array itself could take up most of the space leaving no room for the indices, but that's hardly a fault with the algorithm, as now you've got a computer that basically can't do anything due to overloading. Whereas overflowing a 32 bit integer is a much more likely occurrence that arguably the algorithm should account for.
- chowells 2y ago
  Why does everyone talk about binary search in terms of arrays? Binary search works with any monotonic function. Looking up a value in a sorted array is just a special case of a monotonic function.
  - LegionMammal978 2y ago
    Because the 'bug' as presented in the article applies to binary search over an array that has a natural maximum length. If you weren't using an array, there'd be nothing constraining the magnitude of the indices, so you might as well go straight to bigints.
    - chowells 2y ago
      Of course there's a natural constraint: the type of the function. You can't pass a bigint to a function that expects an int. And if you are just blind casting, it turns out you have a similar bug: you are calling the function with different arguments than you think you are. It's the same underlying problem with a different expression in some cases.

dietr1ch 2y ago

Doing any math with bounded integers considered harmful. At some point during my undergrad I realized this and tried to be really careful when implementing algorithms, but it's stupidly hard to do in a tidy way, at least in old C. It's not practical and people just rather close their eyes and live in blissful avoidance.