Real Close to the Machine: Floating Point in D

[Don]

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.