如何在任意长度数上实现平方根和取幂？

Question

我正在研究任意长度数字的新数据类型(只有非负整数),并且我坚持实现平方根和取幂函数(仅适用于自然指数).请帮忙.

我将任意长度数字存储为字符串,因此所有操作都由char进行char.

请不要包含使用不同(现有)库或其他方式来存储数字而不是字符串的建议.这是一个编程练习,而不是一个真实的应用程序,所以优化和性能不是那么必要.

如果你在答案中包含代码,我希望它可以是伪代码或C++.重要的是算法,而不是实现本身.

谢谢您的帮助.

Answer 1

平方根:巴比伦方法.即

function sqrt(N):
    oldguess = -1
    guess = 1
    while abs(guess-oldguess) > 1:
        oldguess = guess
        guess = (guess + N/guess) / 2
    return guess

指数:通过平方.

function exp(base, pow):
    result = 1
    bits = toBinary(powr)
    for bit in bits:
        result = result * result
        if (bit):
            result = result * base
    return result

其中toBinary返回1和0的列表/数组,MSB优先,例如由此Python函数实现:

def toBinary(x):
    return map(lambda b: 1 if b == '1' else 0, bin(x)[2:])

请注意,如果您的实现是使用二进制数完成的,则可以使用按位运算来实现,而无需任何额外的内存.如果使用十进制,那么您将需要额外的来存储二进制编码.

但是,算法的十进制版本看起来像这样:

function exp(base, pow):
    lookup = [1, base, base*base, base*base*base, ...] #...up to base^9
     #The above line can be optimised using exp-by-squaring if desired

    result = 1
    digits = toDecimal(powr)
    for digit in digits:
        result = result * result * lookup[digit]
    return result