Найти квадратный корень как число с плавающей запятой из int и остатка?

Сейчас я смотрю на конкретный алгоритм вычисления квадратного корня, который возвращает целую часть квадратного корня и остаток.

Так например: mysqrt(140) = 11*11 + 19 = integer 11, remainder 19

Вопрос в том, могу ли я вычислить квадратный корень как число с плавающей запятой, например квадратный корень из 140 составляет ~ 11,8321 ....?

редактировать из комментариев

Я смотрю на реализацию VHDL квадратного корня с фиксированной точкой, которая использует только двоичные операции, такие как сдвиг влево / вправо, сложение и вычитание.

... алгоритма было бы достаточно.

ИЗМЕНИТЬ 2. Я на самом деле читаю этот алгоритм здесь: http://pioneer.netserv.chula.ac.th/~achatcha/Publications/0012.pdf

Кажется, что лучшую точность можно получить, сдвинув подкоренное выражение влево на 2n. Я не совсем уверен, почему это работает? Может ли кто-нибудь объяснить мне


algorithm math square-root
person mark mcgehee    schedule 17.01.2012    source источник
comment
Я исправил то, что выглядело как опечатка (remainder 9 вместо 19).   -  person NPE    schedule 17.01.2012
comment
По сути, это сводится к написанию вашей собственной реализации квадратного корня.   -  person outis    schedule 17.01.2012
comment
Язык программирования или просто алгоритм?   -  person ChrisBD    schedule 17.01.2012
comment
@ChrisBD, алгоритма будет достаточно.   -  person mark mcgehee    schedule 17.01.2012
comment
Конечно, можно, но какими операциями вы себя ограничиваете? Предположительно вы не хотите использовать полный оператор sqrt. Существуют алгоритмы, которые используют оценку и остатки для вычисления квадратных корней. homeschoolmath.net/teaching/square-root-algorithm.php - это один такой.   -  person Chris    schedule 17.01.2012
comment
Спасибо @Chris, я посмотрю. Алгоритм, который я ищу прямо сейчас (чтобы найти int и остаток), использует только бинарные операции, такие как сдвиг влево / вправо, сложение и вычитание.   -  person mark mcgehee    schedule 17.01.2012
comment
Спасибо @ChrisBD за редактирование вопроса.   -  person mark mcgehee    schedule 17.01.2012

Ответы (3)


arrow_upward
4
arrow_downward 

(11+x)^2 = 140
11^2 + 2*11*x + x^2 = 140
2*11*x + x^2 = 19
x^2 + 2*11*x - 19 = 0

Чтобы решить эту проблему, вам нужно сделать еще один sqrt:

x = -11 + sqrt((2*11)^2 + 4 * 19) / 2

Или окончательный ответ:

11+x = sqrt((2*11)^2 + 4 * 19) / 2

Это не быстрее, чем просто делать

sqrt(140)

Если вы ищете быстрое приближение:

x^2 + 2*11*x - 19 = 0
x = (19 - x^2)/(2*11)

Угадывая x = 0,5, получаем

x = 19/(2*11) - 0.5*0.5/(2*11) = 0.852272727

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

person Ishtar    schedule 17.01.2012
comment
На самом деле это нечто совершенно иное. Я смотрю на реализацию VHDL квадратного корня с фиксированной точкой, которая использует только двоичные операции, такие как сдвиг влево / вправо, сложение и вычитание. - person mark mcgehee; 17.01.2012
comment
Чтобы уточнить, это доказательство того, что ответ на ваш вопрос отрицательный, вы не можете вычислить квадратный корень с плавающей запятой, учитывая целое число и остаток. (по крайней мере, это то, что я получаю от этого ...) - person Justin; 17.01.2012
comment
@Ishtar, извините, я подумал, что есть очевидное (простое) решение, которого я не видел в то время - person mark mcgehee; 17.01.2012

arrow_upward
1
arrow_downward

В ответ на:

Кажется, что лучшую точность можно получить, сдвинув подкоренное выражение влево на 2n. Я не совсем уверен, почему это работает? Может ли кто-нибудь объяснить мне

В статье, которую вы связали, говорится о левом сдвиге на 2n. Причина, по которой это работает, заключается в том, что вы эффективно сдвигаете число, кратное 4, что легко вычислить в виде квадратного корня.

sqrt(K*2^2n) = sqrt(K)*sqrt(2^2n) = sqrt(K)*2^n

Итак, вы просто сдвинетесь назад на n бит и получите правильный ответ. Если вы сохраните эти сдвинутые биты как десятичные части, вы получите дробный ответ.

Подумайте об этом в десятичных выражениях: умножение на 100 перед квадратным корнем и деление на 10 после.

So 

sqrt(2) = sqrt(200)/10 = 14/10 = 1.4

Где sqrt (200) дает только целое число.

person Chris    schedule 17.01.2012
comment
Спасибо @Chris за чудесное объяснение! Я могу принять и твой ответ, и ответ Иштар. - person mark mcgehee; 17.01.2012

arrow_upward
0
arrow_downward

Я не уверен, что понимаю ваш вопрос. Вы хотите знать, как использовать функцию sqrt с плавающей точкой или как написать свою собственную?

Если это первое, то ваш язык что-то предоставит (вероятно, это называется sqrt ()). Если последнее, то вам нужно поискать какой-нибудь числовой ресурс. Я бы порекомендовал GSL: http://www.gnu.org/software/gsl/

person invisiblerhino    schedule 17.01.2012
comment
Нет, я знаю, как его использовать :) Я использую не системный sqrt, который уже реализован, а другой алгоритм, который возвращает целую часть числа и остаток (см. Пример) - person mark mcgehee; 17.01.2012
comment
Итак, учитывая int part = 11 и остаток = 19, каков эквивалент float? - person invisiblerhino; 17.01.2012