Real Close to the Machine: Floating Point in D

[Lars T. Kyllingstad]

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

Thanks, I'll keep that in mind. At one point I had to use several levels 
because I kept interfaces and implementations in the same modules, and 
the source files quickly became very large. Now that I've put the 
implementations in scid.ports, using one level is a lot more manageable.

Whether I choose to use one or two levels, the idea is to mimic the 
structure of the GAMS classification tree.

-Lars