4 ms·
Arbitrary length integers. That is, integers that actually act like integers.
by pfdietz 4y ago
Arbitrary length integers. That is, integers that actually act like integers.
- Zamiel_Snawley 4y agoI agree, this could be a good solution for a lot of situations. People fret about the performance impact, but I'm confident that clever engineers could come up with a way to treat numbers within the typical range(say, signed 64 bit) just as they are today, but if an operation would go out of bounds do the expensive, arbitrary length operation. Emitting some kind of extra warning when those expensive operations are actually done would also be nice.
- pfdietz 4y agoLisp compilers do this (although the integers are 61 bit, not 64, for fixnums in general values), including compile-time style warnings if generic arithmetic operations cannot be optimized. Declarations can be added at performance hotspots, but in almost all places the performance impact doesn't matter.
- tialaramex 4y agoI guess this could arguably make sense as a vocabulary type (provided in the standard library so that everybody agrees on it, not for performance reasons). Right now though you will probably get such a type for free with a library of common maths features you'd likely want to use with it. So the only question is whether there are several different libraries and people would prefer to mix and match.
- pfdietz 4y agoOne can get reasonable performance from them if the language (and ABI) is designed for it. Many implementations of lisp family languages, for example. Most computations will be on fixnums, with a fallback to bignums as required. The fixnums are unboxed. It's nice to require analysis for maximum performance rather than for correctness, since maximum performance usually doesn't matter but correctness usually does.
- deleted 4y ago[deleted]
- nemo1618 4y agoThis is being considered for Go 2: https://github.com/golang/go/issues/19623 https://github.com/golang/go/issues/19623 Personally I'm wary of it: it's not hard to think of adversarial scenarios where this could lead to OOM. On the other hand, adversarially overflowing an int can cause plenty of havoc too...
- chrisshroba 4y agoI like this feature of python, but it's wise to remember that operations that we typically think of as O(1) are actually usually dependent on the length of the input, so allowing arbitrary length integers can cause issues (such as DOS opportunities) in places some people don't think to look. Specifically, Python recently changed the str -> int conversion logic to error on strings beyond a certain length (e.g. `int('1'*4301)` will error.) [1] [1] https://news.ycombinator.com/item?id=32753235 https://news.ycombinator.com/item?id=32753235
- astrange 4y agoThey’re also much more expensive in memory, because you have to separately allocate anything you don’t know the size of. Something being O(N) can also be a security issue since it introduces a timing side channel. I don’t think I’ve ever needed a bignum in my life or even a 64-bit integer (excluding pointers and file sizes). Of course I’ve used them inside black box crypto libraries but they have to be careful with them because of said security issues.
- pfdietz 4y agoAs implemented in lisps they typically don't use more memory than 64 bit longs. That's because fixnums (typically 61 bit signed values) are unboxed, existing in the "pointer" itself; only when numbers fall outside that range do they become bignums that must be heap allocated (and in practice almost all integers are fixnums.)
- dahfizz 4y agoAs long as you don't want fast code, sure.