awk和gawk使用大整数和2的大幂

Question

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

这意味着awk / gawk / perl(没有自动提升到任意精度整数的那些)的最大整数大小将是53位，因为这是IEEE 754 double中可以容纳的最大整数大小。(当数量级大于2^53时，你不能再指望1像处理整数那样工作，但是浮点运算仍然在IEEE double的限制内工作。)

这似乎很容易证明。

这些按预期工作，在 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

任何形式的<代码>[整数

$ 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文档并不是很有用，因为它提到了64位无符号和有符号整数的最大值，这意味着它们是以某种方式使用的。但很容易证明，除了2的幂外，gawk上的最大整数是2**53

问题：

> < Li > < p > awk/gawk中的所有整数计算实际上都是IEEE doubles，1的最大值为2**53，我说的对吗？这有记录吗？

如果这是正确的，2的大幂幂会发生什么？

（如果有一个自动切换到浮点格式（就像Perl那样）在那个量级上，顺便说一句，精度会损失，那就太好了。




Answer 1

一个关于2的幂的特例-

如果您只需要1023次幂的2^N-1，一个非常干净的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的幂应该是多少位，那么这种方法更快，否则，子串替换方法肯定比通过对数函数运行它更快。

Answer 2

匿名用户

更新：关于 10 中 754 倍的幂的声明：

有趣的是，即使没有bigint插件，如果你只是在寻找10次幂的独立插件，或者使用它们对2次幂进行mod（%），那么你似乎可以达到10^22。

jot 25 | gawk -be '$++NF = sprintf("%.f", 10^$1)' # same for mawk+nawk

{ … pruned smaller ones… }

13  10000000000000
14  100000000000000
15  1000000000000000
16  10000000000000000

17  100000000000000000
18  1000000000000000000
19  10000000000000000000
20  100000000000000000000

21  1000000000000000000000
22  10000000000000000000000 <---------

23  99999999999999991611392
24  999999999999999983222784
25  10000000000000000905969664

< code> ( 2 ^ x ) % ( 10 ^ 22 )

   jot -w 'x=%d;y=22; print x,"=",y,"=",(2^x)%%(10^y),"\n"; ' - 3 1023 68 | 
   bc      | 
   mawk2 '$++NF = sprintf("\f\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b"\
                                        "\b\b\b\b\b\b\b\b%.f",
                   ( 2 ^ $1 ) % ( 10 ^ $2 ) )'    FS== OFS== |
   column -s= -t | gcat -n

所有2的幂，甚至高达1023，都可以直接获得10^22的精确模，不需要专门的算法、字符串操作或bigint包，这一点已由gnu-bc确认

 1  3     22  8                       
              8

 2  71    22  2361183241434822606848  
              2361183241434822606848

 3  139   22  2991196020261297061888  
              2991196020261297061888

 4  207   22  1983204197482918576128  
              1983204197482918576128

 5  275   22  7804340758912662765568  
              7804340758912662765568

 6  343   22  3047019946172856926208  
              3047019946172856926208

 7  411   22  729696200186866434048   
              729696200186866434048

 8  479   22  3987839644142653145088  
              3987839644142653145088

 9  547   22  1954520592778765795328  
              1954520592778765795328

10  615   22  5333860664072122400768  
              5333860664072122400768

11  683   22  3741475809259744657408  
              3741475809259744657408

12  751   22  1513586051123404341248  
              1513586051123404341248

13  819   22  2458937421726941708288  
              2458937421726941708288

14  887   22  8118143630040815894528  
              8118143630040815894528

15  955   22  3346307143437247315968  
              3346307143437247315968

16  1023  22  2417678164812112068608  
              2417678164812112068608

=============

并不是所有2的幂。正如您所说的，它基于IEEE 754双格式的限制。我能让它吐出的最高值是2^1023。

除非您调用bignum mode -M，否则2^1024会产生INF

也就是说，差距开始跳到 2^53 以上，并在此过程中增加（随着您进一步进入所谓的“次优”范围。至于打印出来，%d / %i 适用于 gawk/mawk2 中的 /- 63 位，%u 适用于无符号的 64 位 int（但除了超过 2^53 的精确幂外，可能不精确）。

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

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

Answer 3

我不能谈论gawk或awk的特定版本中使用的数字实现。这个答案一般针对浮点，尤其是IEEE-754二进制格式。

计算2⁹⁹用于2**99和2²³⁰用于2**230只是浮点运算的普通操作。每个都用一个有意义的数字表示，其中一个有意义的二进制数字为1，指数为99或230。无论使用什么例程来实现指数运算，都可能正确地完成了它的工作。由于二进制浮点表示一个数字，使用符号、有意义和2到某个次幂的缩放，2⁹⁹和2²³⁰很容易表示。

当这些数字被打印出来时，调用某个例程将它们转换成十进制数字。这个例程似乎也实现得很好，产生了正确的输出。要正确完成这种转换，需要做一些工作，因为用简单的算法实现转换会引入舍入误差，从而产生不正确的结果。(有时，在转换程序上几乎不花什么工程功夫，它们产生的结果只精确到有限的有效十进制数字。这似乎不太常见；正确舍入的实现现在比过去更常见。)

明显的“精度损失”，更准确地称为“精度损失”或“舍入错误”，当结果不能精确实现时（例如2⁵³1）或在没有正确舍入的情况下实现浮点运算时会发生。对于2⁹⁹和2²³⁰，浮点格式没有施加这种损失。

这意味着整数的最大大小结果与awk / gawk / perl...将是 53 位..."

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