In this paper we present efficient algorithms to take advantage of the double-base number system in the context of elliptic curve scalar multiplication. We propose a generalized version of Yao’s exponentiation algorithm allowing the use of general double-base expansions instead of the popular double base chains. We introduce a class of constrained double base expansions and prove that the average density of non-zero terms in such expansions is $O(\frac{\log\, k}{\log\, \log\, k})$<alternatives> <inline-graphic xlink:type="simple" xlink:href="meloni-ieq1-2360539.gif"/></alternatives> for any large integer $k$<alternatives><inline-graphic xlink:type="simple" xlink:href="meloni-ieq2-2360539.gif"/> </alternatives>. We also propose an efficient algorithm for computing constrained expansions and finally provide a comprehensive comparison to double-base chain expansions, including a large variety of curve shapes and various key sizes.