Calculate the triangular root by adding, subtracting and halving

Question

The rule in a particular game is that the strength of the symbol is proportional to the triangular root of the character’s experience. For example, 15-20 experience gives 5 units, 21-27 experience gives 6 units, 28-35 experience gives 7 units. Etc. Some players are known to have gained hundreds of billions of experience.

I am trying to implement this game on an 8-bit machine, which has only three arithmetic instructions: add, subtract and divide by 2. For example, to multiply a number by 4, the program will add it to itself twice, General multiplication is much slower; I wrote a program routine to do this using a square table.

I looked at calculating the triangular root T(p)through bisection search for consecutive triangular numbers, limiting the number of experiences above and below. My plan was to use the repeat identifier for T(2*p)until it exceeded the experience, and then use it as an upper bound to search in half. But it’s hard for me to find the identifier for T((x+y)/2)half-division, which does not use either x*y, or (x+y)^2.

Is there an efficient algorithm for calculating the triangular root of a number with just adding, subtracting and halving it? Or should I end up doing O (log n) multiplication to compute each midpoint in a normal search? Or would it be better to consider the use of long division to use the Newton method?

Definition T(x):

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

The identities I received are:

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

Do the search in half, but make sure that y - xthere are always two. (This does not increase the asymptotic time of work.) Then T((x + y) / 2) = T(x) + T(h) + x * h, where his the degree of two, therefore it is x * hcomputable with a shift.

Here's a proof of the Python concept (hastily written, more or less non-optimized, but avoiding costly operations).

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

As you can see on the linked page on math.stackexchange.com, there is a direct formula to solve this problem, and x = n*(n+1)/2then the opposite:

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

, , , , floor(sqrt(8*x+1)) + 1 , n 2 ( n2 : n2 += n + n + n + n + 4, ).