RE: erroneous claim at sources.redhat.com/gsl/ref/gsl-ref_4.html# SEC3 2

[keith dot briggs at bt dot com]

There is a section discussing this problem in quite a lot of detail in
Knuth's Seminumerical Algorithms.
Keith

	Dr. Keith M. Briggs
	Senior Mathematician, Complexity Research, BT Exact
	http://research.btexact.com/teralab/keithbriggs.html
	phone: +44(0)1473  work: 641 911 home: 610 517  fax: 642 161
      mail: Keith Briggs, Polaris 134, Adastral Park, Martlesham, Suffolk
IP5 3RE, UK


-----Original Message-----
From: Achim Gädke [mailto:Achim.Gaedke@physik.tu-darmstadt.de]
Sent: 15 July 2003 13:22
To: jimmy mcguire; gsl-discuss@sources.redhat.com
Subject: Re: erroneous claim at
sources.redhat.com/gsl/ref/gsl-ref_4.html# SEC3 2


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:
>