3 ms·

Hmm, I always figured it was just assumed that, unless otherwise specified, most well-known implementations fail with sufficiently large numbers.

taneq 10y ago
All code running on a machine of finite size will fail (sometimes gracefully, usually not) for sufficiently large input values.
- tgb 10y ago
  But the goal is only to work for the finite number of possible inputs allowed by the input types. There's no reason a finite machine has to fail on those.
  - Retric 10y ago
    Try to pass in data with zero bits of free memory.
    - mrich 10y ago
      That should still result in a clean error, not some kind of undefined behavior.
    - tgb 10y ago
      It's not impossible to guarantee that a system has sufficient memory for all possible inputs. Look at high stakes embedded software development. You need more control than you get as an application on a desktop computer but there's nothing inherent about finite state machines that make them vulnerable.
gfody 10y ago
Yep, this is just vintage click-bait.. you can bet more than sorting routines will fail with numbers approaching 2^63. It doesn't matter because if you're running quick sort on a list of 2^64 entries then something else is going wrong before your (l+r)/2 has a chance to overflow.
- mrich 10y ago
  int in Java and C is 32 bit wide, not 64 bit, this limit is easily reached. You cannot just assume nobody will use your algorithms with large inputs and act like your data types have unlimited range. Such bugs will typically manifest at important customers and be hard to analyze. Better think about your types beforehand and do add runtime checks!
- colejohnson66 10y ago
  If you're trying to sort 2^63 items at once, you have other problems.
mrich 10y ago
What is 'sufficiently large'? Could be anything. A function, especially when part of the standard library, must work correctly for all possible inputs or reject them outright.

taneq 10y ago

All code running on a machine of finite size will fail (sometimes gracefully, usually not) for sufficiently large input values.

tgb 10y ago
But the goal is only to work for the finite number of possible inputs allowed by the input types. There's no reason a finite machine has to fail on those.
- Retric 10y ago
  Try to pass in data with zero bits of free memory.
  - mrich 10y ago
    That should still result in a clean error, not some kind of undefined behavior.
  - tgb 10y ago
    It's not impossible to guarantee that a system has sufficient memory for all possible inputs. Look at high stakes embedded software development. You need more control than you get as an application on a desktop computer but there's nothing inherent about finite state machines that make them vulnerable.

gfody 10y ago

Yep, this is just vintage click-bait.. you can bet more than sorting routines will fail with numbers approaching 2^63. It doesn't matter because if you're running quick sort on a list of 2^64 entries then something else is going wrong before your (l+r)/2 has a chance to overflow.

mrich 10y ago
int in Java and C is 32 bit wide, not 64 bit, this limit is easily reached. You cannot just assume nobody will use your algorithms with large inputs and act like your data types have unlimited range. Such bugs will typically manifest at important customers and be hard to analyze. Better think about your types beforehand and do add runtime checks!
colejohnson66 10y ago
If you're trying to sort 2^63 items at once, you have other problems.

mrich 10y ago

What is 'sufficiently large'? Could be anything. A function, especially when part of the standard library, must work correctly for all possible inputs or reject them outright.