3 ms·

Yep, integer overflow suddenly turns into heap overflow. Not good.

PaulHoule 5y ago
I was reading a 1987 article from Byte magazine that reminded me that many of the plots of "fractals" that you've seen are wrong. Specifically, when people make a plot like https://galileo-unbound.blog/2018/12/10/the-wonderful-world-of-hamiltonian-maps/ https://galileo-unbound.blog/2018/12/10/the-wonderful-world-... you see these areas that look like television static that are wrong. The reason why you see chaotic motion in those areas (a infinite number of unstable fixed points) is that there are an infinite number of stable fixed points and they breed unstable fixed points on the separatrices between them. If you look at the edges of the unstable areas you see a hierarchy of stable islands that come out of resonances having resonances with other resonances that have resonances with even more resonances, etc. If you could run the simulation long enough AND you ran it accurately you'd see that throughout the whole unstable region the chaotic motion weaves around numerous islands of stability it which would make a much more detailed and beautiful plot. If you run this with, say, 64-bit fixed point math, you'd find that the dynamics after 64 doubling times is dominated by rounding errors. So a plot like that is showing just a fraction of the detail that's there. Now you could increase the precision as you run over time and it ought to be possible to use interval math to do a grid search and prove the calculations are accurate, but it turns something that is O(N) in time where N is the number of iterations to something that is O(N^2). In terms of storage it goes from O(1) to O(N). It's one of those problems that usually gets ignored and that's some of the reason why chaos and fractals get less respect and less progress than they deserve. I've been thinking about better ways to draw them however, not because I care about the dynamics themselves, but I want to make more beautiful images and see improved dynamics as the royal road to that.
SuchAnonMuchWow 5y ago
I think those cases are a minority, and in most cases you would have been fine with just slightly larger ints. It doesn't seems to cause any issue in python for example, because the cases where integers grow exponentially (which is the same as making their size grow linearly, so its still slow memory-wise) and without bounds are not all that common. For example, an overflow bug was famous in java for being present in the standard library for a very long time: in a core function performing a binary search, the operation computing the middle of the two bounds was a simple average (max + min)/2, which overflow when max and min are big enough, even if the final result always fit in a standard integer. In a lot of other cases, integer are used to address memory (or to represent array indexes, etc), so in most code they will naturally be restricted by the available amount of memory, even if intermediate computations can temporarily overflow.
- kevingadd 5y ago
  Converting a 'numeric overflow exception' to a 'you eventually run out of memory' failure is much worse, because exhausting memory will cause system-wide impact instead of just killing the individual process handling a request/operation. OOM is also generally handled much worse in software vs throwing an exception at the point where data first exceeds the expected range. Do you really want to kick off the linux oom killer every time someone uploads a corrupted png to your server? In general, it's much better to catch out-of-range/corrupt data early, and silently promoting to a 256-bit int is effectively hiding corrupt data in the majority of cases. The maximum 64-bit int is really big.

I was reading a 1987 article from Byte magazine that reminded me that many of the plots of "fractals" that you've seen are wrong. Specifically, when people make a plot like https://galileo-unbound.blog/2018/12/10/the-wonderful-world-of-hamiltonian-maps/ https://galileo-unbound.blog/2018/12/10/the-wonderful-world-... you see these areas that look like television static that are wrong. The reason why you see chaotic motion in those areas (a infinite number of unstable fixed points) is that there are an infinite number of stable fixed points and they breed unstable fixed points on the separatrices between them. If you look at the edges of the unstable areas you see a hierarchy of stable islands that come out of resonances having resonances with other resonances that have resonances with even more resonances, etc. If you could run the simulation long enough AND you ran it accurately you'd see that throughout the whole unstable region the chaotic motion weaves around numerous islands of stability it which would make a much more detailed and beautiful plot. If you run this with, say, 64-bit fixed point math, you'd find that the dynamics after 64 doubling times is dominated by rounding errors. So a plot like that is showing just a fraction of the detail that's there. Now you could increase the precision as you run over time and it ought to be possible to use interval math to do a grid search and prove the calculations are accurate, but it turns something that is O(N) in time where N is the number of iterations to something that is O(N^2). In terms of storage it goes from O(1) to O(N). It's one of those problems that usually gets ignored and that's some of the reason why chaos and fractals get less respect and less progress than they deserve. I've been thinking about better ways to draw them however, not because I care about the dynamics themselves, but I want to make more beautiful images and see improved dynamics as the royal road to that.

SuchAnonMuchWow 5y ago

I think those cases are a minority, and in most cases you would have been fine with just slightly larger ints. It doesn't seems to cause any issue in python for example, because the cases where integers grow exponentially (which is the same as making their size grow linearly, so its still slow memory-wise) and without bounds are not all that common. For example, an overflow bug was famous in java for being present in the standard library for a very long time: in a core function performing a binary search, the operation computing the middle of the two bounds was a simple average (max + min)/2, which overflow when max and min are big enough, even if the final result always fit in a standard integer. In a lot of other cases, integer are used to address memory (or to represent array indexes, etc), so in most code they will naturally be restricted by the available amount of memory, even if intermediate computations can temporarily overflow.

kevingadd 5y ago
Converting a 'numeric overflow exception' to a 'you eventually run out of memory' failure is much worse, because exhausting memory will cause system-wide impact instead of just killing the individual process handling a request/operation. OOM is also generally handled much worse in software vs throwing an exception at the point where data first exceeds the expected range. Do you really want to kick off the linux oom killer every time someone uploads a corrupted png to your server? In general, it's much better to catch out-of-range/corrupt data early, and silently promoting to a 256-bit int is effectively hiding corrupt data in the majority of cases. The maximum 64-bit int is really big.