archive/issues_020334.json:
{
"assignees": [],
"body": "<div id=\"comment:0\"></div>\n\nIn #20086 a `nth_root` method for polynomial was implemented using factorization. But we can use Newton method for that!\n\nIt is faster than factorization even over ZZ where factor is highly optimized:\n\n```\nsage: x = polygen(ZZ)\nsage: p = x**14 + x**3 - 12\n\nsage: q = p**13\nsage: %timeit _ = q.nth_root(13)\n1000 loops, best of 3: 416 \u00b5s per loop\nsage: %timeit _ = q.factor()\n1000 loops, best of 3: 895 \u00b5s per loop\n\nsage: q = p**37\nsage: %timeit _ = q.nth_root(37)\n1000 loops, best of 3: 1.17 \u00b5s per loop\nsage: %timeit _ = q.factor()\n100 loops, best of 3: 3.92 ms per loop\n```\nAnd the Newton method also works over polynomial when factorization is not implemented\n\n```\nsage: R1.<x> = QQ[]\nsage: R2.<y> = R1[]\nsage: R3.<z> = R2[]\nsage: q = (x+y+z)**3\nsage: q.factor()\nTraceback (most recent call last):\n...\nNotImplementedError: \nsage: q.nth_root(3)\nz + y + x\n```\n\nCC: @nbruin @behackl @kedlaya\n\nComponent: **algebra**\n\nAuthor: **Vincent Delecroix**\n\nBranch/Commit: **[`24ffc9f`](https://github.com/sagemath/sagetrac-mirror/commit/24ffc9fca48ab2ce4123ba83cefe5543a11114c8)**\n\nReviewer: **Bruno Grenet**\n\n_Issue created by migration from https://trac.sagemath.org/ticket/20571_\n\n",
"closed_at": "2016-06-14T07:10:26Z",
"created_at": "2016-05-08T01:51:36Z",
"labels": [
"https://github.com/sagemath/sage/labels/c%3A%20algebra",
"https://github.com/sagemath/sage/labels/p%3A%20major%20/%203",
"https://github.com/sagemath/sage/labels/enhancement"
],
"milestone": "https://github.com/sagemath/sage/milestones/sage-7.3",
"reactions": [],
"repository": "https://github.com/sagemath/sage",
"title": "Newton method for nth_root of polynomial",
"type": "issue",
"updated_at": "2016-06-14T07:10:26Z",
"url": "https://github.com/sagemath/sage/issues/20571",
"user": "https://github.com/videlec"
}In #20086 a nth_root method for polynomial was implemented using factorization. But we can use Newton method for that!
It is faster than factorization even over ZZ where factor is highly optimized:
sage: x = polygen(ZZ)
sage: p = x**14 + x**3 - 12
sage: q = p**13
sage: %timeit _ = q.nth_root(13)
1000 loops, best of 3: 416 µs per loop
sage: %timeit _ = q.factor()
1000 loops, best of 3: 895 µs per loop
sage: q = p**37
sage: %timeit _ = q.nth_root(37)
1000 loops, best of 3: 1.17 µs per loop
sage: %timeit _ = q.factor()
100 loops, best of 3: 3.92 ms per loop
And the Newton method also works over polynomial when factorization is not implemented
sage: R1.<x> = QQ[]
sage: R2.<y> = R1[]
sage: R3.<z> = R2[]
sage: q = (x+y+z)**3
sage: q.factor()
Traceback (most recent call last):
...
NotImplementedError:
sage: q.nth_root(3)
z + y + x
CC: @nbruin @behackl @kedlaya
Component: algebra
Author: Vincent Delecroix
Branch/Commit: 24ffc9f
Reviewer: Bruno Grenet
Issue created by migration from https://trac.sagemath.org/ticket/20571
archive/issue_events_287265.json:
{
"actor": "https://github.com/videlec",
"created_at": "2016-05-08T01:51:36Z",
"event": "milestoned",
"issue": "https://github.com/sagemath/sage/issues/20571",
"milestone_number": null,
"milestone_title": "sage-7.2",
"type": "issue_event",
"url": "https://github.com/sagemath/sage/issues/20571#event-287265"
}archive/issue_events_287266.json:
{
"actor": "https://github.com/videlec",
"created_at": "2016-05-08T01:51:36Z",
"event": "labeled",
"issue": "https://github.com/sagemath/sage/issues/20571",
"label": "https://github.com/sagemath/sage/labels/c%3A%20algebra",
"label_color": "0000ff",
"label_name": "c: algebra",
"label_text_color": "ffffff",
"type": "issue_event",
"url": "https://github.com/sagemath/sage/issues/20571#event-287266"
}archive/issue_events_287267.json:
{
"actor": "https://github.com/videlec",
"created_at": "2016-05-08T01:51:36Z",
"event": "labeled",
"issue": "https://github.com/sagemath/sage/issues/20571",
"label": "https://github.com/sagemath/sage/labels/p%3A%20major%20/%203",
"label_color": "ffbb00",
"label_name": "p: major / 3",
"label_text_color": "ffffff",
"type": "issue_event",
"url": "https://github.com/sagemath/sage/issues/20571#event-287267"
}archive/issue_events_287268.json:
{
"actor": "https://github.com/videlec",
"created_at": "2016-05-08T01:51:36Z",
"event": "labeled",
"issue": "https://github.com/sagemath/sage/issues/20571",
"label": "https://github.com/sagemath/sage/labels/enhancement",
"label_color": "696969",
"label_name": "enhancement",
"label_text_color": "ffffff",
"type": "issue_event",
"url": "https://github.com/sagemath/sage/issues/20571#event-287268"
}archive/issue_comments_297364.json:
{
"body": "<div id=\"comment:1\" align=\"right\">comment:1</div>\n\nWaiting for #20086 to be merged... in the mean time people can have a look at [attachment: poly_nth_root.py](https://github.com/sagemath/sage/files/ticket20571/poly_nth_root.py.gz).",
"created_at": "2016-05-08T01:58:39Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20571",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20571#issuecomment-297364",
"user": "https://github.com/videlec"
}comment:1
Waiting for #20086 to be merged... in the mean time people can have a look at attachment: poly_nth_root.py.
archive/issue_comments_297365.json:
{
"body": "Description changed:\n``````diff\n--- \n+++ \n@@ -1 +1,19 @@\n We can use Newton method to compute n-th root of polynomials. In all (?) cases, this should be much more efficient than relying on factorisation.\n+\n+An example of a x4 faster compared to factorization\n+\n+```\n+sage: p = x**14 + x**3 - 12\n+\n+sage: q = p**13\n+sage: %timeit _ = nth_root(q, 13)\n+1000 loops, best of 3: 216 \u00b5s per loop\n+sage: %timeit _ = q.factor()\n+1000 loops, best of 3: 895 \u00b5s per loop\n+\n+sage: q = p**37\n+sage: %timeit _ = nth_root(q, 37)\n+1000 loops, best of 3: 625 \u00b5s per loop\n+sage: %timeit _ = q.factor()\n+100 loops, best of 3: 3.92 ms per loop\n+```\n``````\n",
"created_at": "2016-05-08T02:16:46Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20571",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20571#issuecomment-297365",
"user": "https://github.com/videlec"
}Description changed:
---
+++
@@ -1 +1,19 @@
We can use Newton method to compute n-th root of polynomials. In all (?) cases, this should be much more efficient than relying on factorisation.
+
+An example of a x4 faster compared to factorization
+
+```
+sage: p = x**14 + x**3 - 12
+
+sage: q = p**13
+sage: %timeit _ = nth_root(q, 13)
+1000 loops, best of 3: 216 µs per loop
+sage: %timeit _ = q.factor()
+1000 loops, best of 3: 895 µs per loop
+
+sage: q = p**37
+sage: %timeit _ = nth_root(q, 37)
+1000 loops, best of 3: 625 µs per loop
+sage: %timeit _ = q.factor()
+100 loops, best of 3: 3.92 ms per loop
+```archive/issue_comments_297366.json:
{
"body": "Description changed:\n``````diff\n--- \n+++ \n@@ -1,6 +1,6 @@\n We can use Newton method to compute n-th root of polynomials. In all (?) cases, this should be much more efficient than relying on factorisation.\n \n-An example of a x4 faster compared to factorization\n+Much faster than factorization\n \n ```\n sage: p = x**14 + x**3 - 12\n``````\n",
"created_at": "2016-05-08T02:17:08Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20571",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20571#issuecomment-297366",
"user": "https://github.com/videlec"
}Description changed:
---
+++
@@ -1,6 +1,6 @@
We can use Newton method to compute n-th root of polynomials. In all (?) cases, this should be much more efficient than relying on factorisation.
-An example of a x4 faster compared to factorization
+Much faster than factorization
```
sage: p = x**14 + x**3 - 12archive/issue_comments_297367.json:
{
"body": "<div id=\"comment:4\" align=\"right\">comment:4</div>\n\nWe need to do something else when the characteristic divides n.\n\n```\nsage: R.<x>=GF(5)[]\nsage: nth_root((x+1)^5,5)\nZeroDivisionError: Inverse does not exist.\n```\nTaking a p-th root (with p the characteristic) is easy, though: all exponents that occur need to be a multiple of p and we simply divide them by p. Similarly, we take a p-th root of all coefficients.",
"created_at": "2016-05-08T05:22:01Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20571",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20571#issuecomment-297367",
"user": "https://github.com/nbruin"
}comment:4
We need to do something else when the characteristic divides n.
sage: R.<x>=GF(5)[]
sage: nth_root((x+1)^5,5)
ZeroDivisionError: Inverse does not exist.
Taking a p-th root (with p the characteristic) is easy, though: all exponents that occur need to be a multiple of p and we simply divide them by p. Similarly, we take a p-th root of all coefficients.
archive/issue_comments_297368.json:
{
"body": "Attachment: **[poly_nth_root.py.gz](https://github.com/sagemath/sage/files/ticket20571/poly_nth_root.py.gz)**",
"created_at": "2016-05-08T23:47:40Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20571",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20571#issuecomment-297368",
"user": "https://github.com/videlec"
}Attachment: poly_nth_root.py.gz
archive/issue_comments_297369.json:
{
"body": "<div id=\"comment:5\" align=\"right\">comment:5</div>\n\nIndeed! Thanks for having a look. I added some random tests in positive characteristic as well (and they pass).",
"created_at": "2016-05-08T23:48:31Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20571",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20571#issuecomment-297369",
"user": "https://github.com/videlec"
}comment:5
Indeed! Thanks for having a look. I added some random tests in positive characteristic as well (and they pass).
archive/issue_events_287269.json:
{
"actor": "https://github.com/videlec",
"created_at": "2016-05-24T01:04:06Z",
"event": "labeled",
"issue": "https://github.com/sagemath/sage/issues/20571",
"label": "https://github.com/sagemath/sage/labels/needs%20review",
"label_color": "7fff00",
"label_name": "needs review",
"label_text_color": "ffffff",
"type": "issue_event",
"url": "https://github.com/sagemath/sage/issues/20571#event-287269"
}archive/issue_events_287270.json:
{
"actor": "https://github.com/videlec",
"created_at": "2016-05-24T01:04:06Z",
"event": "demilestoned",
"issue": "https://github.com/sagemath/sage/issues/20571",
"milestone_number": null,
"milestone_title": "sage-7.2",
"type": "issue_event",
"url": "https://github.com/sagemath/sage/issues/20571#event-287270"
}archive/issue_events_287271.json:
{
"actor": "https://github.com/videlec",
"created_at": "2016-05-24T01:04:06Z",
"event": "milestoned",
"issue": "https://github.com/sagemath/sage/issues/20571",
"milestone_number": null,
"milestone_title": "sage-7.3",
"type": "issue_event",
"url": "https://github.com/sagemath/sage/issues/20571#event-287271"
}archive/issue_comments_297370.json:
{
"body": "Commit: **[`530a563`](https://github.com/sagemath/sagetrac-mirror/commit/530a5639eb44d9f6feccb1b4d382ca356faf3146)**",
"created_at": "2016-05-24T01:04:06Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20571",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20571#issuecomment-297370",
"user": "https://github.com/videlec"
}Commit: 530a563
archive/issue_comments_297371.json:
{
"body": "Changed dependencies from **#20086** to none",
"created_at": "2016-05-24T01:04:06Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20571",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20571#issuecomment-297371",
"user": "https://github.com/videlec"
}Changed dependencies from #20086 to none
archive/issue_comments_297372.json:
{
"body": "<div id=\"comment:6\" align=\"right\">comment:6</div>\n\nAll right. Ready for review!\n\n---\nNew commits:\n<table><tr><td><a href=\"https://github.com/sagemath/sagetrac-mirror/commit/530a5639eb44d9f6feccb1b4d382ca356faf3146\"><code>530a563</code></a></td><td><code>Trac 20571: polynomial nth_root via Newton method</code></td></tr></table>\n",
"created_at": "2016-05-24T01:04:06Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20571",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20571#issuecomment-297372",
"user": "https://github.com/videlec"
}comment:6
All right. Ready for review!
New commits:
530a563 | Trac 20571: polynomial nth_root via Newton method |
archive/issue_comments_297373.json:
{
"body": "Branch: **[u/vdelecroix/20571](https://github.com/sagemath/sagetrac-mirror/tree/u/vdelecroix/20571)**",
"created_at": "2016-05-24T01:04:06Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20571",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20571#issuecomment-297373",
"user": "https://github.com/videlec"
}Branch: u/vdelecroix/20571
archive/issue_comments_297374.json:
{
"body": "Description changed:\n``````diff\n--- \n+++ \n@@ -1,19 +1,34 @@\n-We can use Newton method to compute n-th root of polynomials. In all (?) cases, this should be much more efficient than relying on factorisation.\n+We can use Newton method to compute n-th root of polynomials.\n \n-Much faster than factorization\n+It is faster than factorization even over ZZ where factor is highly optimized:\n \n ```\n+sage: x = polygen(ZZ)\n sage: p = x**14 + x**3 - 12\n \n sage: q = p**13\n-sage: %timeit _ = nth_root(q, 13)\n-1000 loops, best of 3: 216 \u00b5s per loop\n+sage: %timeit _ = q.nth_root(13)\n+1000 loops, best of 3: 416 \u00b5s per loop\n sage: %timeit _ = q.factor()\n 1000 loops, best of 3: 895 \u00b5s per loop\n \n sage: q = p**37\n-sage: %timeit _ = nth_root(q, 37)\n-1000 loops, best of 3: 625 \u00b5s per loop\n+sage: %timeit _ = q.nth_root(37)\n+1000 loops, best of 3: 1.17 \u00b5s per loop\n sage: %timeit _ = q.factor()\n 100 loops, best of 3: 3.92 ms per loop\n ```\n+And the Newton method also works over polynomial when factorization is not implemented\n+\n+```\n+sage: R1.<x> = QQ[]\n+sage: R2.<y> = R1[]\n+sage: R3.<z> = R2[]\n+sage: q = (x+y+z)**3\n+sage: q.factor()\n+Traceback (most recent call last):\n+...\n+NotImplementedError: \n+sage: q.nth_root(3)\n+z + y + x\n+```\n``````\n",
"created_at": "2016-05-24T01:10:37Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20571",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20571#issuecomment-297374",
"user": "https://github.com/videlec"
}Description changed:
---
+++
@@ -1,19 +1,34 @@
-We can use Newton method to compute n-th root of polynomials. In all (?) cases, this should be much more efficient than relying on factorisation.
+We can use Newton method to compute n-th root of polynomials.
-Much faster than factorization
+It is faster than factorization even over ZZ where factor is highly optimized:
```
+sage: x = polygen(ZZ)
sage: p = x**14 + x**3 - 12
sage: q = p**13
-sage: %timeit _ = nth_root(q, 13)
-1000 loops, best of 3: 216 µs per loop
+sage: %timeit _ = q.nth_root(13)
+1000 loops, best of 3: 416 µs per loop
sage: %timeit _ = q.factor()
1000 loops, best of 3: 895 µs per loop
sage: q = p**37
-sage: %timeit _ = nth_root(q, 37)
-1000 loops, best of 3: 625 µs per loop
+sage: %timeit _ = q.nth_root(37)
+1000 loops, best of 3: 1.17 µs per loop
sage: %timeit _ = q.factor()
100 loops, best of 3: 3.92 ms per loop
```
+And the Newton method also works over polynomial when factorization is not implemented
+
+```
+sage: R1.<x> = QQ[]
+sage: R2.<y> = R1[]
+sage: R3.<z> = R2[]
+sage: q = (x+y+z)**3
+sage: q.factor()
+Traceback (most recent call last):
+...
+NotImplementedError:
+sage: q.nth_root(3)
+z + y + x
+```archive/issue_comments_297375.json:
{
"body": "Description changed:\n``````diff\n--- \n+++ \n@@ -1,4 +1,4 @@\n-We can use Newton method to compute n-th root of polynomials.\n+In #20086 a `nth_root` method for polynomial was implemented using factorization. But we can use Newton method for that!\n \n It is faster than factorization even over ZZ where factor is highly optimized:\n \n``````\n",
"created_at": "2016-05-24T02:00:06Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20571",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20571#issuecomment-297375",
"user": "https://github.com/videlec"
}Description changed:
---
+++
@@ -1,4 +1,4 @@
-We can use Newton method to compute n-th root of polynomials.
+In #20086 a `nth_root` method for polynomial was implemented using factorization. But we can use Newton method for that!
It is faster than factorization even over ZZ where factor is highly optimized:
archive/issue_comments_297376.json:
{
"body": "Changed commit from **[`530a563`](https://github.com/sagemath/sagetrac-mirror/commit/530a5639eb44d9f6feccb1b4d382ca356faf3146)** to **[`f1996ab`](https://github.com/sagemath/sagetrac-mirror/commit/f1996ab8f035d548bec7d2e518da0081ab211b29)**",
"created_at": "2016-05-24T14:56:10Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20571",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20571#issuecomment-297376",
"user": "https://github.com/sagetrac-git"
}Changed commit from 530a563 to f1996ab
archive/issue_comments_297377.json:
{
"body": "<div id=\"comment:9\"></div>\n\nBranch pushed to git repo; I updated commit sha1. New commits:\n<table><tr><td><a href=\"https://github.com/sagemath/sagetrac-mirror/commit/f1996ab8f035d548bec7d2e518da0081ab211b29\"><code>f1996ab</code></a></td><td><code>Trac 20571: use m.ordinal_str() and fix doctests</code></td></tr></table>\n",
"created_at": "2016-05-24T14:56:10Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20571",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20571#issuecomment-297377",
"user": "https://github.com/sagetrac-git"
}Branch pushed to git repo; I updated commit sha1. New commits:
f1996ab | Trac 20571: use m.ordinal_str() and fix doctests |
archive/issue_events_287272.json:
{
"actor": "https://github.com/bgrenet",
"created_at": "2016-06-10T16:22:31Z",
"event": "unlabeled",
"issue": "https://github.com/sagemath/sage/issues/20571",
"label": "https://github.com/sagemath/sage/labels/needs%20review",
"label_color": "7fff00",
"label_name": "needs review",
"label_text_color": "ffffff",
"type": "issue_event",
"url": "https://github.com/sagemath/sage/issues/20571#event-287272"
}archive/issue_events_287273.json:
{
"actor": "https://github.com/bgrenet",
"created_at": "2016-06-10T16:22:31Z",
"event": "labeled",
"issue": "https://github.com/sagemath/sage/issues/20571",
"label": "https://github.com/sagemath/sage/labels/needs%20work",
"label_color": "ffff00",
"label_name": "needs work",
"label_text_color": "ffffff",
"type": "issue_event",
"url": "https://github.com/sagemath/sage/issues/20571#event-287273"
}archive/issue_comments_297378.json:
{
"body": "<div id=\"comment:11\" align=\"right\">comment:11</div>\n\nHi Vincent,\n\n1. For the Newton method, your loop ranges over `newton_method_sizes(p.degree()+1)`: if you are computing an `n`-th root, isn't it sufficient to loop up to `p.degree()//n + 1`? It would fasten the case when `p.nth_root(n)` raises an `Exception`.\n\n2. Instead of the following code, you may use `i = self.valuation()`. The code would gain in legibility, and it is slightly faster if I ran my tests correctly:\n\n```python\n i = 1\n while self[i].is_zero():\n i += 1\n```\n\n3. Two typos:\n\n```diff\n This is computed using Newton method in the ring of power series. This\n method works only when the base ring is an integral domain. Morever, for\n polynomial whose coefficient of lower degree is different from 1, the\n- elemehts of the base ring should have a method ``nth_root`` implemented.\n+ elements of the base ring should have a method ``nth_root`` implemented.\n```\n\n```diff\n- # begining of Newton method\n+ # beginning of Newton method\n Sorig = p.parent()\n```",
"created_at": "2016-06-10T16:22:31Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20571",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20571#issuecomment-297378",
"user": "https://github.com/bgrenet"
}comment:11
Hi Vincent,
-
For the Newton method, your loop ranges over
newton_method_sizes(p.degree()+1): if you are computing ann-th root, isn't it sufficient to loop up top.degree()//n + 1? It would fasten the case whenp.nth_root(n)raises anException. -
Instead of the following code, you may use
i = self.valuation(). The code would gain in legibility, and it is slightly faster if I ran my tests correctly:
i = 1
while self[i].is_zero():
i += 1- Two typos:
This is computed using Newton method in the ring of power series. This
method works only when the base ring is an integral domain. Morever, for
polynomial whose coefficient of lower degree is different from 1, the
- elemehts of the base ring should have a method ``nth_root`` implemented.
+ elements of the base ring should have a method ``nth_root`` implemented.- # begining of Newton method
+ # beginning of Newton method
Sorig = p.parent()archive/issue_comments_297379.json:
{
"body": "<div id=\"comment:12\"></div>\n\nBranch pushed to git repo; I updated commit sha1. New commits:\n<table><tr><td><a href=\"https://github.com/sagemath/sagetrac-mirror/commit/24ffc9fca48ab2ce4123ba83cefe5543a11114c8\"><code>24ffc9f</code></a></td><td><code>Trac 20571: review</code></td></tr></table>\n",
"created_at": "2016-06-10T22:31:25Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20571",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20571#issuecomment-297379",
"user": "https://github.com/sagetrac-git"
}Branch pushed to git repo; I updated commit sha1. New commits:
24ffc9f | Trac 20571: review |
archive/issue_comments_297380.json:
{
"body": "Changed commit from **[`f1996ab`](https://github.com/sagemath/sagetrac-mirror/commit/f1996ab8f035d548bec7d2e518da0081ab211b29)** to **[`24ffc9f`](https://github.com/sagemath/sagetrac-mirror/commit/24ffc9fca48ab2ce4123ba83cefe5543a11114c8)**",
"created_at": "2016-06-10T22:31:25Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20571",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20571#issuecomment-297380",
"user": "https://github.com/sagetrac-git"
}Changed commit from f1996ab to 24ffc9f
archive/issue_events_287274.json:
{
"actor": "https://github.com/videlec",
"created_at": "2016-06-10T22:32:39Z",
"event": "unlabeled",
"issue": "https://github.com/sagemath/sage/issues/20571",
"label": "https://github.com/sagemath/sage/labels/needs%20work",
"label_color": "ffff00",
"label_name": "needs work",
"label_text_color": "ffffff",
"type": "issue_event",
"url": "https://github.com/sagemath/sage/issues/20571#event-287274"
}archive/issue_events_287275.json:
{
"actor": "https://github.com/videlec",
"created_at": "2016-06-10T22:32:39Z",
"event": "labeled",
"issue": "https://github.com/sagemath/sage/issues/20571",
"label": "https://github.com/sagemath/sage/labels/needs%20review",
"label_color": "7fff00",
"label_name": "needs review",
"label_text_color": "ffffff",
"type": "issue_event",
"url": "https://github.com/sagemath/sage/issues/20571#event-287275"
}archive/issue_comments_297381.json:
{
"body": "<div id=\"comment:13\" align=\"right\">comment:13</div>\n\nHi Bruno,\n\nThanks for having a look. I implemented your suggestions.\n\nVincent",
"created_at": "2016-06-10T22:32:39Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20571",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20571#issuecomment-297381",
"user": "https://github.com/videlec"
}comment:13
Hi Bruno,
Thanks for having a look. I implemented your suggestions.
Vincent
archive/issue_comments_297382.json:
{
"body": "<div id=\"comment:14\" align=\"right\">comment:14</div>\n\nLooks good to me!",
"created_at": "2016-06-13T15:36:43Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20571",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20571#issuecomment-297382",
"user": "https://github.com/bgrenet"
}comment:14
Looks good to me!
archive/issue_comments_297383.json:
{
"body": "Reviewer: **Bruno Grenet**",
"created_at": "2016-06-13T15:36:43Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20571",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20571#issuecomment-297383",
"user": "https://github.com/bgrenet"
}Reviewer: Bruno Grenet
archive/issue_events_287276.json:
{
"actor": "https://github.com/bgrenet",
"created_at": "2016-06-13T15:36:43Z",
"event": "unlabeled",
"issue": "https://github.com/sagemath/sage/issues/20571",
"label": "https://github.com/sagemath/sage/labels/needs%20review",
"label_color": "7fff00",
"label_name": "needs review",
"label_text_color": "ffffff",
"type": "issue_event",
"url": "https://github.com/sagemath/sage/issues/20571#event-287276"
}archive/issue_events_287277.json:
{
"actor": "https://github.com/bgrenet",
"created_at": "2016-06-13T15:36:43Z",
"event": "labeled",
"issue": "https://github.com/sagemath/sage/issues/20571",
"label": "https://github.com/sagemath/sage/labels/positive%20review",
"label_color": "dfffc0",
"label_name": "positive review",
"label_text_color": "ffffff",
"type": "issue_event",
"url": "https://github.com/sagemath/sage/issues/20571#event-287277"
}archive/issue_events_287278.json:
{
"actor": "https://github.com/vbraun",
"created_at": "2016-06-14T07:10:26Z",
"event": "unlabeled",
"issue": "https://github.com/sagemath/sage/issues/20571",
"label": "https://github.com/sagemath/sage/labels/positive%20review",
"label_color": "dfffc0",
"label_name": "positive review",
"label_text_color": "ffffff",
"type": "issue_event",
"url": "https://github.com/sagemath/sage/issues/20571#event-287278"
}archive/issue_events_287279.json:
{
"actor": "https://github.com/vbraun",
"commit_id": "18025e03dfa53e33c343de694851e7661c209b69",
"commit_repository": "https://github.com/sagemath/sage",
"created_at": "2016-06-14T07:10:26Z",
"event": "closed",
"issue": "https://github.com/sagemath/sage/issues/20571",
"type": "issue_event",
"url": "https://github.com/sagemath/sage/issues/20571#event-287279"
}archive/issue_comments_297384.json:
{
"body": "Changed branch from **[u/vdelecroix/20571](https://github.com/sagemath/sagetrac-mirror/tree/u/vdelecroix/20571)** to **[`24ffc9f`](https://github.com/sagemath/sagetrac-mirror/commit/24ffc9fca48ab2ce4123ba83cefe5543a11114c8)**",
"created_at": "2016-06-14T07:10:26Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20571",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20571#issuecomment-297384",
"user": "https://github.com/vbraun"
}Changed branch from u/vdelecroix/20571 to 24ffc9f