Real Close to the Machine: Floating Point in D

Lars T. Kyllingstad public at kyllingen.NOSPAMnet
Thu May 14 08:04:31 PDT 2009

Don wrote:
> 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.

In my numerics library (which I've, in all modesty, named SciD) I'm 
converging on a package structure I'm fairly pleased with:

     Internal modules, such as scid.core.traits, scid.core.tests,
     scid.core.exception, etc.

     Here I put ports of various packages from NETLIB and other
     sources. Examples of subpackages are scid.minpack,
     scid.quadpack, etc. These have, for the most part, rather
     nasty APIs, and should normally not be used directly.

     In the root package I've placed the most ubiquitous modules,
     i.e. scid.vector, scid.transformation, etc.

     Specific problem areas get their own subpackages. At the moment
     these mostly just contain nicer interfaces to the routines in
     scid.ports -- "drivers", if you will.

I've tried a lot of setups, and this is the one I've found most 
flexible. The hierarchy isn't as shallow (and inextensible) as Phobos', 
nor is it as deep (and unwieldly) as Tango's.

I can definitely see how having a flat module hierarchy may prohibit the 
expansion of Phobos. I'm not at all convinced this is a bad thing, though.

I really liked your FP article, by the way. It made things a lot clearer 
  for me. :)


More information about the Digitalmars-d mailing list