Re: New and faster algorithm for multiplication


Hans Petter Selasky wrote:
> Hi,
>
> I think I have found a new and faster algorithm for multiplication.
>
> http://home.c2i.net/hselasky/math/multiply.c


As near as I can tell this algorithm is pretty solidly iterative, in
that you have to perform the 32 cycles (assuming 32 bit numbers) one
after the other, so it's O(n). The classical full array multiplier is,
at worst (with just a tree of full width adders), O(lg(n)**2), and
faster with various carry-save schemes.

Perhaps if you wrote some more about the underlying theory of this
algorithm...

.

Relevant Pages

  • Re: off-topic: Why is lisp so weird?
    ... I'm not arguing against finding a better algorithm. ... >> advantage to be had by running in a more efficient environment. ... some languages can optimize code better. ... actually be faster than a faster algorithm in a different language. ...
    (comp.programming)
  • Fast Binary-to-Decimal Conversion Algorithms?
    ... and I'd like a similarly fast algorithm for converting back from decimal ... I've also been informed of what seems to be a faster algorithm by ... It's a way of using an n-bit-to-m-digit ... converter in a 2n-bit-to-2m-digit converter. ...
    (comp.programming)
  • Re: Fast Binary-to-Decimal Conversion Algorithms?
    ... >Without much success, I've been trying to find a 'fast' algorithm for ... >converting large numbers from binary to decimal. ... >and I'd like a similarly fast algorithm for converting back from decimal ... >I've also been informed of what seems to be a faster algorithm by ...
    (comp.programming)
  • Fast Binary-to-Decimal Conversion Algorithms?
    ... and I'd like a similarly fast algorithm for converting back from decimal ... I've also been informed of what seems to be a faster algorithm by ... It's a way of using an n-bit-to-m-digit ... converter in a 2n-bit-to-2m-digit converter. ...
    (comp.theory)
  • Re: New and faster algorithm for multiplication
    ... Proginoskes wrote: ... > Hans Petter Selasky wrote: ... >> I think I have found a new and faster algorithm for multiplication. ... Prev by Date: ...
    (sci.math)