Writeup about generics

[Fredrik Johansson]

Hi all,

As I promised a while ago, here is a longer writeup about the implementation of generic rings in C (currently a work in progress): https://fredrikj.net/blog/2022/07/generics-in-flint/

Fredrik

[Jeffrey Sarnoff]

Very nice write-up. I am glad to see "This turns out to be wrong." in Interfaces are hard (and I agree fullly).

As the real numbers extended with ±∞ are not a field, is it possible to use a nonspecific very large magnitude which essentially gobbles up or collapses (whichever is mathematically preferable) all magnitudes that exceed the maximum exactly representable real magnitude, e.g. ±huge?

Best,
Jeffrey Sarnoff

--

---
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/CAJdUXTLiFLqE1G7RLqRk8cw076AEja1w1xoyr3ofaBz-Myd7DQ%40mail.gmail.com.

[Fredrik Johansson]

It is possible to have structures that are not fields; they will just explicitly not be fields. The interface already supports creating a base domain of inexact floating-point arithmetic (wrapping arf_t) which supports +/inf and nan.

I even made minimal mpmath backend using these floating-point numbers, which works:

>>> from mpmath2 import *
>>> mp.dps = 100
>>> nsum(lambda n: 1/n**2, [1, inf])
1.64493406684822643647241516664602518921894990120679843773555822937000747040320087383362890061975870530
>>> diff(lambda x: gamma(x), 1)
-0.577215664901532860606512090082402431042159335939923598805767234884867726777664670936947063291746749515
>>> quadosc(lambda x: sin(x)/x, [0, inf], omega=1)
1.57079632679489661923132169163975144209858469968755291048747229615390820314310449931401741267105853399

Later there could be exact/interval based extended reals as well.

Fredrik

To view this discussion on the web, visit https://groups.google.com/d/msgid/flint-devel/CAM96OoKBqD3uAqxSjCWtJuCGqRJ0%3DVcQMb234JbMmjpAYyOYQw%40mail.gmail.com.

[Jeffrey Sarnoff]

This question was raised by a respected Julia contributor:

for n an integer, find the limit as n goes to +infinty of

     2n*log(n) / log2( factorial(n) )

the  related question, find the limit as r goes to +infinity
for r a positive real and factorial(n) replaced with gamma(r+1)
is also of interest.

Any thoughts -- not for this specific problem, rather for the larger class of problems that seem to run out digit memory if approached as calculations.
The values are large enough that intervals would become unhelpful pbly.

To view this discussion on the web, visit https://groups.google.com/d/msgid/flint-devel/CAJdUXTKmumhZ0L3-LZm_rjg3wN7Q6VKb7S96_rDx_oi88To%2BwA%40mail.gmail.com.

[Fredrik Johansson]

On Sun, Jul 24, 2022 at 8:22 AM Jeffrey Sarnoff <jeffrey...@gmail.com> wrote:

This question was raised by a respected Julia contributor:

for n an integer, find the limit as n goes to +infinty of

     2n*log(n) / log2( factorial(n) )

the  related question, find the limit as r goes to +infinity
for r a positive real and factorial(n) replaced with gamma(r+1)
is also of interest.

Any thoughts -- not for this specific problem, rather for the larger class of problems that seem to run out digit memory if approached as calculations.
The values are large enough that intervals would become unhelpful pbly.

There are various ways to calculate this kind of limit numerically, none of which require unusual techniques for dealing with large numbers. With a change of variables n -> exp(n) or n -> 2^n the sequence has at a regular rate for convergence acceleration with Richardson extrapolation, e.g. with mpmath.limit:

>>> f = lambda n: 2*n*log(n)/log(fac(n),2); limit(lambda n: f(exp(n)), inf)
1.386294361119890618834464242916353136151000268720510508241360018986787243939389431211726653992837375
>>> 2*log(2)
1.386294361119890618834464242916353136151000268720510508241360018986787243939389431211726653992837375

log(fac(n)) does get large enough to require bignum exponents here, but you can replace log(factorial(n)) with logamma(n) to avoid that.

In fact, if you replace log(factorial(n)) with logamma(n), you can even evaluate the function directly at a sufficiently large n to get an accurate approximation of the limit:

>>> (lambda n: 2*(n)*log(n)/loggamma(n)*log(2))(exp(10**100))
1.386294361119890618834464242916353136151000268720510508241360018986787243939389431211726653992837375

With that said, some kind of level-index arithmetic could be quite interesting for dealing with asymptotic problems without manual rewriting.

Fredrik