{"action":"created","comment":{"url":"https://api.github.com/repos/ruHaskell/ruhaskell/pulls/comments/65169965","id":65169965,"diff_hunk":"@@ -0,0 +1,182 @@\n+---\n+author:      Алексей Худяков\n+title:       Улучшение тестов для statistics, часть 1.\n+tags:        numeric\n+description: Длинная история о отладке тестов для statistics и пакета math-functions\n+---\n+\n+Это первый пост из, как мне кажется, длинной серии о том как я исправлял тесты к\n+пакету [`statistics`](http://hackage.haskell.org/package/statistics) и находил и\n+чинил баги в\n+[`math-functions`](http://hackage.haskell.org/package/math-functions). Как и\n+подобает подобному сочинению, оно состоит большей частью из картинок и\n+формул.\n+\n+Тут надо сказать несколько слов похвалы о проекте\n+[IHaskell](http://hackage.haskell.org/package/ihaskell). Отладка численного кода\n+— занятие интерактивное, и один из основных инструментов — рисование\n+графиков. IHaskell делает это относительно удобным. Нотебуки в которых я\n+отлаживал код можно найти в репозитории\n+[numeric-notebooks](https://github.com/Shimuuar/numeric-notebooks).\n+\n+На данный момент (31 мая 2016г.) тесты для `statistics` через раз выдают ложные\n+срабатывания, а может быть и истинные, отличить их всё равно можно только на\n+глаз. Проблема в тестировании численного кода состоит в том, что вычисления с\n+плавающей точкой лишь _аппроксимируют_ вычисления с действительными\n+числами. Потому, если обычно, в тестах можно использовать равенство, то тут\n+приходится использовать приблизительное равенство, причём «приблизительно» в\n+каждом случае будет разным. \n+\n+Для абсолютного большинства действительнозначных функций, в лучшем случае, можно\n+добиться того, что вычисленное значение функции будет отличаться от истинного не\n+более чем на\n+[`0.5·ULP`](https://en.wikipedia.org/wiki/Unit_in_the_last_place). И, конечно\n+же, получить много худшее приближение удивительно легко.\n+Одна из причин этой простоты состоит в том, что ошибки округления не\n+композиционны. Другими словами, даже если функции `f` и `g` приближают истинное\n+значение с точностью не хуже `0.5·ULP`, их композиция `f · g` может не иметь ни\n+одной значащей цифры! Это легко проиллюстрировать на примере из презентации\n+«Needed Remedies for the Undebuggability of Large-Scale Floating-Point\n+Computations in Science and Engineering» W. Kahan:\n+\n+$$f(x) = (-\\log x)^{-1/4} \\qquad g(x) = \\exp( -1/x^4 ) $$\n+\n+Нетрудно видеть, что $(f \\cdot g)(x) = x$, однако, если мы построим графики для\n+`\\x → x` и `\\x → f (g x)`, то увидим катастрофу:\n+\n+<center>\n+![](/files/posts/2016-06-01/loss_of_precision.png)\n+</center>\n+\n+Предоставив читателю шанс подумать о том, откуда взялись катастрофические ошибки\n+округления, рассмотрим к чему приводит неизбежная потеря точности при композиции\n+функций в деле написания тестов. В том случае,если мы хотим просто проверить,\n+что `f x ≈ y` (`y` мы вычислили каким-то другим способом и знаем точно),\n+написать тест просто. Достаточно проверить, что вычисленное значение отличается\n+от точного не более чем на `n` ULP.\n+\n+Но как только мы хотим написать тест для композиции функций, например\n+$(f^{-1}\\cdot{}f)(x)\\approx{}x$, нам придётся учитывать ошибки округления.\n+Наивный подход состоит в том, чтобы сделать консервативную оценку ошибки, не\n+зависящую от `x`. Но он не работает: с большой вероятностью найдётся угол в\n+пространстве параметров, где ошибки округления будут хуже, а для большей части\n+параметров оценка будет слишком консервативной. Таким образом мы приходим к\n+необходимости оценки ошибок округления.\n+\n+\n+## Распространение ошибок\n+\n+Ошибки округления удобнее всего выражать в виде относительных ошибок:\n+$x(1+\\varepsilon)$, так как приключаются они как раз в последних битах мантиссы,\n+и потому всегда составляют некоторую долю числа. Для начала рассмотрим какой\n+ответ даёт _точная_ функция, которой на вход подано число заданное с\n+ошибкой. Будем полагать функцию дифференцируемой, и считая ε малым, ограничимся\n+линейным членом в ряде Тейлора.\n+\n+$$f\\left(x[1+\\varepsilon]\\right)\n+ \\approx f(x) + f'(x)\\cdot x\\varepsilon\n+ = f(x)\\left[1 + \\frac{xf'(x)}{f(x)}\\varepsilon\\right]\n+$$\n+\n+Отсюда видно, что относительная ошибка изменяется в $|xf'(x) / f(x)|$ раз. Пусть\n+теперь у нас есть две функции $f,g :: \\mathbb{R}\\rightarrow\\mathbb{R}$ и их\n+приближение числами с плавающей точкой: $\\bar{f},\\bar{g}$. С этого момента будем\n+обозначать приближённые значения чертой над функцией/значением. Теперь нам надо\n+найти отве на вопрос чему равна ошибка округления для $\\bar{g}(\\bar{f}(x))$?\n+Введём следующие обозначения:\n+\n+$$\\begin{aligned}\n+y &= f(x) \\\\\n+z &= g(y) \\\\\n+\\end{aligned}$$\n+\n+Пусть $x$ является числом, представимым как `Double`, тогда из-за погрешностей\n+округления:\n+\n+$$\\bar{y} = \\bar{f}(x) = y(1 + \\varepsilon_f)$$\n+\n+Вычислим теперь значение _точной_ функции $g(\\bar{y})$\n+\n+$$g(\\bar{y}) = g(y)\\left[1 + \\frac{yg'(y)}{g(y)}\\varepsilon_f\\right]$$\n+\n+Но вычисление $\\bar{g}$ само по себе вносит ошибку округления, так что\n+окончательным ответом будет:\n+\n+$$\\bar{g}(\\bar{f}(x))=g(y)\\left(1+\\frac{yg'(y)}{g(y)}\\varepsilon_f+\\varepsilon_g\\right)$$\n+\n+Теперь мы можем сделать консервативную оценку сверху на относительную\n+погрешность $\\bar{g}(\\bar{f}(x))$. Если мы будем считать максимальную ошибку\n+округления для обоих функций одинаковой, и равной ε, то\n+\n+$$\\varepsilon_{g\\cdot{}f} \\leq \\varepsilon\\left[1+\\left|\\frac{yg'(y)}{g(y)}\\right|\\right]$$\n+\n+Это выражение нетрудно обобщить и на композицию большего числа функций, но нам\n+этого не нужно и мы перейдём к написанию тестов.","path":"posts/numeric/2016-06-01-statistics-test-suite-part1.md","position":114,"original_position":114,"commit_id":"aee86cc0cc42c44384c33395609608d9afd6803d","original_commit_id":"aee86cc0cc42c44384c33395609608d9afd6803d","user":{"login":"cblp","id":63495,"avatar_url":"https://avatars.githubusercontent.com/u/63495?v=3","gravatar_id":"","url":"https://api.github.com/users/cblp","html_url":"https://github.com/cblp","followers_url":"https://api.github.com/users/cblp/followers","following_url":"https://api.github.com/users/cblp/following{/other_user}","gists_url":"https://api.github.com/users/cblp/gists{/gist_id}","starred_url":"https://api.github.com/users/cblp/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cblp/subscriptions","organizations_url":"https://api.github.com/users/cblp/orgs","repos_url":"https://api.github.com/users/cblp/repos","events_url":"https://api.github.com/users/cblp/events{/privacy}","received_events_url":"https://api.github.com/users/cblp/received_events","type":"User","site_admin":false},"body":"\"но нам этого не нужно, и мы перейдём\"","created_at":"2016-05-31T12:15:20Z","updated_at":"2016-05-31T12:15:20Z","html_url":"https://github.com/ruHaskell/ruhaskell/pull/79#discussion_r65169965","pull_request_url":"https://api.github.com/repos/ruHaskell/ruhaskell/pulls/79","_links":{"self":{"href":"https://api.github.com/repos/ruHaskell/ruhaskell/pulls/comments/65169965"},"html":{"href":"https://github.com/ruHaskell/ruhaskell/pull/79#discussion_r65169965"},"pull_request":{"href":"https://api.github.com/repos/ruHaskell/ruhaskell/pulls/79"}}},"pull_request":{"url":"https://api.github.com/repos/ruHaskell/ruhaskell/pulls/79","id":72000742,"html_url":"https://github.com/ruHaskell/ruhaskell/pull/79","diff_url":"https://github.com/ruHaskell/ruhaskell/pull/79.diff","patch_url":"https://github.com/ruHaskell/ruhaskell/pull/79.patch","issue_url":"https://api.github.com/repos/ruHaskell/ruhaskell/issues/79","number":79,"state":"open","locked":false,"title":"Первый пост из серии про тесты statistics","user":{"login":"Shimuuar","id":100394,"avatar_url":"https://avatars.githubusercontent.com/u/100394?v=3","gravatar_id":"","url":"https://api.github.com/users/Shimuuar","html_url":"https://github.com/Shimuuar","followers_url":"https://api.github.com/users/Shimuuar/followers","following_url":"https://api.github.com/users/Shimuuar/following{/other_user}","gists_url":"https://api.github.com/users/Shimuuar/gists{/gist_id}","starred_url":"https://api.github.com/users/Shimuuar/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Shimuuar/subscriptions","organizations_url":"https://api.github.com/users/Shimuuar/orgs","repos_url":"https://api.github.com/users/Shimuuar/repos","events_url":"https://api.github.com/users/Shimuuar/events{/privacy}","received_events_url":"https://api.github.com/users/Shimuuar/received_events","type":"User","site_admin":false},"body":"Я ещё добавил рендеринг формул AmthJax'ом. Без нормальных формул писать подобные статьи вовсе невозможно. ","created_at":"2016-05-31T11:39:31Z","updated_at":"2016-05-31T12:15:20Z","closed_at":null,"merged_at":null,"merge_commit_sha":"a13cf748beebd4444cb361ca2a601de7354d5642","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/ruHaskell/ruhaskell/pulls/79/commits","review_comments_url":"https://api.github.com/repos/ruHaskell/ruhaskell/pulls/79/comments","review_comment_url":"https://api.github.com/repos/ruHaskell/ruhaskell/pulls/comments{/number}","comments_url":"https://api.github.com/repos/ruHaskell/ruhaskell/issues/79/comments","statuses_url":"https://api.github.com/repos/ruHaskell/ruhaskell/statuses/aee86cc0cc42c44384c33395609608d9afd6803d","head":{"label":"Shimuuar:stat","ref":"stat","sha":"aee86cc0cc42c44384c33395609608d9afd6803d","user":{"login":"Shimuuar","id":100394,"avatar_url":"https://avatars.githubusercontent.com/u/100394?v=3","gravatar_id":"","url":"https://api.github.com/users/Shimuuar","html_url":"https://github.com/Shimuuar","followers_url":"https://api.github.com/users/Shimuuar/followers","following_url":"https://api.github.com/users/Shimuuar/following{/other_user}","gists_url":"https://api.github.com/users/Shimuuar/gists{/gist_id}","starred_url":"https://api.github.com/users/Shimuuar/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Shimuuar/subscriptions","organizations_url":"https://api.github.com/users/Shimuuar/orgs","repos_url":"https://api.github.com/users/Shimuuar/repos","events_url":"https://api.github.com/users/Shimuuar/events{/privacy}","received_events_url":"https://api.github.com/users/Shimuuar/received_events","type":"User","site_admin":false},"repo":{"id":60026481,"name":"ruhaskell","full_name":"Shimuuar/ruhaskell","owner":{"login":"Shimuuar","id":100394,"avatar_url":"https://avatars.githubusercontent.com/u/100394?v=3","gravatar_id":"","url":"https://api.github.com/users/Shimuuar","html_url":"https://github.com/Shimuuar","followers_url":"https://api.github.com/users/Shimuuar/followers","following_url":"https://api.github.com/users/Shimuuar/following{/other_user}","gists_url":"https://api.github.com/users/Shimuuar/gists{/gist_id}","starred_url":"https://api.github.com/users/Shimuuar/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Shimuuar/subscriptions","organizations_url":"https://api.github.com/users/Shimuuar/orgs","repos_url":"https://api.github.com/users/Shimuuar/repos","events_url":"https://api.github.com/users/Shimuuar/events{/privacy}","received_events_url":"https://api.github.com/users/Shimuuar/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/Shimuuar/ruhaskell","description":"Главный сайт сообщества","fork":true,"url":"https://api.github.com/repos/Shimuuar/ruhaskell","forks_url":"https://api.github.com/repos/Shimuuar/ruhaskell/forks","keys_url":"https://api.github.com/repos/Shimuuar/ruhaskell/keys{/key_id}","collaborators_url":"https://api.github.com/repos/Shimuuar/ruhaskell/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/Shimuuar/ruhaskell/teams","hooks_url":"https://api.github.com/repos/Shimuuar/ruhaskell/hooks","issue_events_url":"https://api.github.com/repos/Shimuuar/ruhaskell/issues/events{/number}","events_url":"https://api.github.com/repos/Shimuuar/ruhaskell/events","assignees_url":"https://api.github.com/repos/Shimuuar/ruhaskell/assignees{/user}","branches_url":"https://api.github.com/repos/Shimuuar/ruhaskell/branches{/branch}","tags_url":"https://api.github.com/repos/Shimuuar/ruhaskell/tags","blobs_url":"https://api.github.com/repos/Shimuuar/ruhaskell/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/Shimuuar/ruhaskell/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/Shimuuar/ruhaskell/git/refs{/sha}","trees_url":"https://api.github.com/repos/Shimuuar/ruhaskell/git/trees{/sha}","statuses_url":"https://api.github.com/repos/Shimuuar/ruhaskell/statuses/{sha}","languages_url":"https://api.github.com/repos/Shimuuar/ruhaskell/languages","stargazers_url":"https://api.github.com/repos/Shimuuar/ruhaskell/stargazers","contributors_url":"https://api.github.com/repos/Shimuuar/ruhaskell/contributors","subscribers_url":"https://api.github.com/repos/Shimuuar/ruhaskell/subscribers","subscription_url":"https://api.github.com/repos/Shimuuar/ruhaskell/subscription","commits_url":"https://api.github.com/repos/Shimuuar/ruhaskell/commits{/sha}","git_commits_url":"https://api.github.com/repos/Shimuuar/ruhaskell/git/commits{/sha}","comments_url":"https://api.github.com/repos/Shimuuar/ruhaskell/comments{/number}","issue_comment_url":"https://api.github.com/repos/Shimuuar/ruhaskell/issues/comments{/number}","contents_url":"https://api.github.com/repos/Shimuuar/ruhaskell/contents/{+path}","compare_url":"https://api.github.com/repos/Shimuuar/ruhaskell/compare/{base}...{head}","merges_url":"https://api.github.com/repos/Shimuuar/ruhaskell/merges","archive_url":"https://api.github.com/repos/Shimuuar/ruhaskell/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/Shimuuar/ruhaskell/downloads","issues_url":"https://api.github.com/repos/Shimuuar/ruhaskell/issues{/number}","pulls_url":"https://api.github.com/repos/Shimuuar/ruhaskell/pulls{/number}","milestones_url":"https://api.github.com/repos/Shimuuar/ruhaskell/milestones{/number}","notifications_url":"https://api.github.com/repos/Shimuuar/ruhaskell/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/Shimuuar/ruhaskell/labels{/name}","releases_url":"https://api.github.com/repos/Shimuuar/ruhaskell/releases{/id}","deployments_url":"https://api.github.com/repos/Shimuuar/ruhaskell/deployments","created_at":"2016-05-30T17:08:42Z","updated_at":"2016-05-30T17:08:43Z","pushed_at":"2016-05-31T11:36:52Z","git_url":"git://github.com/Shimuuar/ruhaskell.git","ssh_url":"git@github.com:Shimuuar/ruhaskell.git","clone_url":"https://github.com/Shimuuar/ruhaskell.git","svn_url":"https://github.com/Shimuuar/ruhaskell","homepage":"http://ruhaskell.org","size":7987,"stargazers_count":0,"watchers_count":0,"language":"Haskell","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"ruHaskell:master","ref":"master","sha":"c1f0752acd76096316c2f29af6434dce73b85e1c","user":{"login":"ruHaskell","id":10528804,"avatar_url":"https://avatars.githubusercontent.com/u/10528804?v=3","gravatar_id":"","url":"https://api.github.com/users/ruHaskell","html_url":"https://github.com/ruHaskell","followers_url":"https://api.github.com/users/ruHaskell/followers","following_url":"https://api.github.com/users/ruHaskell/following{/other_user}","gists_url":"https://api.github.com/users/ruHaskell/gists{/gist_id}","starred_url":"https://api.github.com/users/ruHaskell/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ruHaskell/subscriptions","organizations_url":"https://api.github.com/users/ruHaskell/orgs","repos_url":"https://api.github.com/users/ruHaskell/repos","events_url":"https://api.github.com/users/ruHaskell/events{/privacy}","received_events_url":"https://api.github.com/users/ruHaskell/received_events","type":"Organization","site_admin":false},"repo":{"id":29236630,"name":"ruhaskell","full_name":"ruHaskell/ruhaskell","owner":{"login":"ruHaskell","id":10528804,"avatar_url":"https://avatars.githubusercontent.com/u/10528804?v=3","gravatar_id":"","url":"https://api.github.com/users/ruHaskell","html_url":"https://github.com/ruHaskell","followers_url":"https://api.github.com/users/ruHaskell/followers","following_url":"https://api.github.com/users/ruHaskell/following{/other_user}","gists_url":"https://api.github.com/users/ruHaskell/gists{/gist_id}","starred_url":"https://api.github.com/users/ruHaskell/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ruHaskell/subscriptions","organizations_url":"https://api.github.com/users/ruHaskell/orgs","repos_url":"https://api.github.com/users/ruHaskell/repos","events_url":"https://api.github.com/users/ruHaskell/events{/privacy}","received_events_url":"https://api.github.com/users/ruHaskell/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/ruHaskell/ruhaskell","description":"Главный сайт сообщества","fork":false,"url":"https://api.github.com/repos/ruHaskell/ruhaskell","forks_url":"https://api.github.com/repos/ruHaskell/ruhaskell/forks","keys_url":"https://api.github.com/repos/ruHaskell/ruhaskell/keys{/key_id}","collaborators_url":"https://api.github.com/repos/ruHaskell/ruhaskell/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/ruHaskell/ruhaskell/teams","hooks_url":"https://api.github.com/repos/ruHaskell/ruhaskell/hooks","issue_events_url":"https://api.github.com/repos/ruHaskell/ruhaskell/issues/events{/number}","events_url":"https://api.github.com/repos/ruHaskell/ruhaskell/events","assignees_url":"https://api.github.com/repos/ruHaskell/ruhaskell/assignees{/user}","branches_url":"https://api.github.com/repos/ruHaskell/ruhaskell/branches{/branch}","tags_url":"https://api.github.com/repos/ruHaskell/ruhaskell/tags","blobs_url":"https://api.github.com/repos/ruHaskell/ruhaskell/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/ruHaskell/ruhaskell/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/ruHaskell/ruhaskell/git/refs{/sha}","trees_url":"https://api.github.com/repos/ruHaskell/ruhaskell/git/trees{/sha}","statuses_url":"https://api.github.com/repos/ruHaskell/ruhaskell/statuses/{sha}","languages_url":"https://api.github.com/repos/ruHaskell/ruhaskell/languages","stargazers_url":"https://api.github.com/repos/ruHaskell/ruhaskell/stargazers","contributors_url":"https://api.github.com/repos/ruHaskell/ruhaskell/contributors","subscribers_url":"https://api.github.com/repos/ruHaskell/ruhaskell/subscribers","subscription_url":"https://api.github.com/repos/ruHaskell/ruhaskell/subscription","commits_url":"https://api.github.com/repos/ruHaskell/ruhaskell/commits{/sha}","git_commits_url":"https://api.github.com/repos/ruHaskell/ruhaskell/git/commits{/sha}","comments_url":"https://api.github.com/repos/ruHaskell/ruhaskell/comments{/number}","issue_comment_url":"https://api.github.com/repos/ruHaskell/ruhaskell/issues/comments{/number}","contents_url":"https://api.github.com/repos/ruHaskell/ruhaskell/contents/{+path}","compare_url":"https://api.github.com/repos/ruHaskell/ruhaskell/compare/{base}...{head}","merges_url":"https://api.github.com/repos/ruHaskell/ruhaskell/merges","archive_url":"https://api.github.com/repos/ruHaskell/ruhaskell/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/ruHaskell/ruhaskell/downloads","issues_url":"https://api.github.com/repos/ruHaskell/ruhaskell/issues{/number}","pulls_url":"https://api.github.com/repos/ruHaskell/ruhaskell/pulls{/number}","milestones_url":"https://api.github.com/repos/ruHaskell/ruhaskell/milestones{/number}","notifications_url":"https://api.github.com/repos/ruHaskell/ruhaskell/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/ruHaskell/ruhaskell/labels{/name}","releases_url":"https://api.github.com/repos/ruHaskell/ruhaskell/releases{/id}","deployments_url":"https://api.github.com/repos/ruHaskell/ruhaskell/deployments","created_at":"2015-01-14T09:20:51Z","updated_at":"2016-05-27T21:39:34Z","pushed_at":"2016-05-31T11:39:32Z","git_url":"git://github.com/ruHaskell/ruhaskell.git","ssh_url":"git@github.com:ruHaskell/ruhaskell.git","clone_url":"https://github.com/ruHaskell/ruhaskell.git","svn_url":"https://github.com/ruHaskell/ruhaskell","homepage":"http://ruhaskell.org","size":7836,"stargazers_count":97,"watchers_count":97,"language":"Haskell","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":27,"mirror_url":null,"open_issues_count":2,"forks":27,"open_issues":2,"watchers":97,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/ruHaskell/ruhaskell/pulls/79"},"html":{"href":"https://github.com/ruHaskell/ruhaskell/pull/79"},"issue":{"href":"https://api.github.com/repos/ruHaskell/ruhaskell/issues/79"},"comments":{"href":"https://api.github.com/repos/ruHaskell/ruhaskell/issues/79/comments"},"review_comments":{"href":"https://api.github.com/repos/ruHaskell/ruhaskell/pulls/79/comments"},"review_comment":{"href":"https://api.github.com/repos/ruHaskell/ruhaskell/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/ruHaskell/ruhaskell/pulls/79/commits"},"statuses":{"href":"https://api.github.com/repos/ruHaskell/ruhaskell/statuses/aee86cc0cc42c44384c33395609608d9afd6803d"}}}}
{"actor":{"display_login":"cblp"}}