Просто для затравки.
Есть много способов - от Герона до рядов и до битных вычислений.
Еще один способ ( не претендуя на оригинальность - геометрический, итерационный).
Основан на приближении C^2 = A^2 + B^2.
Число итераций практически Ln(N).
Не очень быстрый, это факт (3..11 итераций).
Известен давно, но доработан до минимизации средней ошибки.
Код (Pascal):
http://shot.qip.ru/00gZ9L-5OPovQGI0/
График ошибок (X = 10..100 тыс.), [%]:
http://shot.qip.ru/00gZ9L-2OPovQGI2/
Число итераций (X = 10..100 тыс.):
http://shot.qip.ru/00gZ9L-4OPovQGI4/
Полная версия этой страницы: Квадратный корень из целочисленного значения.
Форум разработчиков электроники ELECTRONIX.ru > Цифровая обработка сигналов - ЦОС (DSP) > Алгоритмы ЦОС (DSP)
Цитата(TSerg @ Sep 23 2016, 23:41) 
Просто для затравки.
Есть много способов - от Герона до рядов и до битных вычислений.
Еще один способ ( не претендуя на оригинальность - геометрический, итерационный).
Основан на приближении C^2 = A^2 + B^2.
Число итераций практически Ln(N).
Не очень быстрый, это факт (3..11 итераций).
Известен давно, но доработан до минимизации средней ошибки.
Есть много способов - от Герона до рядов и до битных вычислений.
Еще один способ ( не претендуя на оригинальность - геометрический, итерационный).
Основан на приближении C^2 = A^2 + B^2.
Число итераций практически Ln(N).
Не очень быстрый, это факт (3..11 итераций).
Известен давно, но доработан до минимизации средней ошибки.
Там еще и деление на каждой итерации... Печаль. Лучше выбрать нечто более вычислительно простое из горы методов, предложенных здесь:
https://en.wikipedia.org/wiki/Methods_of_co...ng_square_roots
Я сам полиномиальную аппроксимацию для нормализованных чисел использую. Получается:
Нормализация -> вычисление полинома степени 3 по схеме Горнера ->денормализация (половина сдвигов нормализации + умножение, если при нормализации количество сдвигов было нечетным)
Я делал в свое время для DSP от TI с однотактным умножением методом последовательного приближения с дополнительными ухищрениями. Получилось лучше, чем в стандартной библиотеке. Точное количество тактов сейчас не помню, и текста нет под рукой - я в отпуске.
Цитата(TSerg @ Sep 23 2016, 23:41)
Просто для затравки.
Есть много способов - от Герона до рядов и до битных вычислений.
Еще один способ ( не претендуя на оригинальность - геометрический, итерационный).
Основан на приближении C^2 = A^2 + B^2.
Число итераций практически Ln(N).
Не очень быстрый, это факт (3..11 итераций).
Известен давно, но доработан до минимизации средней ошибки.
Код (Pascal):
http://shot.qip.ru/00gZ9L-5OPovQGI0/
График ошибок (X = 10..100 тыс.), [%]:
http://shot.qip.ru/00gZ9L-2OPovQGI2/
Число итераций (X = 10..100 тыс.):
http://shot.qip.ru/00gZ9L-4OPovQGI4/
Есть много способов - от Герона до рядов и до битных вычислений.
Еще один способ ( не претендуя на оригинальность - геометрический, итерационный).
Основан на приближении C^2 = A^2 + B^2.
Число итераций практически Ln(N).
Не очень быстрый, это факт (3..11 итераций).
Известен давно, но доработан до минимизации средней ошибки.
Код (Pascal):
http://shot.qip.ru/00gZ9L-5OPovQGI0/
График ошибок (X = 10..100 тыс.), [%]:
http://shot.qip.ru/00gZ9L-2OPovQGI2/
Число итераций (X = 10..100 тыс.):
http://shot.qip.ru/00gZ9L-4OPovQGI4/
в свое время я его реализовал на FPGA
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.