Shell arithmetic is broken for integer values beyond the system's maximum float precision

[McDutchie]

The C standard says (1, 2):

When a value of integer type is converted to a real floating type, if the value being converted can be represented exactly in the new type, it is unchanged. If the value being converted is in the range of values that can be represented but cannot be represented exactly, the result is either the nearest higher or nearest lower representable value, chosen in an implementation-defined manner. If the value being converted is outside the range of values that can be represented, the behavior is undefined.

Thing is, ksh internally typecasts all values for shell arithmetic to Sfdouble_t, a.k.a. _ast_fltmax_t as derived by the features/float test, i.e., the system's maximum-size float type.

So, all arithmetic is internally done with long double or double values (depending on the system). See streval.c and arith.c. This breaks long integers, as their values may be too large to be represented exactly by the Sfdouble_t type, in which case we hit the implementation-defined behaviour case and the number will be somehow approximated. This is disastrous, because integer calculations that remain within type range must always be exact.

The problem is particularly terrible on ARM systems, whose hardware does not support long double, so Sfdouble_t is double. E.g., on my Mac with an M1 processor:

$ getconf LLONG_MAX
9223372036854775807
$ typeset -lui i=9223372036854775807   # long unsigned int; this value should be only half its max
$ echo $i 
9223372036854775807
$ echo $((i - 1))
9223372036854775807
$ echo $((i - 2))
9223372036854775807
$ echo $((i - 100))
9223372036854775807
$ echo $((i - 1000))
9223372036854774784
$ echo $((i - 100000))
9223372036854675456
$ echo $((i - 1000000))
9223372036853775360
$ echo $((i - 10000000))
9223372036844775424
$ echo $((i - 100000000))
9223372036754776064

Whereas, on x86_64, we get inexact representations when we go beyond LLONG_MAX:

$ typeset -lui i=9223372036854775807
$ echo $((i+1))
9.22337203685477581e+18
$ echo $((i-1))
9223372036854775806

What this shows is that the whole arithmetic subsystem is broken by design. Internally converting integers to floats and back is bogus, because even the largest float type cannot store all the possible integer values. Integers must be stored and calculated as integers, and nothing else.

We need to find a way, somehow, of making that happen, while still supporting floating point arithmetic as well. But the streval.c and arith.c code is so inscrutable, I'm not very much closer to understanding it now than I was when I forked ksh four years ago.

[McDutchie]

Just some links to remember when debugging this later:

• https://stackoverflow.com/a/70797617
• https://stackoverflow.com/a/45927313
• https://www.sciencedirect.com/science/article/pii/S1571066115000468?ref=pdf_download&fr=RR-2&rr=8a8ffe6538f663c8

[hyenias]

To help clarify the extent of impact of ksh's use of double (64bit) floats for integer operations, here are some observations:

From Double-precision floating-point format, the following is stated:

Precision limitations on integer values

• Integers from −2⁵³ to 2⁵³ (−9,007,199,254,740,992 to 9,007,199,254,740,992) can be exactly represented.
• Integers between 2⁵³ and 2⁵⁴ = 18,014,398,509,481,984 round to a multiple of 2 (even number).
• Integers between 2⁵⁴ and 2⁵⁵ = 36,028,797,018,963,968 round to a multiple of 4.
• Integers between 2ⁿ and 2ⁿ⁺¹ round to a multiple of 2ⁿ⁻⁵².

Let's test that on various hardware.

Intel x86_64 having 80bit long doubles having extended presicion:

