?

Log in

No account? Create an account

Математический реверс-инжиниринг - Общество дровосеков Бердичева по изучению Мишны

Oct. 22nd, 2016

07:20 pm - Математический реверс-инжиниринг

Previous Entry Share Next Entry

Или "разговор программиста с математиком о магии числ".
Послесловие к моему предыдущему посту, чтобы не вышло допытывания инженера у математика о непонятном, как xaxam упоминал.

Имеется такая довольно быстрая функция, вычисляющая квадратный корень с хорошей точностью:
Пусть x = a*22b, где 0.25 <= a < 1. Тогда sqrt(x) = sqrt(a)*2b.
Для вычисления sqrt(a) положим
r = 0.365681 + 5a/8
и 3 раза выполним
r = (r + a/r)/2
Максимальная относительная погрешность результата объявляется равной 1.2810-13.

Вопрос к математическим обратным инженерам - каким образом получены значения 0.365681 и 5/8?
(Чтобы гуглические обратные инженеры не мучились ищучи, откуда я это взял: https://pure.tue.nl/ws/files/3023549/674735.pdf)

В книге Computer Approximations by J. F. Hart et al., 1968 (цит. по pers. comm.) приводится такая формула:
Пусть x = a*2b, где 0.5 <= a < 1.
Тогда sqrt(x) = sqrt(a)*2[b/2]*{b mod 2 = 0: 1; b mod 2 = 1: sqrt(2)}.
Для вычисления sqrt(a) положим
r = -0.204405847*a2+0.890194099*a+0.313567057
и 2 раза выполним
r = (r + a/r)/2
Ее максимальная относительная погрешность утверждается равной 1.510-12.

Как получены приведенные значения коэффициентов?

(Символ ⏨ заменен на 10 по просьбе трудящихся пользователей Win7.)

Comments:

[User Picture]
From:lesamohval
Date:October 23rd, 2016 02:35 am (UTC)
(Link)
Я ССЗБ(
(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 23rd, 2016 02:49 am (UTC)
(Link)
Win7?
(Reply) (Parent) (Thread)
[User Picture]
From:lesamohval
Date:October 23rd, 2016 03:09 am (UTC)
(Link)
ога. но установлен универсальный набор шрифтов!любые иероглифы вижу
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:October 23rd, 2016 03:19 am (UTC)
(Link)
Видимо, ни один шрифт из этого набора не стоит.
(Reply) (Parent) (Thread)
[User Picture]
From:lesamohval
Date:October 23rd, 2016 04:03 am (UTC)
(Link)
что это?
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:October 23rd, 2016 04:58 am (UTC)
(Link)
Это список фонтов, в которых есть использованный символ.
Я сейчас попробовал. У меня Symbola стоит, тут в соотв. строке он виден, а браузеры не показывают.
Похоже, что проблема в самом Win7. Ладно, исправлю пост.
(Reply) (Parent) (Thread)
[User Picture]
From:kcmamu
Date:October 23rd, 2016 07:15 am (UTC)
(Link)
5/8 выбрано, чтобы умножать было легко (а оптимальное значение 1/3 + sqrt(2)/4).
(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 23rd, 2016 03:53 pm (UTC)
(Link)
У меня в пятницу столько же получилось, но оно настолько отличается от 5/8, что я не поверил.

Вызывает удивление, что в обоих алгоритмах используется деление вместо аппроксимации обратного значения и умножения.
(Reply) (Parent) (Thread)
[User Picture]
From:janatem
Date:October 23rd, 2016 08:58 am (UTC)
(Link)
Наверно константы можно найти чисто в лоб, записав соответствующий функционал невязки и (приблизительно) найдя его минимум. Количество итераций задается ad hoc (потом проверяется, что полученная погрешность удовл). Вот еще та знаменитая константа из Квейка, там объясняется, как она была найдена, но я что-то не вкурил.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:October 23rd, 2016 04:21 pm (UTC)
(Link)
Понятно, как она была найдена, но непонятно, что за магическое число 0.512964. :)
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:October 23rd, 2016 04:29 pm (UTC)
(Link)
Количество итераций в случае кв. корня определяется желаемой точностью и точностью полученного приближения: каждая итерация увеличивает точность вдвое. Или можно идти назад: задав, сколько итераций мы готовы делать в конце, легко получить необходимую точность первоначального приближения.

(Reply) (Parent) (Thread)
[User Picture]
From:pappadeux
Date:October 23rd, 2016 05:18 pm (UTC)
(Link)
гггг

вспомнил о том же
(Reply) (Parent) (Thread)