特定游戏的规则是角色的力量与角色的力量成正比。三角根 https://math.stackexchange.com/q/698961/93170角色的经历。例如,15-20经验获得5力量,21-27经验获得6力量,28-35经验获得7力量等等。据了解,有些玩家的经验达到了数千亿。
我试图在只有三个算术指令的 8 位机器上实现这个游戏:加法、减法和除以 2。例如,要将一个数字乘以 4,程序会将其与自身相加两次。一般乘法要慢得多;我已经编写了一个软件子例程来使用四分之一方桌来完成此操作。
我曾考虑过计算三角根T(p)
通过二分搜索 https://en.wikipedia.org/wiki/Bisection_method用于从上方和下方限定经验数的连续三角形数。我的计划是使用重复身份T(2*p)
直到它超过经验,然后将其用作二分搜索的上限。但我很难找到一个身份T((x+y)/2)
在不使用任何一个的二分法中x*y
or (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
进行二分搜索,但确保y - x
总是 2 的幂。 (这不会增加渐近运行时间。)然后T((x + y) / 2) = T(x) + T(h) + x * h
, where 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)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)