~$ bash -c 'for ((i=50; i<68; i++)); do echo $(($i+1)) bits: $(((1<<$i)-1)), $((1<<$i)), $(((1<<$i)+1)); done'
51 bits: 1125899906842623, 1125899906842624, 1125899906842625
52 bits: 2251799813685247, 2251799813685248, 2251799813685249
53 bits: 4503599627370495, 4503599627370496, 4503599627370497
54 bits: 9007199254740991, 9007199254740992, 9007199254740993
55 bits: 18014398509481983, 18014398509481984, 18014398509481985
56 bits: 36028797018963967, 36028797018963968, 36028797018963969
57 bits: 72057594037927935, 72057594037927936, 72057594037927937
58 bits: 144115188075855871, 144115188075855872, 144115188075855873
59 bits: 288230376151711743, 288230376151711744, 288230376151711745
60 bits: 576460752303423487, 576460752303423488, 576460752303423489
61 bits: 1152921504606846975, 1152921504606846976, 1152921504606846977
62 bits: 2305843009213693951, 2305843009213693952, 2305843009213693953
63 bits: 4611686018427387903, 4611686018427387904, 4611686018427387905
64 bits: 9223372036854775807, -9223372036854775808, -9223372036854775807
65 bits: 0, 1, 2
66 bits: 1, 2, 3
67 bits: 3, 4, 5
68 bits: 7, 8, 9
~$ zsh -c 'for ((i=50; i<68; i++)); do echo $(($i+1)) bits: $(((1<<$i)-1)), $((1<<$i)), $(((1<<$i)+1)); done'
51 bits: 1125899906842623, 1125899906842624, 1125899906842625
52 bits: 2251799813685247, 2251799813685248, 2251799813685249
53 bits: 4503599627370495, 4503599627370496, 4503599627370497
54 bits: 9007199254740991, 9007199254740992, 9007199254740993
55 bits: 18014398509481983, 18014398509481984, 18014398509481985
56 bits: 36028797018963967, 36028797018963968, 36028797018963969
57 bits: 72057594037927935, 72057594037927936, 72057594037927937
58 bits: 144115188075855871, 144115188075855872, 144115188075855873
59 bits: 288230376151711743, 288230376151711744, 288230376151711745
60 bits: 576460752303423487, 576460752303423488, 576460752303423489
61 bits: 1152921504606846975, 1152921504606846976, 1152921504606846977
62 bits: 2305843009213693951, 2305843009213693952, 2305843009213693953
63 bits: 4611686018427387903, 4611686018427387904, 4611686018427387905
64 bits: 9223372036854775807, -9223372036854775808, -9223372036854775807
65 bits: 0, 1, 2
66 bits: 1, 2, 3
67 bits: 3, 4, 5
68 bits: 7, 8, 9
~$ ksh -c 'for ((i=50; i<68; i++)); do echo $(($i+1)) bits: $(((1<<$i)-1)), $((1<<$i)), $(((1<<$i)+1)); done'
51 bits: 1125899906842623, 1125899906842624, 1125899906842625
52 bits: 2251799813685247, 2251799813685248, 2251799813685249
53 bits: 4503599627370495, 4503599627370496, 4503599627370497
54 bits: 9007199254740991, 9007199254740992, 9007199254740993
55 bits: 18014398509481983, 18014398509481984, 18014398509481985
56 bits: 36028797018963967, 36028797018963968, 36028797018963969
57 bits: 72057594037927935, 72057594037927936, 72057594037927937
58 bits: 144115188075855871, 144115188075855872, 144115188075855873
59 bits: 288230376151711743, 288230376151711744, 288230376151711745
60 bits: 576460752303423487, 576460752303423488, 576460752303423489
61 bits: 1152921504606846975, 1152921504606846976, 1152921504606846977
62 bits: 2305843009213693951, 2305843009213693952, 2305843009213693953
63 bits: 4611686018427387903, 4611686018427387904, 4611686018427387905
64 bits: -9.22337203685477581e+18, -9223372036854775808, -9223372036854775807
65 bits: 0, 1, 2
66 bits: 1, 2, 3
67 bits: 3, 4, 5
68 bits: 7, 8, 9

Aarch64 with 128bit long doubles ARMv8:

