{"action":"created","issue":{"url":"https://api.github.com/repos/cartazio/arithmoi/issues/30","repository_url":"https://api.github.com/repos/cartazio/arithmoi","labels_url":"https://api.github.com/repos/cartazio/arithmoi/issues/30/labels{/name}","comments_url":"https://api.github.com/repos/cartazio/arithmoi/issues/30/comments","events_url":"https://api.github.com/repos/cartazio/arithmoi/issues/30/events","html_url":"https://github.com/cartazio/arithmoi/pull/30","id":160539530,"number":30,"title":"New arithmetic functions","user":{"login":"Bodigrim","id":2293557,"avatar_url":"https://avatars.githubusercontent.com/u/2293557?v=3","gravatar_id":"","url":"https://api.github.com/users/Bodigrim","html_url":"https://github.com/Bodigrim","followers_url":"https://api.github.com/users/Bodigrim/followers","following_url":"https://api.github.com/users/Bodigrim/following{/other_user}","gists_url":"https://api.github.com/users/Bodigrim/gists{/gist_id}","starred_url":"https://api.github.com/users/Bodigrim/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Bodigrim/subscriptions","organizations_url":"https://api.github.com/users/Bodigrim/orgs","repos_url":"https://api.github.com/users/Bodigrim/repos","events_url":"https://api.github.com/users/Bodigrim/events{/privacy}","received_events_url":"https://api.github.com/users/Bodigrim/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":5,"created_at":"2016-06-15T22:34:45Z","updated_at":"2016-07-05T20:31:19Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/cartazio/arithmoi/pulls/30","html_url":"https://github.com/cartazio/arithmoi/pull/30","diff_url":"https://github.com/cartazio/arithmoi/pull/30.diff","patch_url":"https://github.com/cartazio/arithmoi/pull/30.patch"},"body":"This branch aims to refactor implementation of number-theoretic functions on the modern basis. \r\n\r\nThe released `arithmoi` provides a few arithmetic functions, including the divisors function `tau`, the sum of divisors function `sigma`, `totient`, `moebius` and `carmichael`. All of them have monomorphic type `Integer -> Integer`. There are several areas to improve:\r\n\r\n1. One may need arithmetic functions, working on other domains. This includes both `Int`, `Word`, `Natural` arguments (where one may expect better performance than in general case), and other unique factorisation domains, such as `GaussianInteger` (and many others in future). We should have a way to define arithmetic function polymorphically.\r\n\r\n2. There is no helpers to define new arithmetic functions. Every time one have to write everything from the scratch. Simple wrappers for common classes (multiplicative, additive, etc.) would simplify a deal. \r\n\r\n3. Current functions lacks composability. For example, if I want to compute sum of `totient` and `moebius` on the same argument, the argument will be factored twice, which is expensive. The type of arithmetic function should be `Applicative`. \r\n\r\nThe proposed branch addresses the issues above. It includes new `UniqueFactorisation` type class to collect all unique factorisation domains under single interface. It also includes a special type `ArithmeticFunction` with a pack of useful instances and helpers. Both changes introduces additional abstraction layers, but I have managed to minimise their impact on performance. \r\n\r\nMy intention was to avoid low-level stuff (unboxed types and tuples) and thoughtless pragmas INLINE / SPECIALISE. `unsafeCoerce` is the only trick, which is used widely to convert between small positive integers of different types. It is ugly, but quite safe and has significant effect on performance. \r\n\r\nHere are benchmarks:\r\n\r\n```\r\nbenchmarking divisors/old\r\ntime                 456.4 ms   (409.3 ms .. 500.3 ms)\r\nbenchmarking divisors/new\r\ntime                 525.9 ms   (NaN s .. 541.0 ms)\r\nbenchmarking divisors/newint\r\ntime                 305.9 ms   (301.4 ms .. 308.1 ms)\r\n\r\nbenchmarking totient/old\r\ntime                 185.7 ms   (174.0 ms .. 197.6 ms)\r\nbenchmarking totient/new\r\ntime                 192.3 ms   (181.4 ms .. 203.8 ms)\r\n\r\nbenchmarking carmichael/old\r\ntime                 200.1 ms   (193.3 ms .. 204.9 ms)\r\nbenchmarking carmichael/new\r\ntime                 210.2 ms   (203.0 ms .. 216.3 ms)\r\n\r\nbenchmarking moebius/old\r\ntime                 129.7 ms   (121.9 ms .. 145.6 ms)\r\nbenchmarking moebius/new\r\ntime                 130.3 ms   (125.6 ms .. 134.9 ms)\r\n\r\nbenchmarking tau/old\r\ntime                 183.7 ms   (176.4 ms .. 197.6 ms)\r\nbenchmarking tau/new\r\ntime                 181.6 ms   (167.0 ms .. 195.8 ms)\r\n\r\nbenchmarking sigma 1/old\r\ntime                 188.2 ms   (180.1 ms .. 195.8 ms)\r\nbenchmarking sigma 1/new\r\ntime                 186.8 ms   (184.5 ms .. 190.4 ms)\r\n\r\nbenchmarking sigma 2/old\r\ntime                 245.1 ms   (235.7 ms .. 265.8 ms)\r\nbenchmarking sigma 2/new\r\ntime                 213.3 ms   (197.3 ms .. 226.3 ms)\r\n```"},"comment":{"url":"https://api.github.com/repos/cartazio/arithmoi/issues/comments/230593813","html_url":"https://github.com/cartazio/arithmoi/pull/30#issuecomment-230593813","issue_url":"https://api.github.com/repos/cartazio/arithmoi/issues/30","id":230593813,"user":{"login":"Bodigrim","id":2293557,"avatar_url":"https://avatars.githubusercontent.com/u/2293557?v=3","gravatar_id":"","url":"https://api.github.com/users/Bodigrim","html_url":"https://github.com/Bodigrim","followers_url":"https://api.github.com/users/Bodigrim/followers","following_url":"https://api.github.com/users/Bodigrim/following{/other_user}","gists_url":"https://api.github.com/users/Bodigrim/gists{/gist_id}","starred_url":"https://api.github.com/users/Bodigrim/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Bodigrim/subscriptions","organizations_url":"https://api.github.com/users/Bodigrim/orgs","repos_url":"https://api.github.com/users/Bodigrim/repos","events_url":"https://api.github.com/users/Bodigrim/events{/privacy}","received_events_url":"https://api.github.com/users/Bodigrim/received_events","type":"User","site_admin":false},"created_at":"2016-07-05T20:31:19Z","updated_at":"2016-07-05T20:31:19Z","body":"Fixed. GHC 7.6 is a real headache. \r\n\r\nAny more comments?"}}
{"actor":{"display_login":"Bodigrim"}}