功能定义在整数范围内的快速求和计算 - (0,2^52)

Question

我在看一个特定的加密货币赌场游戏的代码（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

不幸的是，循环运行的时间太长了-有什么办法让我能更快地完成这个任务吗？你知道吗

Answer 1

我已经能够通过利用numpy矢量化来加速您的代码：

import numpy as np
import time

two52 = 2**52
crash = lambda x: np.floor( ( 100 * two52 - x ) / ( two52 - x ) ) / 100

starttime = time.time()
icur = 0
ispan = 100000
crashes_sum = 0
while icur < two52-ispan:
    i = np.arange(icur, icur+ispan, 1)
    crashes_sum += np.sum(crash(i))
    icur += ispan
crashes_sum += np.sum(crash(np.arange(icur, two52, 1)))
expected_crash = crashes_sum / two52
print(time.time() - starttime)

诀窍是计算移动窗口上的和，以利用numpy的矢量化（用C编写）。我尝试了2**30，在我的笔记本电脑上花了9秒（而且太长了，你的代码无法进行基准测试）。你知道吗

Python可能不是最适合您的语言，您可以尝试C或Fortran（并利用线程）。你知道吗

Answer 2

使用map函数可能有助于提高速度，因为它使计算并行

import math

two52 = 2**52

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

crashes_sum = sum(map(crash,range(two52)))

expected_crash = crashes_sum/two52

Answer 3

好吧，如果你不能直截了当的话，是时候变聪明了，对吧？ 所以我们想得到一个范围，在这个范围内可以快速计算出整个和。我会把一些伪代码，甚至不编译，可能有错误等，用它来说明。你知道吗

首先，让我们把这个词改写为

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

第一个想法-得到的范围，地板是没有变化的，因为事实上，该术语 n=<；99*x/（2⁵²-x）<；n+1。很明显，对于这个范围，我们可以把它加到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或更多。你知道吗

好的，第二个想法-同样是范围，这里的和是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

也许会想些别的，但这些把戏值得一试