This isn't overly useful, but i think its an interesting way to multiply two integers. For a given function

f(a, b);

the obvious way to multply integers is simply to add a to itself b-1 times. The algorithm below, however, adds a shifted i times to the left if b is odd (b & 0x01 == 1), where i is a number from 0 (beginning) to whatever. After every iteration, shift b to the right, lather, rinse, repeat until no more b. Keep in mind, for all i know, i could be the first person to use this, or this may be common knowledge already. I really don't know. thought i'd post it and see what you all thought.


sub multiply {
        ($a, $b) = @_;
        $i=0; $product=0;

        do {
                $product += ($a << $i) if ($b & 0x01);
                $i++;
        }  while ($b>>=1);

        return $product;
}

[download]

Replies are listed 'Best First'.
Re (tilly) 1: Fast Multiplication
by tilly (Archbishop) on Jan 09, 2001 at 19:56 UTC
    With the overhead of an interpreted language this should be substantially slower than just using Perl's native multiplication.

    Perl isn't C. And trying to outthink the implementation of Perl is almost always a loss. (If you can find cases where you don't lose, then that is a bug in Perl.)

[reply]
      oh i know this, i just think this is an interesting concept. I should have clarified; This would be fast if this is how the processor implemented it. I doubt perl would implement this algorithm so cleanly. Also, i originally wrote something like this up in C.
      I guess the whole point is, i know $a * $b is faster than multiply($a, $b);, but who knows, if i have a subroutine: 

      sub mult2 {
        my($a, $b)  = @_;
        my $product = 0;

        $product += $a while ($b--);

        return $product;
}

      [download]

      mine would be faster for larger numbers.. i think. i could always be wrong, its happened before :) I'll have to use Benchmark; to test it ;)

[reply]
[d/l]
[select]
        That would be slower.

        Much slower.

        In fact I don't need to look at Benchmark to immediately say that your algorithm is O($b), which is slow indeed.

        Multiplication is slower than addition in a chip because general multiplication is a complex operation. That said, multiplication is implemented efficiently. Repeated addition is much, much worse than the general routine except for a small number of exceptions. (eg 0, 1, 2.)

[reply]
Slow Multiplication
by I0 (Priest) on Jan 10, 2001 at 01:55 UTC
[reply]

Back to Cool Uses for Perl