~$ bash -c 'for ((i=50; i<68; i++)); do echo $(($i+1)) bits: $(((1<<$i)-1)), $((1<<$i)), $(((1<<$i)+1)); done'
51 bits: 1125899906842623, 1125899906842624, 1125899906842625
52 bits: 2251799813685247, 2251799813685248, 2251799813685249
53 bits: 4503599627370495, 4503599627370496, 4503599627370497
54 bits: 9007199254740991, 9007199254740992, 9007199254740993
55 bits: 18014398509481983, 18014398509481984, 18014398509481985
56 bits: 36028797018963967, 36028797018963968, 36028797018963969
57 bits: 72057594037927935, 72057594037927936, 72057594037927937
58 bits: 144115188075855871, 144115188075855872, 144115188075855873
59 bits: 288230376151711743, 288230376151711744, 288230376151711745
60 bits: 576460752303423487, 576460752303423488, 576460752303423489
61 bits: 1152921504606846975, 1152921504606846976, 1152921504606846977
62 bits: 2305843009213693951, 2305843009213693952, 2305843009213693953
63 bits: 4611686018427387903, 4611686018427387904, 4611686018427387905
64 bits: 9223372036854775807, -9223372036854775808, -9223372036854775807
65 bits: 0, 1, 2
66 bits: 1, 2, 3
67 bits: 3, 4, 5
68 bits: 7, 8, 9
~$ zsh -c 'for ((i=50; i<68; i++)); do echo $(($i+1)) bits: $(((1<<$i)-1)), $((1<<$i)), $(((1<<$i)+1)); done'
51 bits: 1125899906842623, 1125899906842624, 1125899906842625
52 bits: 2251799813685247, 2251799813685248, 2251799813685249
53 bits: 4503599627370495, 4503599627370496, 4503599627370497
54 bits: 9007199254740991, 9007199254740992, 9007199254740993
55 bits: 18014398509481983, 18014398509481984, 18014398509481985
56 bits: 36028797018963967, 36028797018963968, 36028797018963969
57 bits: 72057594037927935, 72057594037927936, 72057594037927937
58 bits: 144115188075855871, 144115188075855872, 144115188075855873
59 bits: 288230376151711743, 288230376151711744, 288230376151711745
60 bits: 576460752303423487, 576460752303423488, 576460752303423489
61 bits: 1152921504606846975, 1152921504606846976, 1152921504606846977
62 bits: 2305843009213693951, 2305843009213693952, 2305843009213693953
63 bits: 4611686018427387903, 4611686018427387904, 4611686018427387905
64 bits: 9223372036854775807, -9223372036854775808, -9223372036854775807
65 bits: 0, 1, 2
66 bits: 1, 2, 3
67 bits: 3, 4, 5
68 bits: 7, 8, 9
$ ksh -c 'for ((i=50; i<68; i++)); do echo $(($i+1)) bits: $(((1<<$i)-1)), $((1<<$i)), $(((1<<$i)+1)); done'
51 bits: 1125899906842623, 1125899906842624, 1125899906842625
52 bits: 2251799813685247, 2251799813685248, 2251799813685249
53 bits: 4503599627370495, 4503599627370496, 4503599627370497
54 bits: 9007199254740991, 9007199254740992, 9007199254740993
55 bits: 18014398509481983, 18014398509481984, 18014398509481985
56 bits: 36028797018963967, 36028797018963968, 36028797018963969
57 bits: 72057594037927935, 72057594037927936, 72057594037927937
58 bits: 144115188075855871, 144115188075855872, 144115188075855873
59 bits: 288230376151711743, 288230376151711744, 288230376151711745
60 bits: 576460752303423487, 576460752303423488, 576460752303423489
61 bits: 1152921504606846975, 1152921504606846976, 1152921504606846977
62 bits: 2305843009213693951, 2305843009213693952, 2305843009213693953
63 bits: 4611686018427387903, 4611686018427387904, 4611686018427387905
64 bits: -9223372036854775809, -9223372036854775808, -9223372036854775807
65 bits: 0, 1, 2
66 bits: 1, 2, 3
67 bits: 3, 4, 5
68 bits: 7, 8, 9

ARMv7l with 64bit doubles:

~$ bash -c 'for ((i=50; i<68; i++)); do echo $(($i+1)) bits: $(((1<<$i)-1)), $((1<<$i)), $(((1<<$i)+1)); done'
51 bits: 1125899906842623, 1125899906842624, 1125899906842625
52 bits: 2251799813685247, 2251799813685248, 2251799813685249
53 bits: 4503599627370495, 4503599627370496, 4503599627370497
54 bits: 9007199254740991, 9007199254740992, 9007199254740993
55 bits: 18014398509481983, 18014398509481984, 18014398509481985
56 bits: 36028797018963967, 36028797018963968, 36028797018963969
57 bits: 72057594037927935, 72057594037927936, 72057594037927937
58 bits: 144115188075855871, 144115188075855872, 144115188075855873
59 bits: 288230376151711743, 288230376151711744, 288230376151711745
60 bits: 576460752303423487, 576460752303423488, 576460752303423489
61 bits: 1152921504606846975, 1152921504606846976, 1152921504606846977
62 bits: 2305843009213693951, 2305843009213693952, 2305843009213693953
63 bits: 4611686018427387903, 4611686018427387904, 4611686018427387905
64 bits: 9223372036854775807, -9223372036854775808, -9223372036854775807
65 bits: -1, 0, 1
66 bits: -1, 0, 1
67 bits: -1, 0, 1
68 bits: -1, 0, 1
~$ zsh -c 'for ((i=50; i<68; i++)); do echo $(($i+1)) bits: $(((1<<$i)-1)), $((1<<$i)), $(((1<<$i)+1)); done'
51 bits: 1125899906842623, 1125899906842624, 1125899906842625
52 bits: 2251799813685247, 2251799813685248, 2251799813685249
53 bits: 4503599627370495, 4503599627370496, 4503599627370497
54 bits: 9007199254740991, 9007199254740992, 9007199254740993
55 bits: 18014398509481983, 18014398509481984, 18014398509481985
56 bits: 36028797018963967, 36028797018963968, 36028797018963969
57 bits: 72057594037927935, 72057594037927936, 72057594037927937
58 bits: 144115188075855871, 144115188075855872, 144115188075855873
59 bits: 288230376151711743, 288230376151711744, 288230376151711745
60 bits: 576460752303423487, 576460752303423488, 576460752303423489
61 bits: 1152921504606846975, 1152921504606846976, 1152921504606846977
62 bits: 2305843009213693951, 2305843009213693952, 2305843009213693953
63 bits: 4611686018427387903, 4611686018427387904, 4611686018427387905
64 bits: 9223372036854775807, -9223372036854775808, -9223372036854775807
65 bits: -1, 0, 1
66 bits: -1, 0, 1
67 bits: -1, 0, 1
68 bits: -1, 0, 1
~$ ksh -c 'for ((i=50; i<68; i++)); do echo $(($i+1)) bits: $(((1<<$i)-1)), $((1<<$i)), $(((1<<$i)+1)); done'
51 bits: 1125899906842623, 1125899906842624, 1125899906842625
52 bits: 2251799813685247, 2251799813685248, 2251799813685249
53 bits: 4503599627370495, 4503599627370496, 4503599627370497
54 bits: 9007199254740991, 9007199254740992, 9007199254740992
55 bits: 18014398509481984, 18014398509481984, 18014398509481984
56 bits: 36028797018963968, 36028797018963968, 36028797018963968
57 bits: 72057594037927936, 72057594037927936, 72057594037927936
58 bits: 144115188075855872, 144115188075855872, 144115188075855872
59 bits: 288230376151711744, 288230376151711744, 288230376151711744
60 bits: 576460752303423488, 576460752303423488, 576460752303423488
61 bits: 1152921504606846976, 1152921504606846976, 1152921504606846976
62 bits: 2305843009213693952, 2305843009213693952, 2305843009213693952
63 bits: 4611686018427387904, 4611686018427387904, 4611686018427387904
64 bits: -9223372036854775808, -9223372036854775808, -9223372036854775808
65 bits: -1, 0, 1
66 bits: -1, 0, 1
67 bits: -1, 0, 1
68 bits: -1, 0, 1

