Корень квадратный быстрый

Алгоритм актуален для встроенных систем, т.е. там, где код обычно пишется на Си, в лучшем случае — на Си++. Но, уж, больно просто написать и погонять на Питоне. На Си это дело напишется просто один в один.

Если обозвать файл, как и функцию, int_sqrt.py, то запустить можно из командной строки:

python int_sqrt.py 150

либо в интерпретаторе, например, так:


>>> from int_sqrt import int_sqrt as sqrt
>>> sqrt(150)
>>> 12

Как оно работает, мне неведомо. Нашёл уже давно где-то на просторах Интернета. Ссылку, к сожалению, не сохранил. Алгоритм хорош тем, что самая тяжёлая операция в цикле, насколько я могу судить, — это вычитание.

import sys

def int_sqrt(x):
    m = 0x40000000
    y = 0

    while m:
        b = y | m
        y = y >> 1
        if x >= b:
            x = x - b
            y = y | m
        m = m >> 2
    return y

if len(sys.argv) >= 2:
    x = int(sys.argv[1])
    print(int_sqrt(x))

Разукрашено на tohtml.com.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.