草庐IT

ruby - 为什么 10^9942066 是我可以计算而不会溢出的最大功率?

coder 2025-05-24 原文

在 ruby​​ 中,一些大数大于无穷大。通过二分查找,我发现:

(1.0/0) > 10**9942066.000000001 # => false
(1.0/0) > 10**9942066 # => true
RUBY_VERSION # => "2.3.0"

为什么是这样? 109942066有什么特别之处?它似乎不是像 9999999 这样的任意数字,它不接近任何 2 的幂(它大约等于 233026828.36662442)。

为什么 ruby 的无穷大不是无穷大? 109942066是怎么参与的?

我现在意识到,任何大于 109942066 的数字都会溢出到无穷大:
10**9942066.000000001 #=> Infinity
10**9942067 #=> Infinity

但这仍然留下了问题:为什么是 109942066?

最佳答案

TL;博士

我在里面做了计算numeric.cint_pow手动检查整数溢出(以及对 Bignum 的传播,包括对 rb_big_pow 的调用)发生的位置。一旦调用rb_big_pow碰巧检查您在 int_pow 中是否获得了两个中间值是否太大,并且截止值似乎只是在 9942066 左右(如果您使用 10 的底数作为幂)。大约这个值接近

BIGLEN_LIMIT / ceil(log2(base^n)) * n ==
32*1024*1024 / ceil(log2(10^16)) * 16 ==
32*1024*1024 / 54 * 16 ~=
9942054

哪里BIGLEN_LIMIT是 ruby​​ 中的内部限制,用作常量来检查功率计算是否太大,并定义为 32*1024*1024 . base是 10,而 n是仍然适合 Fixnum 的基数的最大 2 次幂指数。

不幸的是,由于用于计算大数幂的算法,我找不到比这种近似更好的方法,但如果您的代码需要在对大数取幂之前检查有效性,它可能足以用作上限.

原问题:

问题不在于 9942066,而在于您的数字之一是整数,另一个是浮点数。所以
(10**9942066).class # => Bignum
(10**9942066.00000001).class # => Float

第一个在内部可以用一个特定的数字来表示,它小于 Infinity .第二个,因为它仍然是一个浮点数,不能用实际数字表示,并简单地替换为 Infinity ,当然不大于 Infinity .

更新的问题:

您是对的,9942066 似乎存在一些差异(如果您在 Linux 下使用 64 位 ruby​​,因为在其他系统下限制可能不同)。虽然 ruby​​ 确实使用 GMP 库来处理大数字,但它甚至在进入 GMP 之前会进行一些预检查,如您可以收到的警告所示。它还将使用 GMP 的 mul 命令手动进行取幂,而不调用 GMP 的 pow 函数。

幸运的是,警告很容易捕捉到:
irb(main):010:0> (10**9942066).class
=> Bignum

irb(main):005:0> (10**9942067).class
(irb):5: warning: in a**b, b may be too big
=> Float

然后你实际上可以检查这些警告是在 ruby​​ 的 bignum.c 中的哪里发出的。图书馆。

但首先我们需要进入 Bignum 领域,因为我们的两个数字都是简单的 Fixnum。计算的初始部分,以及从 fixnum 到 bignum 的“升级”是在 numeric.c 内完成的。 . Ruby 进行快速求幂,并在每一步检查结果是否仍然适合 Fixnum(比系统位大小少 2 位:64 位机器上的 62 位)。如果不是,它会将值转换为 Bignum 领域,并在那里继续计算。我们对这种转换发生的时间点很感兴趣,所以让我们试着在我们的 10^9942066 中找出它何时发生。示例(我使用 ruby​​ 的 numeric.c 代码中存在的 x,y,z 变量):
x = 10^1  z = 10^0   y = 9942066
x = 10^2  z = 10^0   y = 4971033
x = 10^2  z = 10^2   y = 4971032
x = 10^4  z = 10^2   y = 2485516
x = 10^8  z = 10^2   y = 1242758
x = 10^16 z = 10^2   y = 621379
x = 10^16 z = 10^18  y = 621378
x = OWFL

此时 x 将溢出( 10^32 > 2^62-1 ),因此该过程将通过计算 x**y 在 Bignum 领域继续进行。 , 即 (10^16)^621378 (在这个阶段实际上仍然是两个 Fixnum)

如果您现在返回 bignum.c并检查它如何确定一个数字是否太大,您可以看到它将检查保持x所需的位数。 ,然后将此数字乘以 y .如果结果大于 32*1024*1024 ,然后它将失败(发出警告并使用基本浮点数进行计算)。
(10^16)是 54 位 ( ceil(log_2(10^16)) == 54 ), 54*621378是 33554412。这仅比 33554432(小 20)略小,在此之后 ruby​​ 不会做 Bignum 取幂,而只是简单地转换 y加倍,并希望最好(显然会失败,然后返回 Infinity )

