Г-н Фаршеклоакин (spamsink) wrote,
Г-н Фаршеклоакин
spamsink

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

Или "разговор программиста с математиком о магии числ".
Послесловие к моему предыдущему посту, чтобы не вышло допытывания инженера у математика о непонятном, как 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.)
Subscribe

  • Это что за орфографические новости?

    В одном ютубовском ролике, который автор стесняется озвучивать голосом, в субтитрах замечены слова вида puttx, poppx, havx, gettx, eatx, gox. Судя…

  • Юникод для новояза

    В списке кодов, предложенных к включению в юникод версии 14: 1AC9..1ACA 2 COMBINING DOUBLE PLUS SIGN ABOVE COMBINING DOUBLE PLUS SIGN BELOW Также…

  • Ни на что не намекаю, просто песенку пою

    Подсадил меня Ютуб в последние дни на песенный конкурс для детей, оставшихся без попечения родителей "Ты супер!" (по-моему, весьма полезное,…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 12 comments

  • Это что за орфографические новости?

    В одном ютубовском ролике, который автор стесняется озвучивать голосом, в субтитрах замечены слова вида puttx, poppx, havx, gettx, eatx, gox. Судя…

  • Юникод для новояза

    В списке кодов, предложенных к включению в юникод версии 14: 1AC9..1ACA 2 COMBINING DOUBLE PLUS SIGN ABOVE COMBINING DOUBLE PLUS SIGN BELOW Также…

  • Ни на что не намекаю, просто песенку пою

    Подсадил меня Ютуб в последние дни на песенный конкурс для детей, оставшихся без попечения родителей "Ты супер!" (по-моему, весьма полезное,…