Мне нужно извлечь квадратный корень из числа без использования модуля math.

Существует ли алгоритм который использует только умножение, сложение и вычитание? Т.к. хотелось бы использовать его с вот этим модулем: http://www.pythoncraft.com/Decimal.py А там другие операции не реализованы ;)

Нужно это для вот такого устройства: http://www.telit.com/en/products/python.php
Там python 1.5.2 и нету почти ничего из стандартной библиотеки.

первое что приходит на ум – разложить в ряд тэйлора до требуемой точности. если я не ошибаюсь, так практически везде и сделано.

в принципе, еще можно дихотомию пускать. сходимость логарифмическая. но все-таки это уже из разряда извращений.

тута интересно :)
И тут
И тута почитайте
Ага, а вот тут подробно написано, правда на С.

Угу. Тот код, который на gamedev, AFAIR, id Software использовал :)

В питоне 2.5 в модуле decimal - есть вычисление корня.
На питоне - 100 строк, поэтому даю ссылку на модуль.
Функция называется sqrt =)
http://svn.python.org/view/python/trunk/Lib/decimal.py?rev=58550&view=markup
Я думаю ее надо немного подправить - чтоб совместить с 1.5.2.

хотя… я бы поступил по другому.
перевел бы decimal во float, и сделал
pow(x, 0.5)
это побыстрее будет чем столбиком или по ньютону считать ;)

p.s. pow - встроенная в 1.5.2 питон функция

shiza
перевел бы decimal во float, и сделал

К сожалению, там нету float…

Я работал на телитских модули год назад. По моему встроений интерпретатор весьма бесполезней, недомыслие какое-то :) По моему лучше тебе будет сделать все математики,низкоуровневых и time-critical операций на внешний контролер, ползую только файловая система… но сделать надеждной протокол для связь по UART-a тоже невозможно, потому что телитский питон будет считать простой XOR каждого 64-байтово пакета для какие там 0.5-0.6 секунд:) для CRC :)

Если нет выбора и если обхват аргумента позволяет, лучше всего будет запихать все в словарь :)

_sqrt={1:1,2:1,4:2…..}