现在让我们试着用 9942067 来检查一下:
x = 10^1   z = 10^0    y = 9942067
x = 10^1   z = 10^1    y = 9942066
x = 10^2   z = 10^1    y = 4971033
x = 10^2   z = 10^3    y = 4971032
x = 10^4   z = 10^3    y = 2485516
x = 10^8   z = 10^3    y = 1242758
x = 10^16  z = 10^3    y = 621379
x = 10^16  z = OWFL

这里,在 z 溢出点( 10^19 > 2^62-1 ),计算将在 Bignum 域上继续,并计算 x**y .注意这里会计算(10^16)^621379 , 而同时 (10^16)仍然是 54 位,54*621379是 33554466,比 33554432(大 34)。由于它较大,您会收到警告,而 ruby​​ 只会使用 double 进行计算,因此结果为 Infinity .

请注意,这些检查仅在您使用幂函数时进行。这就是为什么您仍然可以这样做 (10**9942066)*10 ,因为在进行普通乘法时不存在类似的检查,这意味着您可以在 ruby​​ 中实现自己的快速取幂方法,在这种情况下,它仍然可以使用更大的值,尽管您将不再进行此安全检查。例如,请参阅此快速实现:
def unbounded_pow(x,n)
  if n < 0
    x = 1.0 / x
    n = -n
  end
  return 1 if n == 0
  y = 1
  while n > 1
    if n.even?
      x = x*x
      n = n/2
    else
      y = x*y
      x = x*x
      n = (n-1)/2
    end
  end
  x*y
end

puts (10**9942066) == (unbounded_pow(10,9942066)) # => true
puts (10**9942067) == (unbounded_pow(10,9942067)) # => false 
puts ((10**9942066)*10) == (unbounded_pow(10,9942067)) # => true

但是我怎么知道特定碱基的截止值?

我的数学不太好,但我可以说出一种方法来估算截止值的位置。如果您检查上述调用,您可以看到当中间基数达到 Fixnum 的限制时,会发生 Fixnum 和 Bignum 之间的转换。这个阶段的中间底总是有一个指数,它是 2 的幂,所以你只需要最大化这个值。例如,让我们尝试计算 12 的最大截止值。

首先,我们必须检查可以存储在 Fixnum 中的最高基数是多少:
ceil(log2(12^1)) = 4
ceil(log2(12^2)) = 8
ceil(log2(12^4)) = 15
ceil(log2(12^8)) = 29
ceil(log2(12^16)) = 58
ceil(log2(12^32)) = 115

我们可以看到12^16是我们可以存储在 62 位中的最大值,或者如果我们使用的是 32 位机器 12^8将适合 30 位(ruby 的 Fixnums 最多可以存储比机器大小限制少两位的值)。

对于 12^16我们可以很容易地确定截止值。它将是 32*1024*1024 / ceil(log2(12^16)) , 即 33554432 / 58 ~= 578525 .我们现在可以很容易地在 ruby​​ 中检查这个:
irb(main):004:0> ((12**16)**578525).class
=> Bignum
irb(main):005:0> ((12**16)**578526).class
(irb):5: warning: in a**b, b may be too big
=> Float

现在我们不想回到我们最初的 12 基地。 .截止日期将在 578525*16 附近(16 是新底的指数),即 9256400 .如果您检查 ruby​​,这些值实际上非常接近这个数字:
irb(main):009:0> (12**9256401).class
=> Bignum
irb(main):010:0> (12**9256402).class
(irb):10: warning: in a**b, b may be too big
=> Float

关于ruby - 为什么 10^9942066 是我可以计算而不会溢出的最大功率?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36631573/

