Using double-and-add one multiplication with n requires O(log(n)) additions. I don't think there are more efficient methods.

Adding another bit to the r-values to determine the points on the curve would be a very elegant solution, something to consider if it provides a significant improvement.