This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH] Another tweak to the multiplication algorithm
- From: "Joseph S. Myers" <joseph at codesourcery dot com>
- To: Siddhesh Poyarekar <siddhesh at redhat dot com>
- Cc: <libc-alpha at sourceware dot org>
- Date: Wed, 13 Feb 2013 17:57:54 +0000
- Subject: Re: [PATCH] Another tweak to the multiplication algorithm
- References: <20130213142137.GU15748@spoyarek.pnq.redhat.com>
On Wed, 13 Feb 2013, Siddhesh Poyarekar wrote:
> Hi,
>
> This is a second tweak to the mpa multiplication algorithm, which is
> based on the Karatsuba algorithm[1]. This reduces multiplication
> instructions in favour of additions and halves the number of
> iterations required in calculating a single mantissa digit. Joseph
The point of Karatsuba is not achieving a factor-2 reduction, but using
recursion to reduce the time required for multiplying numbers of 2^n
digits (n large enough for this to be worthwhile) from 4^n to 3^n. I
don't see obvious recursion here....
--
Joseph S. Myers
joseph@codesourcery.com