Re: Announcing the Moore library for interval arithmetic
On 29.11.2016 11:06, Walter Mascarenhas wrote:
> Dear all,
>
> I finally found the time to complete an interval arithmetic
> library in which I have been working for some time (by
> completing I mean having the code, a manual and
> about 1000 tests)
>
> This message contains a copy of the manual and an
> article about the library. You can obtain the code by
> sending me an email message (I would like to estimate
> the size of the set of people which would ever look
> at it, to know if it is not empty for instance)
>
> The library is open source, and I will send you
> the source code.
Hi Walter,
thanks for sending me the source code. Regarding your article on p. 1,
“the other reference implementation is implemented in Octave and is not
comparable to our library”.
I'd like to say: “Challenge accepted” ;-)
I have migrated your benchmarks into Octave code (attached). Evaluation
of the Lebesgue function is pretty slow because of the interpreter
overhead (on the other hand you don't have to wait while your code
compiles). In my example I use only 20000 points for “t” and it already
takes more than five seconds.
Evaluation speed of Newton's method seems to be somewhere between P1788
and Filib.
Regarding elementary functions the Octave package currently is in the
league of P1788 and your library, because we mainly measure runtimes of
MPFR. However, I have integrated the crlibm library for the upcoming
version. Now, computation times for elementary functions are almost in
the league of Filib, better than Boost, and with tight enclosures of
binary64 precision.
Best
Oliver
Output of the Octave script on my Notebook (with crlibm used for
elementary functions):
--8<-----------------------------------------------
Lebesgue function 5.40116 sec
Newton's method on polynomials
deg 1 0.0215349 sec
deg 2 0.878694 sec
deg 3 0.99651 sec
deg 4 2.21467 sec
deg 5 2.08057 sec
deg 6 3.72349 sec
deg 7 5.37517 sec
deg 8 4.81427 sec
deg 9 7.88394 sec
deg 10 7.12032 sec
Elementary Functions
sin 0.278104 sec
cos 0.289208 sec
tan 0.21759 sec
asin 0.140792 sec
acos 0.143261 sec
atan 0.160316 sec
exp 0.0642691 sec
log 0.0479481 sec
pkg load interval
#########################################
function y = lebesgue (w, x, t)
diff = t - x;
den = 0;
num = 0;
for i = 1 : rows (w)
q = w(i) ./ diff(i, :);
den += q;
num += abs (q);
endfor
y = num ./ abs (den);
y(any (sup (diff) == 0)) = 1;
endfunction
function [nodes, weights] = chebyshev (degree)
weights = (-1) .^ vec (0 : degree);
weights([1 end]) *= 0.5;
nodes = cos (vec (0 : degree) .* pi / degree);
endfunction
dx = 0.0001;
degree = 256;
x = infsup (-1 : dx : 1);
[nodes, weights] = chebyshev (degree);
tic
y = lebesgue (weights, x, nodes);
printf ("Lebesgue function %d sec\n", toc)
printf ("\n")
#########################################
printf ("Newton's method on polynomials\n")
warning ("off", "interval:UndefinedOperation", "local")
initial_domain = infsup ("[-10, 10]");
options = optimset ("MaxIter", 1000000, ...
"TolFun", 1e-6, ...
"TolX", 1e-6);
for degree = 1 : 10
# random coefficients in the range -10 .. +10
p = (rand (1, degree + 1) - .5) * 2 * 10;
# evaluate polynomial using Horner's scheme
f = @(x) polyval (p, x);
# evaluate polynomial's derivative using Horner's
dp = (degree : -1 : 1) .* p(1 : end - 1);
df = @(x) polyval (dp, x);
# interval newton method
tic
fzero (f, initial_domain, df);
printf ("deg %d %d sec\n", degree, toc)
endfor
printf ("\n")
#########################################
printf ("Elementary Functions\n")
A = infsup (rand ([1 1e6]));
tic
sin (A);
printf ("sin %d sec\n", toc)
tic
cos (A);
printf ("cos %d sec\n", toc)
tic
tan (A);
printf ("tan %d sec\n", toc)
tic
asin (A);
printf ("asin %d sec\n", toc)
tic
acos (A);
printf ("acos %d sec\n", toc)
tic
atan (A);
printf ("atan %d sec\n", toc)
tic
exp (A);
printf ("exp %d sec\n", toc)
tic
log (A);
printf ("log %d sec\n", toc)