fdej

Author here. The table-maker's dilemma is a problem if you insist on correct rounding. However, interval arithmetic does not require correct rounding. It merely requires rigorous error bounds. It turns out that a lot of the time when people ask how to obtain correctly rounded results, they are actually asking the wrong question, and what they really need is just error bounds.

This is why Arb has a lot more functions than MPFR: it's extremely difficult to implement correctly rounded functions as required by MPFR; Arb's contract (returning an error bound) is far easier to satisfy and works just as well 99% of the time.

From a software development point of view, the problem with correct rounding is that it doesn't compose: given correctly rounded functions f and g and correctly rounded input x, f(g(x)) is not (in general) correctly rounded. In interval arithmetic, the corresponding composition law (the inclusion property) does hold; this means that you can compose arbitrarily complicated functions without thinking.

Thanks, it was a temporary mental lapse to forget mentioning Fortran. I have added a sentence.

Nemo (http://nemocas.org/) and Oscar (https://oscar.computeralgebra.de/) are such projects. However, they are focused on algebra and have no support for expression manipulation, symbolic integration and the like.

I think SymPy already flourishes in its space: it's a great tool for users who need some computer algebra functionality with the ability to glue that together with other code (thanks to Python). It's fine as long as you don't need high efficiency or specialized functionality.

Mathematica has no serious competition as a general-purpose symbolic system. I guess Maple is the closest runner-up, but it's more narrowly focused on computer algebra. Most people only need a fraction of Mathematica to get their work done, though.

And then why not: the designer originated through evolution. Which in turn...

Ah, too bad that the sequencer mode is being delayed.

For about 20 years now, I'm still holding my breath for a MIDI sequencer that runs on Linux and has all the functionality and user-friendliness of Cakewalk 3 (http://www.vgmpf.com/Wiki/images/6/63/Player_-_Cakewalk_Prof...).

Sekaiju (https://openmidiproject.osdn.jp/index_en.html) is open source and is 95% there in terms of the user interface, but alas it's Windows only and I'm not aware of any effort to make a Linux port. (Don't suggest Wine, because trying to get MIDI to work with that is a nightmare. A nice thing about the current MuseScore is that MIDI playback works out of the box.)

Do you have a link?

The API itself is perhaps less interesting than the implementation strategy. I'm presently developing a C library for exact real and complex numbers (http://fredrikj.net/calcium/) that goes much further to make equality decidable even in complicated cases while also enabling efficient computations. Still working on implementing functionality and writing up a formal paper.

Sure, go ahead and set something up!

There is nothing in depth yet. I'm happy to discuss (here or by email).

Indeed. I decided not to use MathML for various reasons:

1. The syntax is horrible (for writing by hand).

2. I'm more interested in computation than presentation, so something closer to S-expressions along the lines of Mathematica feels more comfortable to me.

3. The progress so far on defining semantics for content MathML has failed to impress me.

Concretely, I think if you are trying to do semantic mathematics, you need an implementation of the semantics in software, not just a hand-written spec. Ideally this would be backed by a formal theorem proving system. So far I just do randomized testing using symbolic evaluation and interval arithmetic. See this writeup for more details: https://arxiv.org/abs/2003.06181

Nice project! I'm working on something similar with http://fungrim.org/grim/ and http://fungrim.org/

Has anyone tested this with Glenn Gould recordings?

That complexity bound applies to polynomials over more general coefficient rings which may not have roots of unity. Over the usual complex numbers the complexity is O(n log n).

Huh, weird that this is making such big headlines. A fast (O(n log n)) inverse chirp z-transform was described 16 years ago in Alin Bostan's PhD thesis https://specfun.inria.fr/bostan/these/These.pdf

Also in this more compact paper by Bostan and Schost: https://specfun.inria.fr/bostan/publications/BoSc05.pdf

The new algorithm may be a different way to do it (I haven't studied the paper), but the authors ought to have cited previous work. Where does Nature find their referees?

Here's GMP's current tuning (for Skylake CPUs, from https://gmplib.org/devel/thres/)

Basecase: up to 520 digits (27 limbs x 19.26 digits per 64-bit limb = 520)

Karatsuba: 520 - 1425 digits

Toom3: 1425 - 4045 digits

Toom4: 4045 - 6068 digits

Toom6: 6068 - 8053 digits

Toom8: 8053 - 120835 digits

FFT: 120835+ digits

All good remarks.

> The "rewrite engine" ambitions for Fungrim seem potentially misplaced. It would probably be better to contribute to an existing open source state-of-the-art CAS like Fricas

For the record, I have contributed to several existing open source computer algebra systems (not Fricas though). I honestly don't think anyone has found the right foundations for computer algebra systems yet. Nor do I even think that there can necessarily be a "one size fits all solution" that works better than a multitude of specialized systems for different tasks. Fricas gets some things right where others don't, but it has its own weaknesses. I think it's valuable to explore different approaches. This possible future direction for Fungrim is more of a research project, and in any case, I think it's complementary to much of the work that is already being done on other open source computer algebra systems.

Sorry that this is still a bit vague. I have more specific issues in mind, but I don't have time to elaborate in this HN comment. I hope to do a better writeup in the future!

> WTF! Only if one uses Wolfram Alpha exclusively!

Or Maple, or Maxima, or SymPy, or Sage, or... even Fricas. Despite its type system, Fricas has the same problem as the rest with overzealous simplification. One of the very first examples in the Fricas book, "integrate (1/(x^2 + a),x)" gives a result that isn't valid when a = 0... And that's without even digging to look for something more subtle that will be more likely to catch the user off guard.

> Try Fricas.

I admit that I haven't tried Fricas in a long time, but I'm also confident that I wouldn't need to look hard to find examples. Here is just one quote from the Fricas book: "FriCAS can compute some forward Laplace transforms, mostly of elementary functions not involving logarithms, although some cases of special functions are handled." Mathematica, on the other hand, handles a huge number of Laplace transforms involving logarithms and special functions (largely using Meijer G-function methods in combination with internal lookup tables and many different heuristics). How well does Fricas support definite integration with piecewise functions or functions involving branch cuts? Mathematica has improved a lot in this area in the last few years (even if it isn't perfect). Of course, I'm sure Fricas has its strong areas too, and Mathematica is terrible in some areas.

> "Automagical" interfaces suck, they will inevitably break when you stray just a bit from the intended path. It is better to have a typed language like Fricas has.

Oh, I do agree completely about the problem with automagical interfaces that work until they don't :) Nevertheless, even "automagic" that breaks down at some point is great for discovery and prototyping. I think in many cases, we can do a better job providing interfaces that scale smoothly between automatic and user-controlled.

Cheers :)

Arbitrarily precise is not the same as exact. There are many possible examples to illustrate why this matters. Here's one: let's say that you compute floor(f(x)) where f(x) falls right on an integer n. If you evaluate f(x) in floating-point arithmetic, you probably get n +/- epsilon and not n exactly because of rounding errors. This makes the floor function go to either n or n - 1, so you sometimes end up with an error of 1 no matter how precise the floating-point numbers.

That's a good question. The S-expressions are actually a trivial part of the project right now, because there is no symbolic computation going on, just composing S-expressions without any form of rewriting and then generating the website from the final S-expressions. So there is wheel reinvention, but it's just a few minutes of work :) Python happens to be convenient for the website generation, plus I use it because I have other tools in Python. The code is a bit of a mess right now, but I will clean it up gradually.

Later on I plan to make the formula database itself available in some language-agnostic form, with the idea that you could interface it from any programming language or computer algebra system you like. Both Python and Julia are on my radar. And Racket would be quite nice too, since I agree that it's a very nice language for this kind of thing!

Also (shameless self-promotion) python-flint! http://fredrikj.net/python-flint/

Note that number of digits is actually 10^(85 billion), not 85 billion.

I really wish browsers would just render formulas directly from TeX. Let me write <tex>\sqrt{1+x}</tex> or whatever. TeX is the de facto standard for writing mathematical formulas. That browsers don't render it natively just screams of NIH syndrome on the part of browser and web standards developers.

MathML still hasn't caught on after two decades, for three reasons: 1) not working in all browsers; 2) even when it worked, the rendering was often buggy or plain ugly; 3) no one wants to write MathML directly.

MathJax instantly solved all problems, which made it an overnight success. MathML might be able to overcome 1) and 2), but 3) should not be underestimated. MathJax will be around as long as it is the most convenient solution for showing equations in a browser (no user-side compilation required), and rendering times and network traffic will suffer accordingly.

