fredrikj.net / blog /

# 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