python - 快速计算在整数范围内定义的函数的总和 - (0,2^52)

Question

我正在查看特定加密货币赌场游戏的代码(EthCrash - 如果您感兴趣)。游戏使用函数(我称之为 crash(x))生成崩溃点，其中 x 是从整数空间 (0,2^52) 中随机抽取的整数。

我想计算崩溃点的预期值。下面的代码应该解释一切，但该函数的清晰图片在这里:/image/GdZIh.png ，我要计算的是:/image/HdE91.png (抱歉 - 还无法粘贴图片)。

我编写了以下代码:

import math

two52 = 2**52

def crash(x):    
    crash_point = math.floor((100*two52-x)/(two52-x))
    return(crash_point/100)

crashes_sum = 0

for i in range(two52+1):
    crashes_sum += crash(i)

expected_crash = crashes_sum/two52

不幸的是，循环运行时间太长 - 有什么想法可以更快地做到这一点吗？

Answer 1

好吧，如果你不能直接做到这一点，那么是时候变得聪明了，对吧？ 因此，想要获得可以快速计算总和的范围。我将放置一些伪代码，这些伪代码甚至无法编译，可能存在错误等。将其用作说明。

首先，让我们将总和中的项重写为

地板( 100 + 99*x/(2⁵² - x) )

第一个想法 - 获取由于该术语而地板没有变化的范围 n =< 99*x/(2⁵² - x) < n+1。显然，对于整个范围，我们可以添加总和 range_length*(100 + n)，无需逐项进行

sum  = 0
r_lo = 0
for k in range(0, 2*52): # LOOP OVER RANGES
    r_hi = floor(2**52/(1 + 99/n))
    sum += (100 + n -1)*(r_hi - r_lo)
    if r_hi-r_lo == 1:
        break
    r_lo = r_hi + 1

显然，范围大小会缩小到等于1，那么这个方法就没用了，我们突破吧。显然，到那时每一项都会与前一项相差 1 或更多。

好吧，第二个想法 - 再次范围，其中总和是 arithmetic series 。首先我们必须找到增量等于 1 的范围。然后增量等于 2 的范围，依此类推。看起来你必须为此找到二次方程的根，但代码大致相同

r_lo = pos_for_increment(1)
t_lo = ... # term at r_lo
for n in range(2, 2*52): # LOOP OVER RANGES
    r_hi = pos_for_increment(n) - 1
    t_hi = ... # term at r_lo
    sum += (t_lo + t_hi)*(r_hi - r_lo) / 2 # arith.series sum
    if r_hi > 2**52:
        break
    r_lo = r_hi + 1
    t_lo = t_hi + n

可能会考虑其他事情，但这些技巧值得尝试