5 ms·

So, this is basically what dynamic languages do because they _can_ go back an allocate more memory transparently to the developer. However, static languages can

So, this is basically what dynamic languages do because they _can_ go back an allocate more memory transparently to the developer. However, static languages cannot change the size of the values dynamically at runtime without additional memory allocations. In fact, this would likely mean that all numbers must be heap allocated, which will likely be a performance penalty when working in high-performance systems. In these cases, using an algorithm that produces correct results without error with constant memory usage is preferred.

rep_lodsb 4y ago
The result of any expression would still be assigned to a variable or function parameter that has a defined type, so it would be limited to that size. However, intermediate values could automatically use larger registers, the CPU's carry flag, or some other mechanism to expand the range. It would be desirable that every expression either produces the mathematically correct result, or a runtime exception. In many cases it would be easy for the compiler to limit intermediate results to some number of bits (since it knows the maximum allowed range for the final result), but it may be a problem to guarantee this.
webstrand 4y ago
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 stack for the result of the operation. I'm curious which dynamic language reallocates to store larger integers? All of the dynamic languages that I'm familiar with simply store numbers as doubles, with variable width integers being handled by opt-in types.
- 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.
- 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); ... };
PartiallyTyped 4y ago
Haskell is both compiled and has arbitrarily large integers. Granted, Haskell isn't used for high performance systems, but it can be used to generate programs for high performance systems.
kazinator 4y ago
> However, static languages cannot change the size of the values dynamically at runtime without additional memory allocations. That is false; a static language could have bignum integers. E.g. you can easily have a bignum class in C++, which is static. You can't have a variable-length bignum as an unboxed value type. "Language with unboxed value types" and "statically typed language" are separate, somewhat related concepts.
- MaxBarraclough 4y ago
  They're right that this would require additional allocations though, no? As you indicate though there's no need for this to be something the user of the type needs to think about.
  - deleted 4y ago
    [deleted]

rep_lodsb 4y ago

The result of any expression would still be assigned to a variable or function parameter that has a defined type, so it would be limited to that size. However, intermediate values could automatically use larger registers, the CPU's carry flag, or some other mechanism to expand the range. It would be desirable that every expression either produces the mathematically correct result, or a runtime exception. In many cases it would be easy for the compiler to limit intermediate results to some number of bits (since it knows the maximum allowed range for the final result), but it may be a problem to guarantee this.

webstrand 4y ago

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 stack for the result of the operation. I'm curious which dynamic language reallocates to store larger integers? All of the dynamic languages that I'm familiar with simply store numbers as doubles, with variable width integers being handled by opt-in types.

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.
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); ... };

PartiallyTyped 4y ago

Haskell is both compiled and has arbitrarily large integers. Granted, Haskell isn't used for high performance systems, but it can be used to generate programs for high performance systems.

kazinator 4y ago

> However, static languages cannot change the size of the values dynamically at runtime without additional memory allocations. That is false; a static language could have bignum integers. E.g. you can easily have a bignum class in C++, which is static. You can't have a variable-length bignum as an unboxed value type. "Language with unboxed value types" and "statically typed language" are separate, somewhat related concepts.

MaxBarraclough 4y ago
They're right that this would require additional allocations though, no? As you indicate though there's no need for this to be something the user of the type needs to think about.
- deleted 4y ago
  [deleted]