有关ruby - 为什么 10^9942066 是我可以计算而不会溢出的最大功率?的更多相关文章

  1. ruby - 如何使用 Nokogiri 的 xpath 和 at_xpath 方法 - 2

    我正在学习如何使用Nokogiri,根据这段代码我遇到了一些问题:require'rubygems'require'mechanize'post_agent=WWW::Mechanize.newpost_page=post_agent.get('http://www.vbulletin.org/forum/showthread.php?t=230708')puts"\nabsolutepathwithtbodygivesnil"putspost_page.parser.xpath('/html/body/div/div/div/div/div/table/tbody/tr/td/div

  2. ruby - 如何从 ruby​​ 中的字符串运行任意对象方法? - 2

    总的来说,我对ruby​​还比较陌生,我正在为我正在创建的对象编写一些rspec测试用例。许多测试用例都非常基础,我只是想确保正确填充和返回值。我想知道是否有办法使用循环结构来执行此操作。不必为我要测试的每个方法都设置一个assertEquals。例如:describeitem,"TestingtheItem"doit"willhaveanullvaluetostart"doitem=Item.new#HereIcoulddotheitem.name.shouldbe_nil#thenIcoulddoitem.category.shouldbe_nilendend但我想要一些方法来使用

  3. Ruby 解析字符串 - 2

    我有一个字符串input="maybe(thisis|thatwas)some((nice|ugly)(day|night)|(strange(weather|time)))"Ruby中解析该字符串的最佳方法是什么?我的意思是脚本应该能够像这样构建句子:maybethisissomeuglynightmaybethatwassomenicenightmaybethiswassomestrangetime等等,你明白了......我应该一个字符一个字符地读取字符串并构建一个带有堆栈的状态机来存储括号值以供以后计算,还是有更好的方法?也许为此目的准备了一个开箱即用的库?

  4. ruby - 使用 RubyZip 生成 ZIP 文件时设置压缩级别 - 2

    我有一个Ruby程序,它使用rubyzip压缩XML文件的目录树。gem。我的问题是文件开始变得很重,我想提高压缩级别,因为压缩时间不是问题。我在rubyzipdocumentation中找不到一种为创建的ZIP文件指定压缩级别的方法。有人知道如何更改此设置吗?是否有另一个允许指定压缩级别的Ruby库? 最佳答案 这是我通过查看ruby​​zip内部创建的代码。level=Zlib::BEST_COMPRESSIONZip::ZipOutputStream.open(zip_file)do|zip|Dir.glob("**/*")d

  5. ruby - 为什么我可以在 Ruby 中使用 Object#send 访问私有(private)/ protected 方法? - 2

    类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc

  6. ruby-on-rails - 使用 Ruby on Rails 进行自动化测试 - 最佳实践 - 2

    很好奇,就使用ruby​​onrails自动化单元测试而言,你们正在做什么?您是否创建了一个脚本来在cron中运行rake作业并将结果邮寄给您?git中的预提交Hook?只是手动调用?我完全理解测试,但想知道在错误发生之前捕获错误的最佳实践是什么。让我们理所当然地认为测试本身是完美无缺的,并且可以正常工作。下一步是什么以确保他们在正确的时间将可能有害的结果传达给您? 最佳答案 不确定您到底想听什么,但是有几个级别的自动代码库控制:在处理某项功能时,您可以使用类似autotest的内容获得关于哪些有效,哪些无效的即时反馈。要确保您的提

  7. ruby-on-rails - rails : keeping DRY with ActiveRecord models that share similar complex attributes - 2

    这似乎应该有一个直截了当的答案,但在Google上花了很多时间,所以我找不到它。这可能是缺少正确关键字的情况。在我的RoR应用程序中,我有几个模型共享一种特定类型的字符串属性,该属性具有特殊验证和其他功能。我能想到的最接近的类似示例是表示URL的字符串。这会导致模型中出现大量重复(甚至单元测试中会出现更多重复),但我不确定如何让它更DRY。我能想到几个可能的方向...按照“validates_url_format_of”插件,但这只会让验证干给这个特殊的字符串它自己的模型,但这看起来很像重溶液为这个特殊的字符串创建一个ruby​​类,但是我如何得到ActiveRecord关联这个类模型

  8. ruby - 在 Ruby 中使用匿名模块 - 2

    假设我做了一个模块如下:m=Module.newdoclassCendend三个问题:除了对m的引用之外,还有什么方法可以访问C和m中的其他内容?我可以在创建匿名模块后为其命名吗(就像我输入“module...”一样)?如何在使用完匿名模块后将其删除,使其定义的常量不再存在? 最佳答案 三个答案:是的,使用ObjectSpace.此代码使c引用你的类(class)C不引用m:c=nilObjectSpace.each_object{|obj|c=objif(Class===objandobj.name=~/::C$/)}当然这取决于

  9. ruby - 其他文件中的 Rake 任务 - 2

    我试图在一个项目中使用rake,如果我把所有东西都放到Rakefile中,它会很大并且很难读取/找到东西,所以我试着将每个命名空间放在lib/rake中它自己的文件中,我添加了这个到我的rake文件的顶部:Dir['#{File.dirname(__FILE__)}/lib/rake/*.rake'].map{|f|requiref}它加载文件没问题,但没有任务。我现在只有一个.rake文件作为测试,名为“servers.rake”,它看起来像这样:namespace:serverdotask:testdoputs"test"endend所以当我运行rakeserver:testid时

  10. ruby - 如何在 Ruby 中顺序创建 PI - 2

    出于纯粹的兴趣,我很好奇如何按顺序创建PI,而不是在过程结果之后生成数字,而是让数字在过程本身生成时显示。如果是这种情况,那么数字可以自行产生,我可以对以前看到的数字实现垃圾收集,从而创建一个无限系列。结果只是在Pi系列之后每秒生成一个数字。这是我通过互联网筛选的结果:这是流行的计算机友好算法,类机器算法:defarccot(x,unity)xpow=unity/xn=1sign=1sum=0loopdoterm=xpow/nbreakifterm==0sum+=sign*(xpow/n)xpow/=x*xn+=2sign=-signendsumenddefcalc_pi(digits

随机推荐