Real Close to the Machine: Floating Point in D
Don
nospam at nospam.com
Thu May 14 07:22:27 PDT 2009
Lars T. Kyllingstad wrote:
> Don wrote:
>> Lu’ís Marques wrote:
>>>> A naive binary chop doesn't work correctly. The fact that there are
>>>> hundreds or thousands of times as many representable numbers between
>>>> 0 and 1, as there are between 1 and 2, is problematic for
>>>> divide-and-conquer algorithms. A naive binary chop would divide the
>>>> interval [0 .. 2] into [0 .. 1] and [1 .. 2]. Unfortunately, this is
>>>> not a true binary chop, because the interval [0 .. 1] contains more
>>>> than 99% of the representable numbers from the original interval!
>>>
>>> How about adding a template to do a binary chop (binary search?) to
>>> std.algorithm?
>>
>> findRoot() (which needs to be updated to take advantage of compiler
>> improvements) does the job in the most important case. I'm quite proud
>> of it; as far as I know, it's uses a better algorithm than anything
>> else on the planet. <g>
>
>
> Awesome! I hadn't even noticed the std.numeric module before. :)
>
> Just a small comment: I think that the type of the function parameter
> should be templated as well, so that one can pass both functions,
> delegates and functors to it.
>
> Just now I tried to apply findRoot to an actual problem I'm working on,
> and immediately failed because I tried to pass a free function to it. A
> trivial thing to work around, but annoying nevertheless.
>
> How do you choose/limit what to put in std.numeric? I don't suppose
> you're going to put all of NETLIB in there... ;) Already, it seems to me
> that findRoot is somewhat niche for a standard library.
I think it's one of a very small number of primitive math algorithms. It
shows up _very_ frequently.
In Tango, it's in tango.math.Bracket, along with a 1-D maximizer.
(math.Bracket isn't a name I like very much).
There's definitely an issue with Phobos' flat module organisation; it's
not clear that Phobos can sensibly grow to be much more extensive than
(say) the C standard library or the STL with that kind of structure.
I'm convinced that implementation modules, at least, will need to go
somewhere else.
More information about the Digitalmars-d
mailing list