Todd Lehman
Reputation
Top tag
Next privilege 250 Rep.
 Nov 9 awarded Commentator Nov 9 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] There are an infinite number of ellipses that pass through B and C here with center A. The question is to find the one ellipse that passes through B and C, where B and C lie on the axes of the ellipse. Oct 4 awarded Notable Question Jul 2 revised Notation for indexing the factorizations of a number? edited tags Jul 1 asked Notation for indexing the factorizations of a number? Feb 27 comment Finding the cube root of a number using integer arithmetic only? Marc, I like this approach. By the way, arbitrary-length integers are not needed if the a^3>n and n/a^2 subexpressions are rewritten. For example, in C, the loop can be written as: while (a>n/a/a) a=(2*a+n/a/a)/3; to avoid overflow of fixed-length integers. 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