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.
