archive/issues_020519.json:
{
"assignees": [],
"body": "<div id=\"comment:0\"></div>\n\n\n```\nsage: x = polygen(ZZ)\nsage: K.<a> = NumberField(x^100 - 3, embedding=AA(3)**(1/100))\nsage: %time sign(a)\nCPU times: user 1.34 s, sys: 0 ns, total: 1.34 s\nWall time: 1.33 s\n1\nsage: b = continued_fraction(a).convergent(20) - a\nsage: sign(b)\nsgn(-1/1495877943276*(1/4)^(1/5)*(-(sqrt(5) - I*sqrt(-2*sqrt(5) + 10) + 1)*(-3^(1/4))^(1/5))^(1/5)*(373969485819*sqrt(5) - 373969485819*I*sqrt(-2*sqrt(5) + 10) + 373969485819) + 378100611523/373969485819)\n```\nWith the branch applied\n\n```\nsage: %time sign(a)\nCPU times: user 4 ms, sys: 0 ns, total: 4 ms\nWall time: 4.65 ms\n1\nsage: b = continued_fraction(a).convergent(20) - a\nsage: %time sign(b)\nCPU times: user 4 ms, sys: 0 ns, total: 4 ms\nWall time: 6.02 ms\n-1\n```\n\nCC: @jdemeyer @pjbruin\n\nComponent: **number fields**\n\nKeywords: **days74**\n\nAuthor: **Vincent Delecroix**\n\nBranch/Commit: **[`31e8874`](https://github.com/sagemath/sagetrac-mirror/commit/31e8874e03c35a6e1f9f0076d8fe7f2937d0177b)**\n\nReviewer: **Marc Mezzarobba**\n\n_Issue created by migration from https://trac.sagemath.org/ticket/20756_\n\n",
"closed_at": "2016-06-15T18:47:34Z",
"created_at": "2016-06-02T05:57:27Z",
"labels": [
"https://github.com/sagemath/sage/labels/c%3A%20number%20fields",
"https://github.com/sagemath/sage/labels/p%3A%20major%20/%203",
"https://github.com/sagemath/sage/labels/bug"
],
"milestone": "https://github.com/sagemath/sage/milestones/sage-7.3",
"reactions": [],
"repository": "https://github.com/sagemath/sage",
"title": "sign is slow (if not wrong) for number field elements",
"type": "issue",
"updated_at": "2016-06-15T18:47:34Z",
"url": "https://github.com/sagemath/sage/issues/20756",
"user": "https://github.com/videlec"
}sage: x = polygen(ZZ)
sage: K.<a> = NumberField(x^100 - 3, embedding=AA(3)**(1/100))
sage: %time sign(a)
CPU times: user 1.34 s, sys: 0 ns, total: 1.34 s
Wall time: 1.33 s
1
sage: b = continued_fraction(a).convergent(20) - a
sage: sign(b)
sgn(-1/1495877943276*(1/4)^(1/5)*(-(sqrt(5) - I*sqrt(-2*sqrt(5) + 10) + 1)*(-3^(1/4))^(1/5))^(1/5)*(373969485819*sqrt(5) - 373969485819*I*sqrt(-2*sqrt(5) + 10) + 373969485819) + 378100611523/373969485819)
With the branch applied
sage: %time sign(a)
CPU times: user 4 ms, sys: 0 ns, total: 4 ms
Wall time: 4.65 ms
1
sage: b = continued_fraction(a).convergent(20) - a
sage: %time sign(b)
CPU times: user 4 ms, sys: 0 ns, total: 4 ms
Wall time: 6.02 ms
-1
CC: @jdemeyer @pjbruin
Component: number fields
Keywords: days74
Author: Vincent Delecroix
Branch/Commit: 31e8874
Reviewer: Marc Mezzarobba
Issue created by migration from https://trac.sagemath.org/ticket/20756
archive/issue_events_289655.json:
{
"actor": "https://github.com/videlec",
"created_at": "2016-06-02T05:57:27Z",
"event": "milestoned",
"issue": "https://github.com/sagemath/sage/issues/20756",
"milestone_number": null,
"milestone_title": "sage-7.3",
"type": "issue_event",
"url": "https://github.com/sagemath/sage/issues/20756#event-289655"
}archive/issue_events_289656.json:
{
"actor": "https://github.com/videlec",
"created_at": "2016-06-02T05:57:27Z",
"event": "labeled",
"issue": "https://github.com/sagemath/sage/issues/20756",
"label": "https://github.com/sagemath/sage/labels/c%3A%20number%20fields",
"label_color": "0000ff",
"label_name": "c: number fields",
"label_text_color": "ffffff",
"type": "issue_event",
"url": "https://github.com/sagemath/sage/issues/20756#event-289656"
}archive/issue_events_289657.json:
{
"actor": "https://github.com/videlec",
"created_at": "2016-06-02T05:57:27Z",
"event": "labeled",
"issue": "https://github.com/sagemath/sage/issues/20756",
"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/20756#event-289657"
}archive/issue_events_289658.json:
{
"actor": "https://github.com/videlec",
"created_at": "2016-06-02T05:57:27Z",
"event": "labeled",
"issue": "https://github.com/sagemath/sage/issues/20756",
"label": "https://github.com/sagemath/sage/labels/bug",
"label_color": "d73a4a",
"label_name": "bug",
"label_text_color": "ffffff",
"type": "issue_event",
"url": "https://github.com/sagemath/sage/issues/20756#event-289658"
}archive/issue_comments_300918.json:
{
"body": "Branch: **[u/vdelecroix/20756](https://github.com/sagemath/sagetrac-mirror/tree/u/vdelecroix/20756)**",
"created_at": "2016-06-02T07:40:07Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20756",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20756#issuecomment-300918",
"user": "https://github.com/videlec"
}Branch: u/vdelecroix/20756
archive/issue_events_289659.json:
{
"actor": "https://github.com/videlec",
"created_at": "2016-06-02T07:40:07Z",
"event": "labeled",
"issue": "https://github.com/sagemath/sage/issues/20756",
"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/20756#event-289659"
}archive/issue_comments_300919.json:
{
"body": "<div id=\"comment:1\"></div>\n\nNew commits:\n<table><tr><td><a href=\"https://github.com/sagemath/sagetrac-mirror/commit/31e8874e03c35a6e1f9f0076d8fe7f2937d0177b\"><code>31e8874</code></a></td><td><code>Trac 20756: fix sign for algebraic numbers</code></td></tr></table>\n",
"created_at": "2016-06-02T07:40:07Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20756",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20756#issuecomment-300919",
"user": "https://github.com/videlec"
}New commits:
31e8874 | Trac 20756: fix sign for algebraic numbers |
archive/issue_comments_300920.json:
{
"body": "Commit: **[`31e8874`](https://github.com/sagemath/sagetrac-mirror/commit/31e8874e03c35a6e1f9f0076d8fe7f2937d0177b)**",
"created_at": "2016-06-02T07:40:07Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20756",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20756#issuecomment-300920",
"user": "https://github.com/videlec"
}Commit: 31e8874
archive/issue_comments_300921.json:
{
"body": "Description changed:\n``````diff\n--- \n+++ \n@@ -1,18 +1,25 @@\n \n ```\n-sage: R.<x> = ZZ[]\n-sage: p = R.random_element(degree=20) + x**21\n-sage: r = p.roots(AA, False)\n-sage: K.<a> = NumberField(p, embedding=r[0])\n+sage: x = polygen(ZZ)\n+sage: K.<a> = NumberField(x^100 - 3, embedding=AA(3)**(1/100))\n sage: %time sign(a)\n CPU times: user 1.34 s, sys: 0 ns, total: 1.34 s\n Wall time: 1.33 s\n--1\n+1\n sage: b = continued_fraction(a).convergent(20) - a\n sage: sign(b)\n-sgn(3^(1/100) - 179093512558/177136737587)\n+sgn(-1/1495877943276*(1/4)^(1/5)*(-(sqrt(5) - I*sqrt(-2*sqrt(5) + 10) + 1)*(-3^(1/4))^(1/5))^(1/5)*(373969485819*sqrt(5) - 373969485819*I*sqrt(-2*sqrt(5) + 10) + 373969485819) + 378100611523/373969485819)\n+```\n+With the branch applied\n+\n+```\n+sage: %time sign(a)\n+CPU times: user 4 ms, sys: 0 ns, total: 4 ms\n+Wall time: 4.65 ms\n+1\n+sage: b = continued_fraction(a).convergent(20) - a\n sage: %time sign(b)\n-CPU times: user 8.35 s, sys: 20 ms, total: 8.37 s\n-Wall time: 8.32 s\n-sgn(3^(1/100) - 179093512558/177136737587)\n+CPU times: user 4 ms, sys: 0 ns, total: 4 ms\n+Wall time: 6.02 ms\n+-1\n ```\n``````\n",
"created_at": "2016-06-02T07:44:38Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20756",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20756#issuecomment-300921",
"user": "https://github.com/videlec"
}Description changed:
---
+++
@@ -1,18 +1,25 @@
```
-sage: R.<x> = ZZ[]
-sage: p = R.random_element(degree=20) + x**21
-sage: r = p.roots(AA, False)
-sage: K.<a> = NumberField(p, embedding=r[0])
+sage: x = polygen(ZZ)
+sage: K.<a> = NumberField(x^100 - 3, embedding=AA(3)**(1/100))
sage: %time sign(a)
CPU times: user 1.34 s, sys: 0 ns, total: 1.34 s
Wall time: 1.33 s
--1
+1
sage: b = continued_fraction(a).convergent(20) - a
sage: sign(b)
-sgn(3^(1/100) - 179093512558/177136737587)
+sgn(-1/1495877943276*(1/4)^(1/5)*(-(sqrt(5) - I*sqrt(-2*sqrt(5) + 10) + 1)*(-3^(1/4))^(1/5))^(1/5)*(373969485819*sqrt(5) - 373969485819*I*sqrt(-2*sqrt(5) + 10) + 373969485819) + 378100611523/373969485819)
+```
+With the branch applied
+
+```
+sage: %time sign(a)
+CPU times: user 4 ms, sys: 0 ns, total: 4 ms
+Wall time: 4.65 ms
+1
+sage: b = continued_fraction(a).convergent(20) - a
sage: %time sign(b)
-CPU times: user 8.35 s, sys: 20 ms, total: 8.37 s
-Wall time: 8.32 s
-sgn(3^(1/100) - 179093512558/177136737587)
+CPU times: user 4 ms, sys: 0 ns, total: 4 ms
+Wall time: 6.02 ms
+-1
```archive/issue_comments_300922.json:
{
"body": "<div id=\"comment:3\" align=\"right\">comment:3</div>\n\nHi Vincent,\n\nPositive review conditional on the patchbot. But note that using `RealBallField` instead of `RealIntervalField` would likely be faster. For example, with the `b` from the ticket's description, we have:\n\n```\nsage: %timeit RIF(b)\n1000 loops, best of 3: 916 \u00b5s per loop\nsage: %timeit RBF(b)\n1000 loops, best of 3: 312 \u00b5s per loop\n```\n\n```\nsage: %timeit(RealIntervalField(200)(b))\nThe slowest run took 23.70 times longer than the fastest. This could mean that an intermediate result is being cached.\n1000 loops, best of 3: 1.29 ms per loop\nsage: %timeit(RealBallField(200)(b))\nThe slowest run took 5.32 times longer than the fastest. This could mean that an intermediate result is being cached.\n1000 loops, best of 3: 514 \u00b5s per loop\n```",
"created_at": "2016-06-02T09:18:30Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20756",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20756#issuecomment-300922",
"user": "https://github.com/mezzarobba"
}comment:3
Hi Vincent,
Positive review conditional on the patchbot. But note that using RealBallField instead of RealIntervalField would likely be faster. For example, with the b from the ticket's description, we have:
sage: %timeit RIF(b)
1000 loops, best of 3: 916 µs per loop
sage: %timeit RBF(b)
1000 loops, best of 3: 312 µs per loop
sage: %timeit(RealIntervalField(200)(b))
The slowest run took 23.70 times longer than the fastest. This could mean that an intermediate result is being cached.
1000 loops, best of 3: 1.29 ms per loop
sage: %timeit(RealBallField(200)(b))
The slowest run took 5.32 times longer than the fastest. This could mean that an intermediate result is being cached.
1000 loops, best of 3: 514 µs per loop
archive/issue_comments_300923.json:
{
"body": "<div id=\"comment:4\" align=\"right\">comment:4</div>\n\nHo nice! I guess we should move *all* from intervals to balls... I would prefer doing it all at once.",
"created_at": "2016-06-02T09:38:40Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20756",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20756#issuecomment-300923",
"user": "https://github.com/videlec"
}comment:4
Ho nice! I guess we should move all from intervals to balls... I would prefer doing it all at once.
archive/issue_comments_300924.json:
{
"body": "<div id=\"comment:5\" align=\"right\">comment:5</div>\n\nReplying to [@videlec](#comment%3A4):\n> Ho nice! I guess we should move *all* from intervals to balls...\n\nEventually yes. But to be honest, I don't really understand why balls are that much faster in this case, since the conversion from number field elements to balls is optimized in the quadratic case only at this point, and (I think) uses MPFI intervals internally otherwise.\n\n> I would prefer doing it all at once.\n\nYour choice! Yet it could be less effort to do it in new code before trying to change existing code.",
"created_at": "2016-06-02T10:33:33Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20756",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20756#issuecomment-300924",
"user": "https://github.com/mezzarobba"
}comment:5
Replying to @videlec:
Ho nice! I guess we should move all from intervals to balls...
Eventually yes. But to be honest, I don't really understand why balls are that much faster in this case, since the conversion from number field elements to balls is optimized in the quadratic case only at this point, and (I think) uses MPFI intervals internally otherwise.
I would prefer doing it all at once.
Your choice! Yet it could be less effort to do it in new code before trying to change existing code.
archive/issue_comments_300925.json:
{
"body": "<div id=\"comment:6\" align=\"right\">comment:6</div>\n\nIndeed, moving to balls need serious benchmarks. And doing it all at once make sense since we will go deeply into the two possible conversions, possibly improving them.\n\nSo this one stay in needs review as it is. Is that good for you (pathchbot is happy)?",
"created_at": "2016-06-13T18:29:57Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20756",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20756#issuecomment-300925",
"user": "https://github.com/videlec"
}comment:6
Indeed, moving to balls need serious benchmarks. And doing it all at once make sense since we will go deeply into the two possible conversions, possibly improving them.
So this one stay in needs review as it is. Is that good for you (pathchbot is happy)?
archive/issue_comments_300926.json:
{
"body": "Reviewer: **Marc Mezzarobba**",
"created_at": "2016-06-14T08:17:19Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20756",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20756#issuecomment-300926",
"user": "https://github.com/mezzarobba"
}Reviewer: Marc Mezzarobba
archive/issue_events_289660.json:
{
"actor": "https://github.com/mezzarobba",
"created_at": "2016-06-14T08:17:19Z",
"event": "unlabeled",
"issue": "https://github.com/sagemath/sage/issues/20756",
"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/20756#event-289660"
}archive/issue_events_289661.json:
{
"actor": "https://github.com/mezzarobba",
"created_at": "2016-06-14T08:17:19Z",
"event": "labeled",
"issue": "https://github.com/sagemath/sage/issues/20756",
"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/20756#event-289661"
}archive/issue_comments_300927.json:
{
"body": "<div id=\"comment:7\" align=\"right\">comment:7</div>\n\nReplying to [@videlec](#comment%3A6):\n> So this one stay in needs review as it is. Is that good for you (pathchbot is happy)?\n\nYes, what I wrote about balls was just a side remark.",
"created_at": "2016-06-14T08:17:19Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20756",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20756#issuecomment-300927",
"user": "https://github.com/mezzarobba"
}comment:7
Replying to @videlec:
So this one stay in needs review as it is. Is that good for you (pathchbot is happy)?
Yes, what I wrote about balls was just a side remark.
archive/issue_events_289662.json:
{
"actor": "https://github.com/vbraun",
"created_at": "2016-06-15T18:47:34Z",
"event": "unlabeled",
"issue": "https://github.com/sagemath/sage/issues/20756",
"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/20756#event-289662"
}archive/issue_events_289663.json:
{
"actor": "https://github.com/vbraun",
"commit_id": "167fc8d9e39041eb103b4ac89c1a8c9c72be2fd4",
"commit_repository": "https://github.com/sagemath/sage",
"created_at": "2016-06-15T18:47:34Z",
"event": "closed",
"issue": "https://github.com/sagemath/sage/issues/20756",
"type": "issue_event",
"url": "https://github.com/sagemath/sage/issues/20756#event-289663"
}archive/issue_comments_300928.json:
{
"body": "Changed branch from **[u/vdelecroix/20756](https://github.com/sagemath/sagetrac-mirror/tree/u/vdelecroix/20756)** to **[`31e8874`](https://github.com/sagemath/sagetrac-mirror/commit/31e8874e03c35a6e1f9f0076d8fe7f2937d0177b)**",
"created_at": "2016-06-15T18:47:34Z",
"formatter": "markdown",
"issue": "https://github.com/sagemath/sage/issues/20756",
"type": "issue_comment",
"url": "https://github.com/sagemath/sage/issues/20756#issuecomment-300928",
"user": "https://github.com/vbraun"
}Changed branch from u/vdelecroix/20756 to 31e8874