Real Close to the Machine: Floating Point in D

[Don]

Lars T. Kyllingstad wrote:
> 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:
> 
> scid.core:
>     Internal modules, such as scid.core.traits, scid.core.tests,
>     scid.core.exception, etc.
> 
> scid.ports:
>     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.
> 
> scid:
>     In the root package I've placed the most ubiquitous modules,
>     i.e. scid.vector, scid.transformation, etc.
> 
> scid.calculus
>     scid.calculus.differentiation
>     scid.calculus.integration
>     ...
> scid.linalg
>     ...
> scid.nonlinear
>     ...
>     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.

That sounds about right. But you might even consider dropping it down 
one level. For example, everyone knows that differentiation is 
calculus.differentiation; I think you only need a level when the module 
name is ambiguous on its own. (std.integration might be about Product 
Integration or something; but math.integration is unambiguous).

The tango.math heirarchy only has a single level.
module tango.math.Module;
(and internal stuff is in tango.math.internal.Implementation)
Interestingly, when people have complained about Tango's heirarchy, 
they've always excluded tango.math from the complaints. I suspect that 
means that two levels is about right (and btw it's interesting to note 
that biologists use genus.species -- two levels again).

I'm no expert on this, though.

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

The scope of Phobos really needs to be decided sometime. I think it 
either needs to expand significantly, or else some existing code needs 
to be removed (is std.xml actually fundamental?)

If Phobos were to be small, then Tango would make a lot of sense as a 
standard collection of add-on functionality. That's not the only 
possibility, but it is something that needs to be decided.

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

Thanks! It made a lot of things clearer for me, too <g>.

Don