27 views

Skip to first unread message

Jun 18, 2020, 11:12:30 AM6/18/20

to flint-devel, nemo-devel

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

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

Jun 18, 2020, 7:40:49 PM6/18/20

to flint-devel, nemo-devel

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.

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.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu