使用加,减和减半计算三角形根

Question

特定游戏中的规则是角色的力量与角色体验的三角根成正比.例如,15-20经验提供5个权力,21-27经验提供6个权力,28-35经验提供7个权力等.已知一些玩家已经获得了数千亿的经验.

我试图在只有三个算术指令的8位机器上实现这个游戏:加,减和除以2.例如,要将数乘以4,程序会将它自己添加两次.一般乘法要慢得多; 我已经编写了一个软件子程序来使用四分之一平方表来完成它.

我曾考虑T(p)通过二分法搜索三角形根来计算从上方和下方划定经验数的连续三角形数字.我的计划是使用重复身份,T(2*p)直到它超过经验,然后使用它作为二分搜索的上限.但是我很难找到T((x+y)/2)不使用任何一个x*y或两个的二分的身份(x+y)^2.

是否有一种有效的算法来计算数字的三角形根,只需加,减,减半？或者我最终必须执行O(log n)乘法,一个用于计算二分搜索中的每个中点？或者考虑实施长除法以使用牛顿方法会更好吗？

定义T(x):

T(x) = (n * (n + 1))/2

我得出的身份:

T(2*x) = 4*T(x) - x
# e.g. T(5) = 15, T(10) = 4*15 - 5 = 55

T(x/2) = (T(x) + x/2)/4
# e.g. T(10) = 55, T(5) = (55 + 5)/4 = 15

T(x + y) = T(x) + T(y) + x*y
# e.g. T(3) = 6, T(7) = 28, T(10) = 6 + 28 + 21 = 55

T((x + y)/2) = (T(x) + T(y) + x*y + (x + y)/2)/4
# e.g. T(3) = 6, T(7) = 28, T(5) = (6 + 28 + 21 + 10/2)/4 = 15

Answer 1

做二分搜索,但要确保它y - x始终是二的幂.(这不会增加渐近运行时间.)然后T((x + y) / 2) = T(x) + T(h) + x * h,在2 h的幂的位置,x * h也可以用移位计算.

这是一个Python概念证明(匆忙编写,或多或少未经优化但避免昂贵的操作).

def tri(n):
    return ((n * (n + 1)) >> 1)

def triroot(t):
    y = 1
    ty = 1

    # Find a starting point for bisection search by doubling y using
    # the identity T(2*y) = 4*T(y) - y. Stop when T(y) exceeds t.
    # At the end, x = 2*y, tx = T(x), and ty = T(y).
    while (ty <= t):
        assert (ty == tri(y))
        tx = ty
        ty += ty
        ty += ty
        ty -= y
        x = y
        y += y

    # Now do bisection search on the interval [x .. x + h),
    # using these identities:
    # T(x + h) = T(x) + T(h) + x*h
    # T(h/2) = (T(h) + h/2)/4
    th = tx
    h = x
    x_times_h = ((tx + tx) - x)
    while True:
        assert (tx == tri(x))
        assert (x_times_h == (x * h))

        # Divide h by 2
        h >>= 1
        x_times_h >>= 1
        if (not h):
            break
        th += h
        th >>= 1
        th >>= 1

        # Calculate the midpoint of the search interval
        tz = ((tx + th) + x_times_h)
        z = (x + h)
        assert (tz == tri(z))

        # If the midpoint is below the target, move the lower bound
        # of the search interval up to the midpoint
        if (t >= tz):
            tx = tz
            x = z
            x_times_h += ((th + th) - h)
    return x
for q in range(1, 100):
    p = triroot(q)
    assert (tri(p) <= q < tri((p + 1)))
    print(q, p)