The computational performance of cryptographic protocols based on elliptic curves strongly depends on the efficiency of multi scalar multiplications of uP + vQ, where P and Q are points on an elliptic curve. An efficient way to compute uP + vQ is to compute two scalar multiplications simultaneously, rather than computing each scalar multiplications separately. Koblitz introduced a family of curves which admit especially fast elliptic multi scalar multiplication and Solinas brought forward an improved algorithm for kP using the τ-expansion of Koblitz Curves. We give a new algorithm for uP +vQ on Koblitz Curves based on the τ-expansion with the additional speedup of the new joint spare form, which is called τ-NJSF, where P and Q are on an Koblitz Curve defined over F2m. We also present an efficient algorithm to obtain the τ-NJSF and prove its average joint Hamming density (AJHD) is 27/56 via the method of stochastic process. Computing uP +vQ by our algorithm can reduce the computational complexity in more than 95% cases, and the running time is reduced by 3.6% on average, while compared with computation that by using τ-JSF.