4

The rule in a particular game is that a character's power is proportional to the triangular root of the character's experience. For example, 15-20 experience gives 5 power, 21-27 experience gives 6 power, 28-35 experience gives 7 power, etc. Some players are known to have achieved experience in the hundreds of billions.

I am trying to implement this game on an 8-bit machine that has only three arithmetic instructions: add, subtract, and divide by 2. For example, to multiply a number by 4, a program would add it to itself twice. General multiplication is much slower; I've written a software subroutine to do it using a quarter-square table.

I had considered calculating the triangular root T(p) through bisection search for the successive triangular numbers bounding an experience number from above and below. My plan was to use a recurrence identity for T(2*p) until it exceeds experience, then use that as the upper bound for a bisection search. But I'm having trouble finding an identity for T((x+y)/2) in the bisection that doesn't use either x*y or (x+y)^2.

Is there an efficient algorithm to calculate the triangular root of a number with just add, subtract, and halve? Or will I end up having to perform O(log n) multiplications, one to calculate each midpoint in the bisection search? Or would it be better to consider implementing long division to use Newton's method?

Definition of T(x):

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

Identities that I derived:

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
Community
  • 1
  • 1
Damian Yerrick
  • 4,602
  • 2
  • 26
  • 64

2 Answers2

5

Do bisection search, but make sure that y - x is always a power of two. (This does not increase the asymptotic running time.) Then T((x + y) / 2) = T(x) + T(h) + x * h, where h is a power of two, so x * h is computable with a shift.

Here's a Python proof of concept (hastily written, more or less unoptimized but avoids expensive 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)
Toby Speight
  • 27,591
  • 48
  • 66
  • 103
David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
1

As observed in the linked page on math.stackexchange.com there is a direct formula for the solution of this problem and being x = n*(n+1)/2 then the reverse is:

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

Now there is the square root and other things but I would suggest to use this direct formula with an implementation like the following:

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

Of course this can be improved for better performances if neede like considering that integer values of floor(sqrt(8*x+1)) + 1 are even so n can be incremented with steps of 2 (rewriting the n2 calculation accordingly: n2 += n + n + n + n + 4 that can itself be written better than this).

Diego Mazzaro
  • 2,734
  • 1
  • 20
  • 21
  • This algorithm appears to be O(n), something I was hoping to avoid. How many iterations will it run with x = 10 billion? – Damian Yerrick Mar 28 '14 at 01:14
  • O(n^0.5) becouse there is only one loop and it is used to calculate the square root. Indeed this approach shows that the problem you have posed (calculate the Thriangular root) is equivalent to the calculation of the square root (all other step are only done once so are O(1). This tells that now to solve your problem you can take any good algorithm for the square root and put it in place of the current while loop. So if you want to use bisection you can now apply it to square root instead that triangular root and maybe you can found many solutions for that in literature and around. – Diego Mazzaro Mar 28 '14 at 21:21