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.
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.
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).
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.
(Note that I'm not too clear how valuable this would be. Just asking why that isn't a valid path.)
No, that's completely false. You don't need an Int19 but an Int1.
class bignum {
private:
digit_t *limbs;
public:
bignum(int val);
~bignum();
bignum operator +(const bignum &rhs);
...
};Not so for loops and accumulator constructs.
What is the width of `i` in:
foo(int count) {
int i = 0;
for (int j = 0; j < count; j++) {
i = i + i;
}
}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.
The problem you can then run into is that a mathematical operation can OOM
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
yz...
x
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).
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.
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.
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.
As you indicate though there's no need for this to be something the user of the type needs to think about.
The problem in C that you can avoid is not taking into account the destination type of a calculation.
If you have in16 + int16, being assigned, returned or passed to a int32 type, then the calculation can be done in int32.
If the result is going back to an int16 type, then there is no need to go to int32.
In C expressions, the types are almost purely synthesized attributes: what that term means is that the information flows up the abstract syntax tree from the children to the parents. in a = b + c, the type of (b + c) is determined without regard for the parent = node. This is very simple and has the benefit of being not only easy to understand but in some ways referentially transparent: when we move (b + c) elsewhere, it retains its meaning (except for the part of what happens to the resulting value in the new context). More sophisticated rules can reduce errors though.
By the way, if int has 16 bits (which is rare nowadays), then the calculation will happen in 16 bits. If int has more than 16 bits, then both operands will be promoted to that size before the operation.
if (a < b)
return a + (b - a) / 2;
return b + (a - b) / 2;
return a - (a - b) / 2;Which tweet?
min(a,b) + (max(a,b) - min(a,b))>>1
Smalltalk had first class fraction objects as part of it's transcendental number system. There's a great story about Dan Ingalls changing one line of code to make all of the original Smalltalk BitBlt transparently work with fractions. I always miss having fractions as part of the transcendental math experience in "very high level languages".
The downside of these approaches, is that you can optimize some paths so that things stay relatively quick, but other paths will really slow down all of a sudden.
For example, in Smalltalk,
16r7FFFFFFF timesRepeat: [ self fastOp ]
16r7FFFFFFF + 1 timesRepeat: [ self fastOp ]
If you wanted it to wrap around, you could use an expression like "a = (a+1) % 256", or maybe something like Ada's modular types.
Exactly, Ada's modular types would be a good option in this case, if that is what you want (my feeling is, most likely not unless you are doing some low level stuff). An alternative would be to rewrite the for loop in a functional or range based style.
In algorithmic code, you almost never want overflow. If you have a little function to calculate something, you want the intermediate variables to be big enough to perform the calculation, and in the end you cast it down to the size needed (maybe the compiler can do it, but maybe you know from some mathematical principles that the number is in a certain range and do it manually). In any case, I would want to be warned by the compiler if I am:
1. loosing precision
2. performing a wrong calculation (overflowing)
3. accidentially loosing performance (using bignums when avoidable)
1 and 2 can happen in C if you are not careful. 3 could theoretically happen in Python I guess, but it handles the transition int <-> bignum transparently good enough so it was never an issue for me.
You're proposing a language where you cannot increment integers? I don't think that would be a very popular language.
a = a &+ 1
a &+= 1
Compared to the %256 option, it has the advantage that, if you change the type of a, you won’t have to remember to change the modulus.
They also chose to not make modular integers separate types. That makes mixing ‘normal’ and modular arithmetic on integers easier (with modular types, you’d have to convert between regular and modular integers all the time) (edit: that also is consistent with the fact that the bitwise operators work with regular ints, and ook not require a special “set of 8/16/32/…” type that’s implemented as an integer)
I wouldn’t know how common such mixing is and, hence, whether that is a good choice.
a = b.wrapping_add(c);Are there any languages other than Lisp and Python that have automatic bignum support?
Clojure makes a gesture toward it, literals are automatically promoted but the normal operators don't do it:
user=> (+ 1 9223372036854775807) ;; max signed int64
Execution error (ArithmeticException) at user/eval5 (REPL:1).
integer overflow
user=> (+ 1 9223372036854775808) ;; one higher % expr 1 + 9223372036854775807
9223372036854775808
% expr 9223372036854775808 + 1
9223372036854775809However they don't have JS compatibility either (Dart does not round off large integers like JS does), so I forget what the point was.
Dart also (very early) had infinite precision fractions. So if you divided 355 by 113 you didn't get 3 or 3.1415... you got the fraction 355/133 which was an instance of a first class numeric type.
Unfortunately this means your numbers can grow to need arbitrary amounts of storage in loops.
A cooler feature would be requiring the compiler to prove the addition wouldn’t overflow.
Wuffs is specialized enough to do exactly that (https://github.com/google/wuffs).
for i in [0, 100]:
// i is known to be in [0, 100]
// the argument is known to be in [0, 200]
do_something(i*2)
integer[modulo 256] a = 0;
while some_condition:
a += 1
integer[0, 1000] b = 0;
while some_condition:
guard if b < 999:
// b is now in [0, 999]
b += 1
In c/c++ it is. Obviously some other languages would disagree.
I think a better example of what GP is thinking about is Rust's approach, where overflowing an u8 panics (in debug builds), but you can do x.wrapping_add(y), x.saturating_add(y), x.checked_add(y) etc., depending on what you want to happen when the operation overflows.
The compiler could use static analysis to keep the size to a minimum, for example in this case:
int32 a
int32 b = 2
var c = a * b
Assuming x and y are 32-bit integers
But it only goes up to 64-bit, then you get overflow again
In practice you'd store them in the next larger integer, so 32 bits for a 17 bit int. If you really want to cut off bits or overflow, you use a cast or modulo.
It seems really weird that the "correct" way to do this calculation is to resort to bit manipulation (which should be an implementation detail IMO).