Not to detract from the main point, but if you were implementing this multiplication yourself, using the "powers of two" ladder is a bad idea for security reasons. Specifically, for each 1 bit in your secret key you're adding 2^i*G, while for each 0 bit you're not doing anything. Somebody timing your algorithm could easily determine how many powers of 2 you added, i.e. how many bits in your secret key are 1.

In general, you want to use a multiplication algorithm that never puts secret data into if-conditionals [1] or into array indices [2][3]. It is possible to efficiently do this, which I think is actually even more surprising than the fact that you can do the multiplication in sublinear time.

One such algorithm, though by no means the most efficient one, is as follows (a special case of [4], unless I screwed it up):

1. Compute x' = (x + 2^256 - 1)/2 mod the secp256k1 curve order. The bits of this number have a special property: if you interpret all the 0's as -1's, they also represent the original secret key x. See [5], top of page 9.
2. Compute G, -G, 2G, -2G, 4G, -4G, ..., 2^256G, -2^256G and put them in an array P.
3. Compute the sum of { x_i'*P[2*i + 1] + (1 - x_i')*P[2*i] } over each bit x'_i of x'.

[1] "Don't branch on secret data" is folklore, I don't have a citation for it.
[2] https://cryptojedi.org/peter/data/chesrump-20130822.pdf
[3] http://www.tau.ac.il/~tromer/papers/cache.pdf
[4] https://github.com/bitcoin-core/secp256k1/pull/546
[5] https://eprint.iacr.org/2012/309.pdf