{"action":"created","issue":{"url":"https://api.github.com/repos/wbhart/flint2/issues/119","labels_url":"https://api.github.com/repos/wbhart/flint2/issues/119/labels{/name}","comments_url":"https://api.github.com/repos/wbhart/flint2/issues/119/comments","events_url":"https://api.github.com/repos/wbhart/flint2/issues/119/events","html_url":"https://github.com/wbhart/flint2/pull/119","id":58722279,"number":119,"title":"rootrem funtctions in ulong_extras module","user":{"login":"kush789","id":7972943,"avatar_url":"https://avatars.githubusercontent.com/u/7972943?v=3","gravatar_id":"","url":"https://api.github.com/users/kush789","html_url":"https://github.com/kush789","followers_url":"https://api.github.com/users/kush789/followers","following_url":"https://api.github.com/users/kush789/following{/other_user}","gists_url":"https://api.github.com/users/kush789/gists{/gist_id}","starred_url":"https://api.github.com/users/kush789/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kush789/subscriptions","organizations_url":"https://api.github.com/users/kush789/orgs","repos_url":"https://api.github.com/users/kush789/repos","events_url":"https://api.github.com/users/kush789/events{/privacy}","received_events_url":"https://api.github.com/users/kush789/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":40,"created_at":"2015-02-24T10:54:15Z","updated_at":"2015-03-06T12:21:36Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/wbhart/flint2/pulls/119","html_url":"https://github.com/wbhart/flint2/pull/119","diff_url":"https://github.com/wbhart/flint2/pull/119.diff","patch_url":"https://github.com/wbhart/flint2/pull/119.patch"},"body":"Hey,\r\n\r\nI have tried to implement two algorithms to calculate the root remainder.\r\n\r\n- One is the newton iteration method present over here - http://en.wikipedia.org/wiki/Nth_root_algorithm. I cant seem to figure out why it is taking up a lot more time than expected. Maybe it's because of the required precision set (small_float in the code) is too small. However increasing it gives wrong answers. Because of this the number of iterations seem to be quite large, almost equivalent to the value of the input number, and increasing as n increases.\r\n\r\n- The second one is an algorithm I found in the book Modern Computer Arithmetic - Richard P. Brent and Paul Zimmermann. A link to the same is here  - http://arxiv.org/pdf/1004.4710.pdf (section 1.5.2, page 29 ) . I found a reference to this book in the source code of mpn_rootrem. This is turning out to be comparable to the mpn_rootrem function when called in flint (including the overheads of changing data types). I have added some preliminary tests before the actual algorithm so as to avoid overflow when calling n_pow and so that time can be saved by using the fast n_pow present.\r\n\r\n- In both functions, the answers match those produced by mpz_rootrem. However the newton iteration method is horridly slow. It is taking up almost half a second for 1 - 1000. The second algorithm is pretty competitive in terms of speed. "},"comment":{"url":"https://api.github.com/repos/wbhart/flint2/issues/comments/77551049","html_url":"https://github.com/wbhart/flint2/pull/119#issuecomment-77551049","issue_url":"https://api.github.com/repos/wbhart/flint2/issues/119","id":77551049,"user":{"login":"fredrik-johansson","id":368838,"avatar_url":"https://avatars.githubusercontent.com/u/368838?v=3","gravatar_id":"","url":"https://api.github.com/users/fredrik-johansson","html_url":"https://github.com/fredrik-johansson","followers_url":"https://api.github.com/users/fredrik-johansson/followers","following_url":"https://api.github.com/users/fredrik-johansson/following{/other_user}","gists_url":"https://api.github.com/users/fredrik-johansson/gists{/gist_id}","starred_url":"https://api.github.com/users/fredrik-johansson/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/fredrik-johansson/subscriptions","organizations_url":"https://api.github.com/users/fredrik-johansson/orgs","repos_url":"https://api.github.com/users/fredrik-johansson/repos","events_url":"https://api.github.com/users/fredrik-johansson/events{/privacy}","received_events_url":"https://api.github.com/users/fredrik-johansson/received_events","type":"User","site_admin":false},"created_at":"2015-03-06T12:21:36Z","updated_at":"2015-03-06T12:21:36Z","body":"Right, there's not much point going much further as it will waste branch prediction resources and code cache. Perhaps add another 1-2 branches covering inputs up to 10000.\r\n\r\nYou could nest branches and effectively end up with a binary search into a precomputed table of cubes with an unrolled basecase, but it's probably not worth it. The Newton algorithm should be fast enough for 99.99% of uses."}}