Here's hoping that he follows up Linux and git by going and making a better social network!

The propulsive efficiency as defined in the Wikipedia article is the product of the cycle efficiency (the efficiency turning heat into mechanical power) and the mechanical efficiency (the efficiency turning the mechanical power generated by the engine into movement of the airplane). The mechanical efficiency can be close to 100%, but the cycle efficiency is only 40% or so.

The underlying weakness of the Miller-Rabin test has been known for a long time, and yet "just do N rounds of Miller-Rabin" keeps being perpetuated as the folklore solution to probabilistic primality testing. The BPSW test is basically superior in every way: there are no known counterexamples (and there's currently no feasible strategy to construct counterexamples, if any exist), it's as fast as a single Miller-Rabin test for discarding composites, and if I'm not mistaken, it's about as fast as N = 3 Miller-Rabin tests for primes. In other words, doing N = 50 Miller-Rabin rounds instead of just doing a single BPSW test really makes no sense. I'm happy that the authors advocate the BPSW test as a replacement. BPSW is the default pseudoprime test used in Mathematica, Maple and Pari/GP so it's definitely battle-tested too. Perhaps this work will finally prompt widespread change.

There are more specific cases where open source tooling outperforms Mathematica than where the opposite holds. This especially true when you move away from basic calculus and towards research math. For example, many number theorists don't care about Mathematica at all because it has virtually no functionality for modular forms and L-functions which Pari/GP and Sage on the other hand support very well.

However, nothing open source currently comes close to Mathematica for symbolic and symbolic-numerical calculus (expression simplification, symbolic integration, solving PDEs, etc.). Also, one of Mathematica's main strengths is providing a lot of functionality in a neat package where diverse components are very easy for the user to glue together, with automagical interfaces where the user doesn't need to know what happens behind the scenes (or at least that's how Wolfram PR spins Mathematica being closed source).

Meanwhile, Sage combines a lot of functionality but you can't go very far before you run into visible duct tape, API inconsistencies and things that don't quite work together automatically when you think they ought to. Its documentation is also not as good (Sage has very detailed documentation, but often not well structured). Many of the same issues that exist in open source software in other fields, really.

Agreed. I still boot up my Windows computer just to use PSP 6 occasionally when I need to do some raster graphics editing!

It's possible that evolution inherently drives life towards intelligence (as a likely outcome, not in the teleological sense). Three counter-points:

* Sure, an extreme minority of organisms are intelligent right now, but considering that intelligence is such a recent invention, we can't assume that this is the terminal state of affairs. Indeed, intelligence is making progress in taking over the biosphere that shows no signs of slowing down. Perhaps thousands or millions of years from now, we will have converted all biomass to sustain our own civilization and perhaps (artificial?) life entirely devoted to intelligence will be dominant.

* "Evolution towards intelligence" can be a "thing" even if this only occurs to a small minority of species. This is not to say that evolution is a linear progression from primitive to intelligent life; rather, if evolution makes life expand like a tree, and the degree of variation and complexity afforded by this tree is sufficiently large, it could be likely that some of the branches eventually reach intelligence (among myriads of other possible adaptations). This would be sufficient for intelligence to arise with high probability.

* Life is inherently concerned with representing and processing useful information about the environment. The chemical feedback loops that probably made up proto-life would have implicitly encoded information about their chemical environment (and the fundamental chemistry of life still echoes this information). Eventually the incorporation of more complex feedback loops combined with evolution led to the development of complex biomolecules, proper replicators, genetic code, multicellular organisms, nervous systems, brains, the mammalian neocortex, and whatever adaptations enabled human-level intelligence. What we see is a gradual progression through great many improvements towards more sophisticated information processing. It's plausible that a similar progression in information processing complexity occurs with high probability whenever life evolves, although the concrete steps could be radically different. Yes, it took billions of years on earth, but the universe has billions of years to spare and it's massively parallel. Again, there doesn't have to be a linear progression towards intelligence for all life; the conditions just have to be favorable for intelligence to occur as a particular adaptive niche in sufficiently complex ecosystems.

Of course, we can't really say much since we don't know what the actual probabilities given that we only have a sample size of n=1 for life and realistic experiments or simulations are far beyond our current capacity.

"around 20. Not K, just lines/sec"