in reply to Re: Re (tilly) 1: Fast Multiplication
in thread Fast Multiplication

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.)

Replies are listed 'Best First'.
Re: Re (tilly) 3: Fast Multiplication
by zencrypt (Novice) on Jan 13, 2001 at 10:36 UTC
    You meant mult2 is slower, as in O($b), right? cause thats what i thought.. The original algorithm shown i believe runs @
    O(log2 $b). As you said, there are certain occasions when multiplication is not so slow, such as times 0, 1, or 2. Thats pretty much the pattern i found for this algorithm. I noticed, (this was originally in C, mind you, and was purely conjtectural) hey, instead of multiplying by 2, i can just shift the bits 1 to the left, to multiply by 4, just shift 2 bits to the left, etc.. i just noticed that using bitwise manipulators, i could use that speed of multiplying by powers of 2 (2n, shift n to the left), which are very fast operations, so that i would have to add numbers much less than with the latter subroutine. anyway, i have the feeling i'm beating a dead horse here, so i think i'll leave it at that for now :)
[reply]
[d/l]

In Section Cool Uses for Perl