Todd Lehman
Reputation
Top tag
Next privilege 250 Rep.
 Apr6 revised Is there a standard notation for the sequence of sorted exponents in the prime power factorization of a number? deleted 7 characters in body; edited title Apr5 asked Is there a standard notation for the sequence of sorted exponents in the prime power factorization of a number? Feb27 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. Sep9 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? Sep9 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? Sep9 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. Sep9 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!!! Aug3 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. Jan26 awarded Popular Question Nov29 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. Feb11 answered What is the pair $(n,k)$ called where $n$ is an integer and $k$ is the ordered factorization index? Feb9 asked What is the pair $(n,k)$ called where $n$ is an integer and $k$ is the ordered factorization index? Sep30 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. Sep30 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 Sep30 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 Sep29 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. Sep29 awarded Student Sep29 awarded Editor Sep29 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 Sep29 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]