Title: Recursive version of the elliptic curve multiplication algorithm Post by: grondilu on June 06, 2012, 08:49:29 AM As I was trying to speeden my Perl6 bitcoin library (https://bitcointalk.org/index.php?topic=61207.0), 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: Code: def __mul__( self, other ): 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: Code:
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: Code: sub mult { To me it's kind of cool. Title: Re: Recursive version of the elliptic curve multiplication algorithm Post by: grondilu on June 06, 2012, 09:20:43 AM To me it's kind of cool. Recursion is cool on paper. In the real world, unless you have a compiler smart enough to handle tail recursions properly it's dog slow. But then again, it's Perl and Python, so who cares about speed in the first place. The Perl6 developpers are working hard on dealing with tail recursion (I think it's done already in rakudo). I guess the Python team is concerned about that too. Also, the maximum amount of recursive call here is 256. That sure is a lot but it is capped so it should be fine I guess. Title: Re: Recursive version of the elliptic curve multiplication algorithm Post by: realnowhereman on June 06, 2012, 09:25:40 AM It's an interesting exercise, but since all recursion can be converted to iteration (and vice versa), and iteration tends not to have any stack problems, you're almost always better converting your recursive algorithm to iterative (plus compilers are much better at unrolling iterative loops for optimisation purposes).
(Note: I haven't studied your code well enough to know whether this is one of the cases outside the "almost always", but I'd be surprised if it weren't) Title: Re: Recursive version of the elliptic curve multiplication algorithm Post by: grondilu on June 08, 2012, 01:59:42 PM I finally wrote a non-recursive, yet much simpler code:
Code: sub mult { To me it is much better than messing aroung with binary shift operators. |