{"action":"created","issue":{"url":"https://api.github.com/repos/Nemocas/AbstractAlgebra.jl/issues/36","repository_url":"https://api.github.com/repos/Nemocas/AbstractAlgebra.jl","labels_url":"https://api.github.com/repos/Nemocas/AbstractAlgebra.jl/issues/36/labels{/name}","comments_url":"https://api.github.com/repos/Nemocas/AbstractAlgebra.jl/issues/36/comments","events_url":"https://api.github.com/repos/Nemocas/AbstractAlgebra.jl/issues/36/events","html_url":"https://github.com/Nemocas/AbstractAlgebra.jl/issues/36","id":297069139,"number":36,"title":"Implement Euclidean function for Euclidean domains","user":{"login":"wbhart","id":242598,"avatar_url":"https://avatars1.githubusercontent.com/u/242598?v=4","gravatar_id":"","url":"https://api.github.com/users/wbhart","html_url":"https://github.com/wbhart","followers_url":"https://api.github.com/users/wbhart/followers","following_url":"https://api.github.com/users/wbhart/following{/other_user}","gists_url":"https://api.github.com/users/wbhart/gists{/gist_id}","starred_url":"https://api.github.com/users/wbhart/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/wbhart/subscriptions","organizations_url":"https://api.github.com/users/wbhart/orgs","repos_url":"https://api.github.com/users/wbhart/repos","events_url":"https://api.github.com/users/wbhart/events{/privacy}","received_events_url":"https://api.github.com/users/wbhart/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":1,"created_at":"2018-02-14T11:55:11Z","updated_at":"2018-02-14T12:30:41Z","closed_at":null,"author_association":"NONE","body":"It makes sense to require that all Euclidean domains provide a Euclidean function (though I'm not sure what to do when there is more than one).\r\n\r\nIt's not immediately clear if this can be done generically, for example, given a Euclidean division function one can't easily retrieve the Euclidean function.  And given a Euclidean function, it is obviously possible to compute a GCD, but this might not even be the most efficient generic way of doing it, which raises the question: how does the implementation decide whether to use the Euclidean function or use the gcd function which is currently implemented in terms of the required Euclidean division function.\r\n\r\nSo the metaphysical question here is whether a Euclidean domain on a computer is a domain that provides a Euclidean division function, or whether it is a domain that provides a Euclidean function."},"comment":{"url":"https://api.github.com/repos/Nemocas/AbstractAlgebra.jl/issues/comments/365593351","html_url":"https://github.com/Nemocas/AbstractAlgebra.jl/issues/36#issuecomment-365593351","issue_url":"https://api.github.com/repos/Nemocas/AbstractAlgebra.jl/issues/36","id":365593351,"user":{"login":"wbhart","id":242598,"avatar_url":"https://avatars1.githubusercontent.com/u/242598?v=4","gravatar_id":"","url":"https://api.github.com/users/wbhart","html_url":"https://github.com/wbhart","followers_url":"https://api.github.com/users/wbhart/followers","following_url":"https://api.github.com/users/wbhart/following{/other_user}","gists_url":"https://api.github.com/users/wbhart/gists{/gist_id}","starred_url":"https://api.github.com/users/wbhart/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/wbhart/subscriptions","organizations_url":"https://api.github.com/users/wbhart/orgs","repos_url":"https://api.github.com/users/wbhart/repos","events_url":"https://api.github.com/users/wbhart/events{/privacy}","received_events_url":"https://api.github.com/users/wbhart/received_events","type":"User","site_admin":false},"created_at":"2018-02-14T12:30:41Z","updated_at":"2018-02-14T12:30:41Z","author_association":"NONE","body":"On 14 February 2018 at 13:17, Claus Fieker <notifications@github.com> wrote:\n\n> On Wed, Feb 14, 2018 at 03:55:13AM -0800, wbhart wrote:\n> > It makes sense to require that all Euclidean domains provide a Euclidean\n> function (though I'm not sure what to do when there is more than one).\n> >\n> > It's not immediately clear if this can be done generically, for example,\n> given a Euclidean gcd one can't easily retrieve the Euclidean function. And\n> given a Euclidean function, it is obviously possible to compute a GCD, but\n> this might not even be the most efficient generic way of doing it, which\n> raises the question: how does the implementation decide whether to use the\n> Euclidean function or use the gcd function which is currently implemented\n> in terms of the required Euclidean division function.\n> >\n>\n> There are a range of different questions\n> - the gcd has nothing to do with the euclidean function\n>\n\nYes, I meant Euclidean division, not GCD. Typo (twice).\n\n\n> - only divrem use phi (bad name)\n> - Z/nZ eg. has 2 different euclidean functions\n> phi(a) = |a| -> divrem from Z\n> phi(a) = gcd(n, a) in Z -> yields more general strategy\n> they give, of course, different divrem, but the same gcd...\n> - you cannot move from gcd -> phi, neither (I think) from phi -> gcd\n> phi does divrem, divrem does gcd\n> In general:\n> - computing phi is independent of computing divrem\n> - computing divrem is independent computing gcd\n> - ...\n> These are 3 different functions that need to be consistent,\n\n\nI'm mainly talking about the generics here, not specific rings, where it is\nclear what to do.\n\nFirstly, can you give an example of an application for the Euclidean\nfunction, other than Euclidean division?\n\nbut can\n> be implemented independently.\n> For Z/nZ all is trivial...\n> For Z_K/M all is interesting...\n>\n"}}
{"actor":{"display_login":"wbhart"}}