From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 21112 invoked by alias); 15 Jul 2003 12:22:31 -0000 Mailing-List: contact gsl-discuss-help@sources.redhat.com; run by ezmlm Precedence: bulk List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gsl-discuss-owner@sources.redhat.com Received: (qmail 21104 invoked from network); 15 Jul 2003 12:22:30 -0000 Received: from unknown (HELO element.fkp.physik.tu-darmstadt.de) (130.83.32.197) by sources.redhat.com with SMTP; 15 Jul 2003 12:22:30 -0000 Received: from dilbert.fkp.physik.tu-darmstadt.de (element.fkp.physik.tu-darmstadt.de [130.83.32.197]) by element.fkp.physik.tu-darmstadt.de (Postfix on SuSE Linux 7.3 (i386)) with ESMTP id 017F828324; Tue, 15 Jul 2003 14:23:32 +0200 (CEST) Received: from physik.tu-darmstadt.de (localhost [127.0.0.1]) by dilbert.fkp.physik.tu-darmstadt.de (Postfix) with ESMTP id 416554F20; Tue, 15 Jul 2003 14:22:27 +0200 (CEST) Message-ID: <3F13F202.3070109@physik.tu-darmstadt.de> Date: Tue, 15 Jul 2003 12:22:00 -0000 From: =?ISO-8859-1?Q?Achim_G=E4dke?= User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.0.2) Gecko/20030623 X-Accept-Language: en-us, en, de MIME-Version: 1.0 To: jimmy mcguire , gsl-discuss@sources.redhat.com Subject: Re: erroneous claim at sources.redhat.com/gsl/ref/gsl-ref_4.html# SEC3 2 References: <0AAF93247C75E3408638B965DEE11A700101020B@i2km41-ukdy.nat.bt.com> <3F13CFF6.3010304@physik.tu-darmstadt.de> <3F13EE30.6030800@mail.ualr.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 8bit X-SW-Source: 2003-q3/txt/msg00054.txt.bz2 Yes, this is quite true, that I do not really know, what's the optimal way. 1) In order to fix a documentation bug, we should correct the manual. 2) Here we multiply numbers (plain floating point numbers), so the effort to do the optimum should be not to large: approx. O(2*log_2(n)) is not bad in contrast to O(n). 3) If it is cheap to find a better way or if we deal with matrices (e.g. in characteristic polynoms), we may want to find out a better way to split this multiplication. Finding prime factors is quite expensive. For 21 I avoid one multiplication, but what about the costs? 4) I like this problem, because it's simple to explain and becomes difficult when solving it. :-) Achim jimmy mcguire wrote: > Breaking my usual rule against speaking proir to knowing for sure, how > about use the powers of two approach if the destination exponent is a > power of two or if it is prime, otherwise the break the destination > exponent into prime addends and construct multiplicative factors > corresponding to the prime additive exponents. Repeat (recurse) as > necessary. > > Achim Gädke wrote: > >> so, is there anyone outside, knowing similar problems? >> >> I agree, repeated squaring is likely to be the best solution, because >> the binary representation can be obtained easily on a computer. >> So the manual should state, that this algorithm is efficient and in >> most cases the fastest. >> >> Achim >> >> keith.briggs@bt.com wrote: >