使用 Mod 比较 Ruby 中的大幂数 10
Comparing large powers in Ruby using Mod 10
我正在尝试编写一个函数来比较一个数字 x1 对另一个数字 x2 的幂是否大于另一个数字 y1 对另一个数字 y2 的幂。
例如，假设我们有一对数字 x。
x = [2,10]
和另一对 y
y = [3,9]
在这种情况下 y1 ** y2 大于 x1 ** x2。
然而，有时会有非常大的、可怕的数字。像这样
x = [935243113, 987702643]
y = [50894069, 704259526]
为了计算这个，我尝试使用 mod 10 算法
(x[0] ** x[1]) % 10 > (y[0] ** y[1]) % 10
然而，显然这个算法不起作用。有没有更高效的算法。
对任意和取 mod 10 并比较它们与取随机数没有太大区别。你无法避免这里的数字规模。 modulo might 有助于确定两个数字是否相等（如果总和 modulo 任何数字不相等，您可以假设它们不相等） .另请注意，Ruby 仍会计算您的情况下的大数 - 但如果您在 modulo 算术中更详细地进行求幂，则可以使用一些技巧来避免这种情况。
对于一个近似的方法，它应该几乎一直有效，那么你可以使用 Math.log( x ** y ) == y * Math.log( x ).
像这样：
(Math.log(x[0]) * x[1]) > (Math.log(y[0]) * y[1])
当我说 almost 时，我的意思是您将自己暴露在此处的浮点误差中。由于 Math.log 中的四舍五入，两个非常大但非常相似的幂运算可能会以错误的顺序出现。我不确定这对于您显示的尺寸的数字是否是一个实际问题。
更新：
2 ** 9 == 8 ** 3
# => true
但是
(Math.log(2) * 9) > (Math.log(8) * 3)
# => true
因此，完全相等的值的舍入错误是一个更严重的问题，并且可能发生在非常低的输入数字上。如果两个输入可能相等并且知道值是否完全不同很重要，则当 log/log 比较的结果非常接近时，您需要回退到不同的机制，例如两个对数和的比率在 1.0 的 1e-6 范围内。
我正在尝试编写一个函数来比较一个数字 x1 对另一个数字 x2 的幂是否大于另一个数字 y1 对另一个数字 y2 的幂。
例如，假设我们有一对数字 x。
x = [2,10]
和另一对 y
y = [3,9]
在这种情况下 y1 ** y2 大于 x1 ** x2。
然而，有时会有非常大的、可怕的数字。像这样
x = [935243113, 987702643]
y = [50894069, 704259526]
为了计算这个，我尝试使用 mod 10 算法
(x[0] ** x[1]) % 10 > (y[0] ** y[1]) % 10
然而，显然这个算法不起作用。有没有更高效的算法。
对任意和取 mod 10 并比较它们与取随机数没有太大区别。你无法避免这里的数字规模。 modulo might 有助于确定两个数字是否相等（如果总和 modulo 任何数字不相等，您可以假设它们不相等） .另请注意，Ruby 仍会计算您的情况下的大数 - 但如果您在 modulo 算术中更详细地进行求幂，则可以使用一些技巧来避免这种情况。
对于一个近似的方法，它应该几乎一直有效，那么你可以使用 Math.log( x ** y ) == y * Math.log( x ).
像这样：
(Math.log(x[0]) * x[1]) > (Math.log(y[0]) * y[1])
当我说 almost 时，我的意思是您将自己暴露在此处的浮点误差中。由于 Math.log 中的四舍五入，两个非常大但非常相似的幂运算可能会以错误的顺序出现。我不确定这对于您显示的尺寸的数字是否是一个实际问题。
更新：
2 ** 9 == 8 ** 3
# => true
但是
(Math.log(2) * 9) > (Math.log(8) * 3)
# => true
因此，完全相等的值的舍入错误是一个更严重的问题，并且可能发生在非常低的输入数字上。如果两个输入可能相等并且知道值是否完全不同很重要，则当 log/log 比较的结果非常接近时，您需要回退到不同的机制，例如两个对数和的比率在 1.0 的 1e-6 范围内。