时间戳

首页 > 解决方案 > 快速计算在整数范围内定义的函数的总和 - (0,2^52)

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

问题描述

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

我想计算崩溃点的预期值。下面的代码应该解释一切，但函数的清晰图片在这里： https ://i.imgur.com/8dPBALa.png ，我要计算的是在这里：https://i.imgur。 com/nllykDQ.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

不幸的是，循环运行时间太长 - 关于如何更快地做到这一点的任何想法？

标签： pythonmathstatistics

解决方案

好吧，如果你不能直接做到这一点，是时候变聪明了，对吧？所以想法得到可以快速计算整个总和的范围。我会放一些甚至无法编译的伪代码，可能有错误等。用它作为说明。

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

地板（100 + 99*x/（2 52 - x））

第一个想法 - 由于术语 n =< 99*x/(2 52 - x) < n+1的事实，得到 floor 不变的范围。显然，对于整个范围，我们可以将 range_length*(100 + n) 添加到 sum 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 或更多。

好的，第二个想法 - 再次是范围，其中 sum 是算术级数。首先，我们必须找到增量等于 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

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

推荐阅读