Confirmed. Integer operations are safe up to the 53bits (2⁵³) on machines that do not possess a greater precision for long double than 64bits as pointed out being Apple M1, M2, and M3 and ARMv7 chips. Not sure if Apple M4 still only has 64bit max precision as M4 maybe ARMv9 compatiable chipset. Almost all ARMv8 chips have supported 128bit floats for many years. For Intel, since forever. I hope Apple closes this gap and includes a floating point processor that supports a better precision than Intel such as 128bit or better.

Since Intel's significand is 63bits in size, ksh should be able to support at least signed 64bit integers with a high probability of unsigned 64 bit integers as sign bit is available in addition to the significand.

On the above output for Intel using ksh, the following is displayed, 64 bits: -9.22337203685477581e+18, -9223372036854775808, -9223372036854775807. For whatever reason, scientific notation is being used to output the value on the first column. As noted by @McDutchie, similar situation also occurs possibly on the same 64bit boundary. Perhaps there is some sort of conditional statement or such resetting things or providing a ceiling or floor messing up when crossing the 64 bit boundary.

Please also note the difference in output when output goes beyond 64 bits, 32bit system was "-1, 0, 1" but for 64bit systems was "0, 1, 2".

[BetterScripts]

Recently discovered this independently - been a long time since I found such a... um... fun(?)... bug!

Not sure it adds much, but for the record (on x86_64):

$ i=9223372036854775807
$ echo $i
9223372036854775807

$ j=$((i+1))
$ echo $j
9.22337203685477581e+18

$ printf '%d\n' $j
ksh93: printf: warning: 9.22337203685477581e+18: overflow exception
9223372036854775807

$ echo $((j-1))
9.22337203685477581e+18

$ echo $((j-i))
3

$ echo $((j-3))
9223372036854775807

$ while test j -gt i; do j=$((j - 1)); done # <- Infinite loop

FWIW also verified this affects 93u+ 2012-08-01 (the earliest version I had available) - which is as you likely expected anyway.

[hlangeveld]

test j -gt i

Is always true. It compares two strings.

[McDutchie]

test j -gt i

Is always true. It compares two strings.

Not on ksh93; j and i are treated as arithmetic expressions, so this is equivalent to test $((j)) -gt $((i)).

Since that behaviour is not POSIX compliant, I've disabled that in the POSIX mode on ksh 93u+m (full rationale in c898e3e):

$ (set --posix; test j -gt i)
ksh: test: j: bad number

Besides (as you can see from the error message above), -gt never compares strings; that would be > (which should be written as \>, '>' or ">" since that needs to be quoted to avoid it being treated as a redirection operator).