6 ms·

This should be possible for static languages? Since the width of the operands are known ahead of time, a wider integer can be unconditionally reserved on the st

• Aaargh20318 4y ago
  But if you do this in a static language you’d quickly run out of space anyway. Say you start with two Int16’s. Any addition would result in an Int17. Adding a pair of those together would result in an Int18, and so forth. You’d blow past Int64 in no time.
  • dekhn 4y ago
    I'm pretty sure their intent was to demote the value back to an int16 after completing the midpoint operation.
  • IncRnd 4y ago
    > You’d blow past Int64 in no time. Not really. You only need to preserve according to the msb of each number. If you are adding 0(Int18)+1(Int18), you don't need 1(Int36) anymore than you need 1(Int18) or even 1(Int1).
    • tsimionescu 4y ago
      But you don't know the MSB at compile time in the general case.
    • Aaargh20318 4y ago
      > If you are adding 0(Int18)+1(Int18), you don't need 1(Int36) No, you’d need an Int19. We were talking about statically typed languages, so you need to decide the type at compile-time. If you add two UInt16’s they could both contain up to 0xFFFF, you need 17 bits to store that answer. Basically, with every addition you need 1 more bit than the largest of the two (types, not values) you are adding together to prevent a potential overflow. It’s even worse for multiplication.
      • taeric 4y ago
        Couldn't you have a constraining operation in there to assert that you have enough bits? You are right that we don't know if `a + b` would need more bits than either a or b. However, we could have an assert that allows us to ensure the static constraints are satisfied. And the type system could be used as a place to know where we haven't checked the constraint. (Note that I'm not too clear how valuable this would be. Just asking why that isn't a valid path.)
      • IncRnd 4y ago
        > No, you’d need an Int19. No, that's completely false. You don't need an Int19 but an Int1.
        • Aaargh20318 4y ago
          How do you figure that you can store the result of adding 2 Int18s in an Int1 ? Remember, we’re talking about static types and you don’t know the values at compile time.
  • deleted 4y ago
    [deleted]
• hansvm 4y ago
  Python, common lisp, and perl for starters.
  • webstrand 4y ago
    I didn't know python could do that, that's pretty cool. I gotta disagree on perl, though, even though it can represent numbers outside of the range of a double, it can't manipulate them without converting them into doubles.
    • Sesse__ 4y ago
      “use bignum;” and you can.
  • pacaro 4y ago
    Also scheme and prolog The problem you can then run into is that a mathematical operation can OOM
    • kazinator 4y ago
      I've not seen this in practice. You need some numeric accident involving a higher power operator like exponentiation. In TXR Lisp I made exponentiation n-ary: you can do (expt x y z ...). The associativity is right to left: it means ... z y x rather than the less useful cumulative exponentiation of the same base: yz... x which can easily be obtained as (expt x (* y z ..)). So, anyway, if you apply expt to small list of small operands, you can cons up a big number in rather a hurry. If it is important to prevent a problem like this, a limit can be imposed on bignums (say, large enough for common cryptography to still work).
• andrewla 4y ago
  > Since the width of the operands are known ahead of time Not so for loops and accumulator constructs.
  • jcparkyn 4y ago
    I think it would be reasonable to also have overflowing and checked versions of the operators, for cases where the compiler can't guarantee the size (e.g. mutable variables in loops).
• munificent 4y ago
  > Since the width of the operands are known ahead of time, a wider integer can be unconditionally reserved on the stack for the result of the operation. What is the width of `i` in: foo(int count) { int i = 0; for (int j = 0; j < count; j++) { i = i + i; } }
  • zmgsabst 4y ago
    You probably want i=1 since i=0 is an answer you can predict: i = 0 implies that i = 0 + 0 = 0; so the loop doesn’t evolve, and the whole thing can be optimized to just i = 0. For i=1, the loop simplifies to 2^count and a count-length type, which is the point I think you wanted.
    • munificent 4y ago
      Heh, oops, yes. :)
• kazinator 4y ago
  Static languages can have types which have an unboxed value part (of fixed size) that manages a boxed heap part. class bignum { private: digit_t *limbs; public: bignum(int val); ~bignum(); bignum operator +(const bignum &rhs); ... };