126 reputation
4
bio website
location Boston, MA
age
visits member for 2 years, 11 months
seen Oct 2 at 2:44

Sep
9
comment Efficient way to determine if a number is Perfect Square
Also curious: Your comment with the if (x&6) return -1; statement says "Early escape" — implying an optimization shortcut. But I noticed that if I comment it out, it actually returns incorrect result for numbers like 80, 128, 192, 320, 512, 768, 1280, 2048, etc. So it's not really so much an early-out test, but rather is fundamental and crucial to the algorithm, correct?
Sep
9
comment Efficient way to determine if a number is Perfect Square
By the way, what happens when x==0 on input? My compiler doesn't have __builtin_ctzll(), so instead I did int sh = 0; while (x % 4 == 0) { x /= 4; sh++; } and for the return part did return y << sh. The while loop gets stuck forever if x == 0, so I check that specially before doing anything else. Just curious what happens in your original version using the trailing zero count. Does it right-shift x by 64 and then fall through with x being 0?
Sep
9
comment Efficient way to determine if a number is Perfect Square
Question: From what is this derived? You say it's "2-adic Newton," which I'm not familiar with. I'll go read about it, but in particular I'm wondering why strange things like 3-x, which underflows an unsigned value, and the x&6 != 0 test. It's like magic and I'd like to understand what's really going on under the hood.
Sep
9
comment Efficient way to determine if a number is Perfect Square
This is brilliant! Thank you so much for posting this. On my system, this test is actually 5 times faster than using 80-bit hardware square root, e.g., uint64_t y = (uint64_t)sqrtl((long double)x); bool is_square = (y * y == x); across the whole range from 0 all the way up to 2^64-1. I'm amazed!!!
Aug
3
comment Detecting perfect squares faster than by extracting square root
@CogitoErgoCogitoSum — I think this answer is great!! Obviously it doesn't fully answer the question, but it does provide a wealth of practical information. I don't know who voted you down to –1. I voted you up a notch.
Jan
26
awarded  Popular Question
Nov
29
comment Approximate arc length of cubic bezier curve?
Instead of looking at the sub-segment length, you could look at the curvature of the sub-Bezier and stop recursion when the curvature is below some threshold. A couple simple dot-product operations and square roots are needed to check the cosines of the angles involved.
Feb
11
answered What is the pair $(n,k)$ called where $n$ is an integer and $k$ is the ordered factorization index?
Feb
9
asked What is the pair $(n,k)$ called where $n$ is an integer and $k$ is the ordered factorization index?
Sep
30
comment Passing an ellipse through 3 points (where 2 two points lie on the ellipse axes)? [Updated with alternative statement of problem and new picture]
@RahulNarain — A circle works very nicely when $P_2$ is positioned between $P_1$ and $P_3$, particularly when its close to the $P_1P_3$ line segment. But when $P_2$ is, say, way off to the right or left of $P_3$ and close to collinear with $P_1P_3$, then a circle creates an undesirable tangent that’s almost in a perpendicular direction from what I need. I appreciate the suggestion of trying a circle instead, though! I’m definitely open to possibilities besides ellipses. I was thinking last night that maybe a parabola would work.
Sep
30
revised Passing an ellipse through 3 points (where 2 two points lie on the ellipse axes)? [Updated with alternative statement of problem and new picture]
added 205 characters in body
Sep
30
revised Passing an ellipse through 3 points (where 2 two points lie on the ellipse axes)? [Updated with alternative statement of problem and new picture]
added 1671 characters in body
Sep
29
comment Passing an ellipse through 3 points (where 2 two points lie on the ellipse axes)? [Updated with alternative statement of problem and new picture]
@Hagen — Well, using a line orthogonal to $P_2-M$, where $M = \frac{1}{2}(P_1+P_3)$, is a decent approximation if $P_2$ is far away from $P_3$. But if $P_2$ is close to $P_3$ (that is, much closer to $P_3$ than it is to $P_1$), then it gives disastrously different line than the tangent to the fitted ellipse. So this is why I’m seeking a solution that actually fits an ellipse, rather than a simpler approximation. Although I won’t be fitting my final curve using the ellipse (I use cubic Bézier curves for that), the tangent of the fitted ellipse supplies a beautiful set of Bézier control points.
Sep
29
awarded  Student
Sep
29
awarded  Editor
Sep
29
revised Passing an ellipse through 3 points (where 2 two points lie on the ellipse axes)? [Updated with alternative statement of problem and new picture]
added 24 characters in body
Sep
29
asked Passing an ellipse through 3 points (where 2 two points lie on the ellipse axes)? [Updated with alternative statement of problem and new picture]
Jan
4
awarded  Supporter