As I was trying to speeden my

Perl6 bitcoin library, I realized something that is worth mentionning, imho.

In the elliptic curve arithmetics library, the implementation of "mult" is kind of weird and tough to understand. Here is the relevant part in Python:

def __mul__( self, other ):

"""Multiply a point by an integer."""

def leftmost_bit( x ):

assert x > 0

result = 1L

while result <= x: result = 2 * result

return result // 2

e = other

if self.__order: e = e % self.__order

if e == 0: return INFINITY

if self == INFINITY: return INFINITY

assert e > 0

# From X9.62 D.3.2:

e3 = 3 * e

negative_self = Point( self.__curve, self.__x, -self.__y, self.__order )

i = leftmost_bit( e3 ) // 2

result = self

# print "Multiplying %s by %d (e3 = %d):" % ( self, other, e3 )

while i > 1:

result = result.double()

if ( e3 & i ) != 0 and ( e & i ) == 0: result = result + self

if ( e3 & i ) == 0 and ( e & i ) != 0: result = result + negative_self

# print ". . . i = %d, result = %s" % ( i, result )

i = i // 2

return result

Well, I don't know about you, but to me, this is ugly.

I love recursive functions, so whenever I think I can write one, I think hard about how to actually do it.

It appeared to me that this one is a good candidate. Here is what I'd do:

def __mul__( self, other ):

"""Multiply a point by an integer."""

e = other

if self.__order: e = e % self.__order

if e == 0: return INFINITY

if self == INFINITY: return INFINITY

assert e > 0

if e == 1: return self

if e == 2: return self.double

assert e > 2

if e%2 == 0: return (e/2 * self).double

return self + (e/2 * self).double

Well, I didn't try this particular one because I don't like python, but the same idea worked fine with my perl implementation for instance:

sub mult {

no warnings qw(recursion);

my $k = shift;

my $u = shift;

return

$k == 1 ? $u :

$k == 2 ? double $u :

$k%2 == 0 ? double mult $k/2, $u :

add $u, double mult $k/2, $u

;

}

To me it's kind of cool.