Найти квадратный корень как float от int и остаток?

Question

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

Так, например: 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.Я не совсем уверен, почему это работает?Может ли кто-нибудь, пожалуйста, объясните мне

Answer 1

(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)

Гадание х = 0,5 дает

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

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

Answer 2

В ответ на:

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

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

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

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

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

Итак

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

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

Answer 3

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

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