-1
$\begingroup$

What is an algorithm to calculate $\lfloor n\phi \rfloor$ given some integer $n$, where $\phi$ is the golden ratio?

I am thinking the easiest way will involve calculating multiples of its continued fraction representation, since the golden ratio has a simple representation as a continued fraction ($[1;1,1,1,\dots]$) and it is easy to find the floor of a continued fraction (it is just the integer part of the fraction). However, I do not know how to calculate multiples of a continued fraction.

Also, by algorithm, I mean that it could be efficiently implemented on a computer. The algorithm may use arbitrary-precision integer arithmetic. It should not, however, be sensitive to rounding errors if floating arithmetic is used (I would prefer to avoid floats entirely). Pseudocode would be great, but if you do not include it, that is fine.

$\endgroup$
  • 1
    $\begingroup$ This is A000201 on OEIS. $\endgroup$ – lulu Mar 20 at 13:57
  • $\begingroup$ @lulu good link. One thing to note though is that only covers the positive integers. $\endgroup$ – PyRulez Mar 20 at 14:36
  • $\begingroup$ What's the order of $n$ ? $\endgroup$ – Yves Daoust Mar 20 at 15:06
  • $\begingroup$ @YvesDaoust you mean the number of bits? $O(\log n)$ $\endgroup$ – PyRulez Mar 20 at 16:05
  • $\begingroup$ @PyRulez: are you kidding me ? $\endgroup$ – Yves Daoust Mar 20 at 16:12
1
$\begingroup$

The golden ratio satisfies $\phi^2-\phi-1=0$, so $n\phi$ is the positive solution to $x^2-nx-n^2=0$. You can use standard numerical methods (bisection, if you're in a hurry coding-wise, but you could save running time by starting with approximate Newton-Raphson until the deltas get small) to bracket the root between two neighboring integers.

$\endgroup$
  • $\begingroup$ Why the positive solution? $\endgroup$ – PyRulez Mar 20 at 14:35
  • $\begingroup$ @PyRulez: Because the negative solution is $n(1-\phi)$. $\endgroup$ – Henning Makholm Mar 20 at 14:36
  • $\begingroup$ wouldn't that be positive if $n$ is negative? $\endgroup$ – PyRulez Mar 20 at 14:36
  • 1
    $\begingroup$ @PyRulez: I'm assuming that $n$ is positive. For negative multiples, you can use $$\lfloor (-n)\phi\rfloor = -\lfloor n\phi\rfloor -1 \qquad(n\ge 1),$$ since $n\phi$ is never an integer. $\endgroup$ – Henning Makholm Mar 20 at 14:38
  • $\begingroup$ I quickly whipped up a python script implementing this. Hitting "run" executes a demonstration. (Backup in case repl.it goes down.) Feel free to link or copy it into the answer if you think that would add to it. $\endgroup$ – PyRulez Mar 20 at 17:42
0
$\begingroup$

The Golden ratio can be approximated with arbitrary precision as the ratio of two consecutive Fibonacci numbers. These are easy to compute incrementally. Then compute and round

$$\left[n\frac{F_{k+1}}{F_k}\right].$$

It is even possible to compute $nF_k$ simultaneously to $F_k$. So the total cost is $2k$ additions and one division.

$\endgroup$
  • $\begingroup$ What value is $k$? $\endgroup$ – PyRulez Mar 20 at 14:02
  • $\begingroup$ Unfriendly downvote. $\endgroup$ – Yves Daoust Mar 20 at 14:24
  • $\begingroup$ @PyRulez Such that the error on $\phi$ is smaller than $1/n$. $\endgroup$ – Yves Daoust Mar 20 at 14:25
  • $\begingroup$ @HenningMakholm: obviously. The iterates are alternatively by default and by excess, so the sign is predictable. $\endgroup$ – Yves Daoust Mar 20 at 14:35
  • 1
    $\begingroup$ @PyRulez: You can estimate the error in Yves's approximation using $F_n=\frac{\phi^n+(-1)^{n+1}\phi^{-n}}{\sqrt 5}$. You will find that choosing $k$ as some constant times $\log n$ will make the error less than $1$. Thus doing Yves' computation for this $k$ as well as $k+1$ will either tell you the final result immediately, or an integer $a$ such that $a<n\phi<a+2$. In the latter case, use my polynomial once to compare $a+1$ to $n\phi$, and you're done. $\endgroup$ – Henning Makholm Mar 20 at 15:18

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.