WikiSort.ru - Не сортированное

Использование только целочисленного деления

Для вычисления ${\displaystyle \lfloor {\sqrt {n}}\rfloor }$ для очень больших целых чисел n можно использовать частное деления с остатком при обоих операциях деления. Преимуществом является использование только целых чисел для каждого промежуточного значения, что освобождает от использования представления чисел в виде чисел с плавающей запятой. Это эквивалентно использованию итеративной формулы

${\displaystyle {x}_{k+1}=\left\lfloor {\frac {1}{2}}\left(x_{k}+\left\lfloor {\frac {n}{x_{k}}}\right\rfloor \right)\right\rfloor ,\quad k\geq 0,\quad x_{0}>0,\quad x_{0}\in \mathbb {Z} .}$

Основываясь на факте, что

${\displaystyle \left\lfloor {\frac {1}{2}}\left(x_{k}+\left\lfloor {\frac {n}{x_{k}}}\right\rfloor \right)\right\rfloor =\left\lfloor {\frac {1}{2}}\left(x_{k}+{\frac {n}{x_{k}}}\right)\right\rfloor ,}$

можно показать, что последовательность достигает ${\displaystyle \lfloor {\sqrt {n}}\rfloor }$ за конечное число итераций ^[4].

Однако ${\displaystyle \lfloor {\sqrt {n}}\rfloor }$ не обязательно будет неподвижной точкой итеративной формулы, приведённой выше. Можно показать, что ${\displaystyle \lfloor {\sqrt {n}}\rfloor }$ будет неподвижной точкой тогда и только тогда, когда ${\displaystyle n+1}$ не является полным квадратом. Если ${\displaystyle n+1}$ является полным квадратом, последовательность не сходится, а переходит в цикл длины два, поочерёдно меняя ${\displaystyle \lfloor {\sqrt {n}}\rfloor }$ и ${\displaystyle \lfloor {\sqrt {n}}\rfloor +1}$ . Для прекращения работы достаточно проверить, что либо последовательность сходится (повторение предыдущего значения), либо что следующее значение ровно на единицу больше текущего, в последнем случае новое значение отбрасывается.

Используя битовые операции

Если * означает умножение, << означает сдвиг влево, а >> — логический сдвиг вправо, рекурсивный алгоритм поиска целочисленного квадратного корня из любого натурального числа следующий:

function integerSqrt(n):
    if n < 0:
        error "integerSqrt работает только с неотрицательным входом"
    else if n < 2:
        return n
    else:
        smallCandidate = integerSqrt(n >> 2) << 1
        largeCandidate = smallCandidate + 1
        if largeCandidate*largeCandidate > n:
            return smallCandidate
        else:
            return largeCandidate

Или итерации вместо рекурсии:

function integerSqrt(n):
    if n < 0:
        error "integerSqrt работает только с неотрицательным входом"     
    # Находим наибольший сдвиг.
    shift = 2
    nShifted = n >> shift
    while nShifted ≠ 0 and nShifted ≠ n:
        shift = shift + 2
        nShifted = n >> shift
    shift = shift - 2
    
    # Находим цифры результата.
    result = 0
    while shift ≥ 0:
        result = result << 1
        candidateResult = result + 1
        if candidateResult*candidateResult ≤ n >> shift:
            result = candidateResult
        shift = shift - 2
   
    return result