具有大整数和 2 的大幂的 awk 和 gawk

Question

据我了解，POSIX awk 和 GNU awk 都对整数和浮点数使用 IEEE 754 double。（我知道 GNU awk 上的 -M 开关可用于任意精度整数。这个问题假设没有选择 -M...）

这意味着 awk / gawk / perl 的整数结果的最大大小（那些没有自动提升为任意精度整数的）将是 53 位，因为这是 IEEE 双精度的 max size integer that can fit in a IEEE 754 double. (At magnitudes greater than 2^53, you can no longer expect ±1 to work as it would with an integer but floating point arithmetic still works within the limits。）

好像很容易演示。

这些在 awk 和 gawk 上都按预期工作，结果正确（到最后一位）：

$ gawk 'BEGIN{print 2**52-1}'
4503599627370495
$ gawk 'BEGIN{print 2**52+1}'
4503599627370497
$ gawk 'BEGIN{print 2**53-1}'
9007199254740991

这相差 1（这是我期望的 53 位最大整数）：

$ gawk 'BEGIN{print 2**53+1}'      # 9007199254740993 is the correct result
9007199254740992

但这是我不期望的。对于 2 的特定幂值，awk 和 GNU awk 都以比 53 位内可能的精度高得多的精度执行整数运算。

（在我的系统上，/usr/bin/awk 是 MacOS POSIX awk；gawk 是 GNU awk。）

考虑这些例子，都精确到数字：

$ gawk 'BEGIN{print 2**230}'  # float result with awk...
1725436586697640946858688965569256363112777243042596638790631055949824

$ /usr/bin/awk 'BEGIN{print 2**99}'   # max that POSIX awk supports
633825300114114700748351602688

这些量级不支持 ±1 的精度，但支持有限 2 的幂的算术运算。同样，精确到数字：

$ /usr/bin/awk 'BEGIN{print 2**99-2**98}'
316912650057057350374175801344    

$ /usr/bin/awk 'BEGIN{print 2**99+2**98}'
950737950171172051122527404032

$ gawk 'BEGIN{print 2**55-968}'  # 2^55=36028797018963968
36028797018963000

我推测 awk 和 gawk 有某种非标准的方式来识别 2^N 等同于 2<<N 并在该领域内做一些有限的数学运算。

结果大于 2^53 的任何形式的 [integer > 2] ^ Y 都会出现预期的精度下降。即，10^15 是 ±1 的粗略最大整数，因为 10^16 需要 54 位。

$ gawk 'BEGIN{print 10**15+1}'  # correct
1000000000000001

$ gawk 'BEGIN{print 10**16+1}'  # not correct
10000000000000000

10**64 的大小是正确的，但仅前 16 位数字是精确的（我希望如此）：

$ gawk 'BEGIN{print 10**64}'
10000000000000001674705827425446886926697411428962669123675881472
# should be '1' + 64 '0'
# This is just a presentation issue of a value implying greater precision...

GNU document 并不完全是有用，因为它谈到了 64 位无符号和有符号整数的最大值，暗示它们以某种方式使用。但是很容易证明除了 2 的幂之外，gawk 上的最大整数是 2**53

问题：

awk / gawk 中的所有整数计算实际上都是 IEEE 双精度数，±1 的最大值为 2**53，我是否正确？在某处记录了吗？
如果这是正确的，那么更大的 2 次方会发生什么？

（顺便说一句，如果在失去精度的情况下自动切换到浮点格式（Perl 的方式），那就太好了。）

Answer 1

不适用于 2 的所有次方。如您所说，它基于 IEEE 754 double 格式的限制。我能吐出来的最高是2^1023.

2^1024 导致 INF，除非你调用 bignum 模式 -M

就是说，差距开始超过 2^53，并一路增加（当你进一步进入所谓的“次优”范围时。至于打印出来，%d / %i is good for +/- 63-bits in gawk/mawk2，和 %u up to unsigned 64-bits int（但是一旦你超过 2^53，除了 2 的精确幂之外可能不精确）。

mawk 1.3.4 似乎分别限制为 31/32 位。

超过这些范围，%.f 几乎是唯一的出路。

Answer 2

我无法谈论特定版本的 gawk 或 awk 中使用的数字实现。这个答案一般来说是浮点数，特别是 IEEE-754 二进制格式。

Computing 2⁹⁹ for 2**99 and 2²³⁰ for 2**230 只是 floating- 的正常操作点算术。每个都用一个有效二进制数 1 和一个指数 99 或 230 表示。无论使用什么例程来实现求幂运算，都可能正确地完成了它的工作。由于二进制浮点数使用符号、有效数和 2 的某个幂的比例来表示数字，因此 2⁹⁹ 和 2²³⁰ 是容易代表。

打印这些数字时，会调用一些例程将它们转换为十进制数字。该例程似乎也得到了很好的实施，产生了正确的输出。需要做一些工作才能正确进行该转换，因为使用朴素算法实现它会引入产生不正确结果的舍入误差。（有时很少对转换例程进行工程设计，它们产生的结果仅精确到有限数量的有效小数位。这似乎不太常见；正确舍入的实现现在比以前更常见。）

当结果无法准确实现时（例如 2⁵³+1，会出现明显的“精度损失”，更准确地说是“精度损失”或“舍入误差” ) 或者在没有正确舍入的情况下实现浮点运算。对于 2⁹⁹ 和 2²³⁰，浮点格式没有这种损失。

This means that the max size of integer result with awk / gawk / perl… would be 53 bits… ”

这是不正确的，或者至少是措辞不正确。可以用 IEEE-754 64 位二进制表示的最后一个连续整数是 2⁵³。但肯定不是最大值。 2⁵³+2也可以表示，跳过了2⁵³+1。比2⁵³大的整数还有很多可以表示。

Answer 3

关于二的幂的一个特例 -

如果你只想要 2^N-1 的幂为 1023，一个非常干净的 sub() 就可以解决这个问题，而不必亲自去弄清楚最后一个数字是什么：

sub(/[2468]$/, index("1:2:0:3", bits % 4), pow2str)

当你对 4 取模时，2 的正整数幂的最后一位具有这种重复和可预测的模式，

所以使用这个特制的字符串，其中值存在于位置 7/3/1/5（以降模顺序），字符串索引本身已经是最后一位减 1。

e.g. 2^719 : it goes 275. . . . 60288
                                    |                         |
719 % 4 = 3, located at position 7 of reference string "1:2:0:3",

所以正则表达式将最后的“8”替换为“7”，对于 2 的任何巨大整数次方，正好给出 2^N-1。

如果你已经知道这个2的幂应该是多少位，那么这种方式更快，否则，子串替换的方式肯定比运行它通过对数函数更快。

具有大整数和 2 的大幂的 awk 和 gawk

awk and gawk with large integers and large powers of 2

floating-point

awk

integer