Как реализовать квадратный корень и возведение в степень на числах произвольной длины? - PullRequest
Новая
       13

Как реализовать квадратный корень и возведение в степень на числах произвольной длины?

5 голосов
/ 26 декабря 2010

Я работаю над новым типом данных для чисел произвольной длины (только неотрицательные целые числа), и я застрял в реализации функций квадратного корня и возведения в степень (только для естественных показателей степени).Пожалуйста, помогите.

Я храню число произвольной длины в виде строки, поэтому все операции выполняются как char * char .

Пожалуйста не Включите советы по использованию другой (существующей) библиотеки или другого способа хранения числа, кроме строки.Это должно быть упражнение по программированию, а не реальное приложение, поэтому оптимизация и производительность не так необходимы.

Если вы включите код в свой ответ, я бы предпочел, чтобы он был либо в псевдокоде, либов C ++.Важным является алгоритм, а не сама реализация.

Спасибо за помощь.

Ответы [ 2 ]

10 голосов
/ 26 декабря 2010

Квадратный корень: Вавилонский метод . * Т.е. 1003 * 

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
3 голосов
/ 26 декабря 2010

Экспонирование тривиально реализуется с умножением - самая базовая реализация - это просто цикл, 

result = 1;    
for (int i = 0; i < power; ++i) result *= base;

Вы можете (и должны) реализовать лучшую версию, используя квадрат с делением и завоеванием - то есть a ^ 5 = a ^ 4 * a = (a ^ 2) ^ 2 * a.

Квадратный корень может быть найден с использованием метода Ньютона - вы должны получить первоначальное предположение (хороший вариант - извлечь квадратный корень из старшей цифры и умножить его на базу цифр, поднятую до половины исходного числа длина), а затем уточнить его, используя деление: если a является приближением к sqrt (x), то лучшим приближением является (a + x / a) / 2. Вам следует остановиться, когда следующее приближение равно предыдущему или к х / а.

...