Алгоритм актуален для встроенных систем, т.е. там, где код обычно пишется на Си, в лучшем случае — на Си++. Но, уж, больно просто написать и погонять на Питоне. На Си это дело напишется просто один в один.
Если обозвать файл, как и функцию, 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.