[achille]

thanks for sharing that, it was simple, neat, elegant.

this sent me down a rabbit hole -- I asked a few models to solve that same problem, then followed up with a request to optimize it so it runs more efficiently.

chatgpt & gemini's solutions were buggy, but claude solved it, and actually found a solution that is even more efficient. It only needs to compute sqrt once per iteration. It's more complex however.

                   yours  claude
  ------------------------------
  Time (ns/call)    40.5   38.3
  sqrt per iter        3      1
  Accuracy        4.8e-7 4.8e-7

Claude's trick: instead of calling sin/cos each iteration, it rotates the existing (cos,sin) pair by the small Newton step and renormalizes:

  // Rotate (c,s) by angle dt, then renormalize to unit circle
  float nc = c + dt*s, ns = s - dt*c;
  float len = sqrt(nc*nc + ns*ns);
  c = nc/len; s = ns/len;

See: https://gist.github.com/achille/d1eadf82aa54056b9ded7706e8f5...

p.s: it seems like Gemini has disabled the ability to share chats can anyone else confirm this?

[0xfaded]

Thanks for pushing this, I've never gone beyond "zero" shotting the prompt (is it still called zero shot with search?)

As a curiosity, it looks like r and q are only ever used as r/q, and therefore a sqrt could be saved by computing rq = sqrt((rxrx + ryry) / (qxqx + qyqy)). The if q < 1e-10 is also perhaps not necessary, since this would imply that the ellipse is degenerate. My method won't work in that case anyway.

For the other sqrt, maybe try std::hypot

Finally, for your test set, could you had some highly eccentric cases such as a=1 and b=100

Thanks for the investigation:)

Edit: BTW, the sin/cos renormalize trick is the same as what tx,ty are doing. It was pointed out to me by another SO member. My original implementation used trig functions

[achille]

Nice, that worked. It's even faster.

                 yours  yours+opt  claude
  ---------------------------------------
  Time (ns)        40.9      36.4    38.7
  sqrt/iter           3         2       1
  Instructions      207       187     241

Edit: it looks like the claude algorithm fails at high eccentricities. Gave chatgpt pro more context and it worked for 30min and only made marginal improvement on yours, by doing 2 steps then taking a third local step.

https://gist.github.com/achille/23680e9100db87565a8e67038797...