Быстрый расчет суммы для функции, определенной в диапазоне целых чисел - (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

хорошо, если вы не можете сделать это прямо, время стать умным, верно? Так что идея получить диапазоны, где вся сумма может быть вычислена быстро. Я добавлю псевдокод, который даже не компилируется, может содержать ошибки и т. Д. Используйте его в качестве иллюстрации.

Во-первых, давайте переписать термин в сумме как

этаж (100 + 99 * x / (2 ⁵² - x))

Первая идея - получить диапазоны, где пол не меняется из-за того, что срок n = <99 * x / (2 <sup>52 - x)

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 или более.

Хорошо, вторая идея - снова диапазоны, где сумма равна арифметический ряд . Сначала мы должны найти диапазон, где приращение равно 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

может подумать о чем-то другом, но эти уловки стоит попробовать

Answer 2

Поскольку вычисление не может быть сведено к минимуму математически, единственной возможностью является его вычисление шаг за шагом.

Это занимает много времени (как указано в других ответах). Ваша лучшая ставка на быстрый расчет - использовать язык более низкого уровня, чем Python. Поскольку python - интерпретируемый язык, он довольно медленно вычисляет подобные вещи.

Кроме того, вы можете использовать многопоточность (если она доступна на выбранном языке), чтобы сделать ее еще быстрее.

Облачные вычисления - также вариант, который может подойти для этого, поскольку вы будете рассчитывать число только один раз. Amazon и Google (и многие другие) предоставляют такие услуги за сравнительно небольшую плату.

Но прежде чем выполнять какие-либо вычисления, вам нужно настроить формулу, как и в том виде, в котором она сейчас стоит, вы получите ZeroDivisionError на самой последней итерации цикла.

Answer 3

Мне удалось ускорить ваш код, воспользовавшись преимуществом векторизации:

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 4

Вам придется использовать мощный графический процессор, если вы не хотите получить результат в течение нескольких часов.

Возможная реализация ЦП

import numpy as np
import numba as nb
import time

two52 = 2**52
loop_to=2**30

@nb.njit(fastmath=True,parallel=True)
def sum_over_crash(two52,loop_to): #loop_to is only for testing performance
  crashes_sum = nb.float64(0)
  for i in nb.prange(loop_to):#nb.prange(two52+1):
    crashes_sum += np.floor((100*two52-i)/(two52-i))/100

  return crashes_sum/two52

sum_over_crash(two52,2)#don't measure static compilation overhead
t1=time.time()
sum_over_crash(two52,2**30)
print(time.time()-t1)

Это требует 0,57 с для моего четырехъядерного процессора i7. например. 28 дней на весь расчет.

Answer 5

Использование функции 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