计算使用加，减，并减半三角根 [英] Calculating a triangular root using add, subtract, and halve
问题描述
在一个特定的游戏规则是，一个人物的功率正比于的人物的经验三角根 。例如，15-20经验使5功率，21-27经验使6个功率，28-35经验使7功率等一些球员已知有在数千亿美元取得的经验。
我想实现这个游戏的8位机只有三个运算指令上：由2加，减，再除以例如，4乘以一个数字，一个计划将其添加到自己的两倍。一般乘法慢得多;我写了一个软件子程序使用四分之一方桌做到这一点。
我曾考虑计算三角形根 T（P）通过的二分查找，在连续的三角形数包围的体验人数从上方和下方。我的计划是使用复发标识T（2 * P），直到超过经验，然后用其作为上限二分法搜索。但我无法找到一个标识为 T（（X + Y）/ 2）在不使用任何二分X *是或（X + Y）^ 2 。
是否有一个有效的算法来计算一个数只有加，减，并减半三角形的根源在哪里？或者将我最终不得不执行O（log n）的乘法，一个计算的二分查找每个中点？或者会是更好的考虑执行长除法用牛顿的方法是什么？
定义T（x）：
T（X）=（N *（N + 1））/ 2
身份我派生的：
T（2 * X）= 4 * T（X） - X
＃ 例如。 T（5）= 15，T（10）= 4 * 15 - 5 = 55
T（X / 2）=（T（x）的+ X / 2）/ 4
＃ 例如。 T（10）= 55，T（5）=（55 + 5）/ 4 = 15
T（X + Y）= T（X）+ T（Y）+ X * Y
＃ 例如。 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
＃ 例如。 T（3）= 6，T（7）= 28，T（5）=（6 + 28 + 21 + 10/2号）/ 4 = 15
做二分查找，但要确保Ÿ - X 始终是二的幂。 （这不会增加渐近运行时间）。然后 T（（X + Y）/ 2）= T（X）+ T（H）+ X * H ，其中， ^ h 是二的幂，所以
下面是一个Python概念验证（匆匆写的，或多或少的未经优化的，但避免了昂贵的操作）。
高清三（正）：
返回（（N *（N + 1））＆GT;→1）
高清triroot（T）：
Y = 1
TY = 1
＃用加倍Ÿ找到一个起点二分法搜索
＃身份T（2 * Y）= 4 * T（γ） - 年。停止当T（Y）超过万吨。
＃在末端中，x = 2 * Y，TX = T（x）的，和ty = T（Y）。
而（TY＆LT; = T）：
断言（TY ==三（Y））
TX = TY
TY + = TY
TY + = TY
TY - = Y
X = Y
Y + = Y
＃现在做的区间二分法搜索[X .. X + H），
＃使用这些身份：
＃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）
而真正的：
断言（TX ==三（X））
断言（x_times_h ==（X * H））
＃除以2小时
h取代;＆GT; = 1
x_times_h＆GT;＆GT; = 1
如果（不高）：
打破
日+ = H
第i;＆GT; = 1
第i;＆GT; = 1
＃计算搜索间隔的中点
TZ =（（TX +个）+ x_times_h）
Z =（X + H）
断言（TZ ==三（Z））
＃如果中点是低于目标，移动下界
＃搜索区间高达中点
如果（T＆GT; = TZ）：
TX = TZ
X =ž
x_times_h + =（（日+日） - 高）
返回X
对于q在范围（1，100）：
p值= triroot（q）的
断言（三（对）其中; = Q＆其中;三（（P + 1）））
打印（Q，P）
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
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)
这篇关于计算使用加，减，并减半三角根的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
