0
$\begingroup$

Euclidean division is an iterative process that has been made super-efficient at the CPU level, right?

Its specification is that if I do (q, r) = f(n, d), I get super efficient result verifying that n = d * q + r with maximal q.

I need to perform a similar decomposition of an integer number, into the highest inferior triangular number and a remainder. In the same terms, this is (i, r) = g(n) verifying that n = i * (i + 1) / 2 + r with maximal i.

What's the way to go? What's the fastest I can get compared to euclidean division?

Improve this question
$\endgroup$
6
  • $\begingroup$ This looks similar to finding the square root. I expect algorithms for these two problems to be very similar in efficiency, since an efficient algorithm for your problem would yield an excellent first guess for the Newton's Method approach to refining square roots. $\endgroup$ – j_random_hacker Nov 8 '20 at 18:51
  • $\begingroup$ Hm, I see what you mean. I'll investigate that, cheers :) $\endgroup$ – iago-lito Nov 8 '20 at 19:25
  • $\begingroup$ In fact for non-negative $n$ the value of $i$ is either $floor(\sqrt{2n})$ or $floor(\sqrt{2n})-1$ if I'm not mistaken. $\endgroup$ – Tassle Nov 8 '20 at 22:27
  • $\begingroup$ $$i = \left \lfloor \sqrt{n + \frac{1}{2}} - \frac{1}{2} \right \rfloor$$ $\endgroup$ – Pseudonym Nov 8 '20 at 23:13
  • $\begingroup$ Are you willing to use floating-point arithmetic so that you can take square roots easily? Then just solve $n \geq \frac{i(i+1)}{2}$ for the largest $i$ possible. Otherwise if you only want to use integer arithmetic, you could use something like binary search to find $i$ quickly (or better perhaps, something like Newton's method). $\endgroup$ – Joppy Nov 9 '20 at 1:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.