Finding a sum involving the golden ratio

This is a math oriented algorithms puzzle.

Let $\varphi$ be the golden ratio: $\dfrac{1+\sqrt{5}}{2}$.

Consider the following sum

$$S_n = [\varphi] + [2 \varphi] + \dots + [n\varphi]$$

i.e

$$S_n = \sum_{k=1}^{n} [k \varphi]$$

where $[x]$ is the integer part of $x$.

Can you give an algorithm to compute $S_n$ that takes a polynomial in $\log n$ time?

[Solution]