Calcium 0.1

September 8, 2020

This post will be is a short announcement of Calcium, a new project I've been working on since April. The code is still highly experimental, but I have tagged version 0.1 to solicit feedback sooner rather than later.

Briefly, Calcium is a C library for computing exactly with real and complex numbers. This means not only being being able to evaluate numbers to arbitrary precision, but being able to solve problems requiring exact comparisons. In Calcium, $(\pi + 1) - 1 = \pi$ exactly. You can think of it as a computer algebra system limited to constant values, or as something like Sage's exact field of algebraic numbers but faster (at least for certain things) and with support for transcendental numbers too.

Calcium builds on Arb (for arbitrary-precision ball arithmetic), Flint (for rational numbers and multivariate polynomial arithmetic) and Antic (for arithmetic in algebraic number fields). The basic idea behind Calcium is to represent numbers as elements of formal fields $\mathbb{Q}(a_1,\ldots,a_n)$ where the extension numbers $a_k$ can be algebraic or transcendental. Simplifications are handled through the field arithmetic together with ideal reduction. This is reasonably fast even for huge expressions thanks to Flint and Antic. Algebraic relations between extension numbers are discovered automatically using LLL and proved through symbolic tests and recursive field computations. The field constructions are managed automatically by the system so that numbers (the Calcium ca_t type) are very easy to use.

To get a better idea of what Calcium can do, the example programs are a good place to start. Here are some examples of expressions that Calcium automatically evaluates to a simple form:

$$\frac{\varphi^{100} - (1-\varphi)^{100}}{\sqrt{5}} \; \rightarrow \; 354224848179261915075$$ $$i^i - e^{-\pi/2} \; \rightarrow \; 0$$ $$\frac{\log(1 + \sqrt{2})}{\log(3 + 2 \sqrt{2})} \; \rightarrow \; \frac{1}{2}$$ $$12 \operatorname{atan}\left(\frac{1}{49}\right) + 32\operatorname{atan}\left(\frac{1}{57}\right) -5 \operatorname{atan}\left(\frac{1}{239}\right) + 12 \operatorname{atan}\left(\frac{1}{110443}\right) - \frac{\pi}{4} \; \rightarrow \; 0$$

Another nice example is constructing Swinnerton-Dyer polynomials $$S_n = \prod (x \pm \sqrt{2} \pm \sqrt{3} \pm \sqrt{5} \pm \ldots \pm \sqrt{p_n}),$$ for example $$S_3 = (x+\sqrt{2}+\sqrt{3}+\sqrt{5})(x+\sqrt{2}+\sqrt{3}-\sqrt{5})\cdots(x-\sqrt{2}-\sqrt{3}-\sqrt{5}) = x^8 - 40x^6 + 352x^4 - 960x^2 + 576.$$ With Calcium, you can just construct the list of roots and multiply out the polynomial. The $n = 10$ polynomial which has degree 1024 and 800-digit coefficients takes 10 seconds to compute. It can be done faster with Arb, but 10 seconds is not bad for a symbolic solution requiring no cleverness at all on the part of the user.

Yet another nice benchmark problem comes from a Sage help request posted recently, in which a user asked for a way to prove equality of two algebraic numbers defined by huge (7000 arithmetic operations) formulas. This takes forever with Sage's QQbar unless the user makes some manipulations to put the input in a better form. Calcium solves the problem in the original form in 8 minutes, and in only 25 seconds if one uses Calcium's internal algebraic number type (qqbar_t) instead of the general-purpose Calcium number type ca_t (it should be possible to fix this discrepancy: on this test problem, the ca_t type is slow partly for entirely stupid reasons).

Right now, Calcium's performance is all over the place. Some things are extremely fast, other things are absurdly slow. Many simplifications don't work, either because the algorithms are not implemented, or because they would be too expensive to apply automatically. Calcium is already reasonably good at determining whether expressions involving logarithms are equal; it knows much less about powers and exponentials and things like real and imaginary parts of numbers. Calcium can always decide equality of algebraic numbers, but merely evaluating an expression does not automatically produce a fully simplified form. For example, $$\sqrt{5 + 2 \sqrt{6}} - \sqrt{2} - \sqrt{3}$$ does not automatically evaluate to zero (but Calcium will prove that it equals zero when prompted through ca_check_is_zero). Should this expression evaluate to zero automatically? Arguably, yes, but then there will be a line to draw somewhere else. I'm going to explore the cost-benefit tradeoffs for expensive simplifications further in the future (hopefully, there will be tricks so that even "expensive" simplifications become practical).

Calcium is in some ways an outgrowth of the Python library for symbolic expressions which I started developing last year as part of Fungrim, though it is motivated by other applications as well. It turns out that much of the complexity when manipulating symbolic expressions over the complex numbers is in actually manipulating constant values, so it seemed like a good idea to write a library specifically for this. At first, I considered developing Calcium as a Python library or a Julia library, but after some thought I decided that it was going to be doable in plain C.

There is a long list of things left to do before Calcium can be considered production-ready. This will probably keep me occupied for several months. There will hopefully be time for other projects too :-)

fredrikj.net | Blog index | RSS feed | Follow me on Mastodon | Become a sponsor