[Maxima-discuss] GMP or Flint

[Oscar B. <osc...@gm...>]

There are a couple of threads on the list discussing the use of GMP
within Maxima based on the fact that some Lisps have GMP already
provided. I wondered if anyone had considered the use of Flint which
is a C library that builds and improves on GMP and provides vastly
more that could be relevant to Maxima.

The Flint website is here:
https://www.flintlib.org/

A more detailed list of features can be found in the docs:
https://www.flintlib.org/doc/

The Flint library provides the same integers and rationals as gmpy but
also much more like polynomials and matrices over those types and
likewise for modular integers. I think that the next release will also
contain Arb which is a superior version of interval arithmetic as well
as Calcium which implements semi-decidable algorithms over
transcendental numbers as well as decidable algorithms over algebraic
numbers.

Here are a couple of demonstrations of using flint from Python via the
python_flint wrapper module (note that this wrapper is incomplete and
misses many features of the underlying Flint library).

Factor a high degree polynomial. This is not a fast computer but we
can factorise a polynomial of degree 4000 in 0.2 seconds:

In [3]: from flint import *

In [4]: p = fmpz_poly([1, 1, 1, 1, 1])

In [5]: p
Out[5]: x^4 + x^3 + x^2 + x + 1

In [6]: p2 = p**1000

In [7]: p2.degree()
Out[7]: 4000

In [8]: %time p2.factor()
CPU times: user 170 ms, sys: 16.1 ms, total: 186 ms
Wall time: 185 ms
Out[8]: (1, [(x^4 + x^3 + x^2 + x + 1, 1000)])

Obviously the exact time taken depends on what sort of polynomial you
pass in. The algorithms in Flint are good though and their
implementation is well-optimised going beyond what can be achieved
with straight-forward portable C code.

With Arb we can also have efficient interval arithmetic for algebraic
and transcendental functions:

In [11]: arb(2).sqrt()
Out[11]: [1.41421356237309 +/- 5.15e-15]

In [12]: ctx.dps = 1000

In [13]: arb(2).sqrt()
Out[13]: [1.414213562373095048801688724209698078569671875376948073176679737990732478462107038850387534327641572735013846230912297024924836055850737212644121497099935831413222665927505592755799950501152782060571470109559971605970274534596862014728517418640889198609552329230484308714321450839762603627995251407989687253396546331808829640620615258352395054745750287759961729835575220337531857011354374603408498847160386899970699004815030544027790316454247823068492936918621580578463111596668713013015618568987237235288509264861249497715421833420428568606014682472077143585487415565706967765372022648544701585880162075847492265722600208558446652145839889394437092659180031138824646815708263010059485870400318648034219489727829064104507263688131373985525611732204024509122770022694112757362728049573810896750401836986836845072579936472906076299694138047565482372899718032680247442062926912485905218100445984215059112024944134172853147810580360337107730918286931471017111168391658172688941975871658215212822951848847
+/- 2.32e-1000]

Note the +/- on these: it is a hard bound on the true result of the
calculation. You can have matrices and polynomials of arb and its
complex variant acb and do linear algebra etc while maintaining hard
bounds.

There is a lot more there than I have time right now to list but the
Flint library is really designed to provide a core of efficient
implementations of the low-level pieces needed in a CAS. I am
currently working on making it so that SymPy can leverage Flint (via
python_flint). It is also used in many other systems listed on the
website.

--
Oscar