使用加，减和减半计算三角根

Question

特定游戏中的规则是角色的力量与角色体验的triangular root成比例。例如，15-20经验给5力量，21-27经验给6力量，28-35经验给力7等等。有些玩家已经获得了数千亿的经验。

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

我已经考虑计算三角形根T(p)到bisection search对于从上面和下面限定经验数的连续三角形数。我的计划是使用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，其中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) 

Answer 2

如在链接的页面上观察到math.stackexchange.com存在用于此问题的解决方案的直接式和为x = n*(n+1)/2那么反向是：

n = (sqrt(1+8*x) - 1)/2 

现在有正方形根和其他的东西，但我会建议使用这种直接用公式类似如下的实现：

tmp = x + x; '2*x 
tmp += tmp;  '4*x 
tmp += tmp + 1; '8*x + 1 
n = 0; 
n2 = 0; 
while(n2 <= tmp){ 
    n2 += n + n + 1; 'remember that (n+1)^2 - n^2 = 2*n + 1 
    n++; 
} 
'here after the loops n = floor(sqrt(8*x+1)) + 1 
n -= 2;   'floor(sqrt(8*x+1)) - 1 
n /= 2;   '(floor(sqrt(8*x+1)) - 1)/2 

当然，这可以为每更好的改善如果像neede那样考虑整数值floor(sqrt(8*x+1)) + 1甚至是n，则可以用2的步长递增（相应地重写n2计算：n2 += n + n + n + n + 4，本身可以写得比这更好）。