Calcium update

[Fredrik Johansson]

Hi all,

I'm making some progress with Calcium. Arithmetic operations are now implemented for the ca_t type (http://fredrikj.net/calcium/ca.html). There's no test code yet, so the code is by definition broken, but I can at least present the first (highly artificial) benchmark of field arithmetic!

The benchmark: compute A = sqrt(1) + sqrt(2) + ... + sqrt(N), compute B = 1/sqrt(1) + 1/sqrt(2) + ... + 1/sqrt(N), compute C = ((A^2-B^2)/(A+B) + B) / A, and verify that C = 1.

Timings (seconds) for Sage's QQbar, Sage's SymbolicRing (SR), and Calcium ca_t:

N / Sage QQbar / Sage SR / Calcium ca_t
2 / 0.0095 / 0.0012 / 0.000015
5 / 0.047 / 0.0020 / 0.00025
10 / 0.26 / 0.035 / 0.00056
12 / 11.3 / 0.039 / 0.00070
15 / 178 / 0.051 / 0.0011
20 / - / 0.069 / 0.00152
50 / - / 0.256 / 0.0102
100 / - / 8.74 / 0.0731

(Note: for SR, I need to call .simplify_full() on the result to trigger a computation.)

This example is admittedly not all that interesting. Currently, when working in Q(x1,...,xn) with algebraic number extension elements x1,...,xn, Calcium will automatically reduce by the minimal polynomial for each element, but it does not yet handle relations between the extension elements. It will thus give (sqrt(2)*sqrt(3))^2 = 6, but it is not yet able to detect that sqrt(2)*sqrt(3) = sqrt(6). Performing such simplifications automatically will slow down this particular benchmark, but it will be vital in other situations.

There's a lot of work left to do on the internals before Calcium is ready for public use. For example, the context object currently hangs on to all created fields until it is destroyed (and it uses linear search to find cached fields). This is fine if you create a context object locally and don't do something that constructs thousands of extension elements, but it's not going to be good enough for working with a long-lived Calcium ring.

Fredrik

[Bill Hart]

The timings look really impressive. Great work! I am sure we'll have
lots of applications for this going forward.

Bill.

> --
>
> ---
> You received this message because you are subscribed to the Google Groups "flint-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to flint-devel...@googlegroups.com.
> To view this discussion on the web, visit https://groups.google.com/d/msgid/flint-devel/CAJdUXT%2B_NJK8C%2BOrZawZZdHgEN8a72x%3D24V%2BbR4dORgUnOBhxQ%40mail.gmail.com.