fdej

4 ms·

1.
by fdej 1y ago
If you don't want to allow division by 2 then there is Winograd's algorithm from 1967 which works over any commutative ring and uses 48 multiplications for 4 x 4.
2.
by fdej 1y ago
> From the paper, "Notably, for multiplying two 4 × 4 matrices, applying the algorithm of Strassen recursively results in an algorithm with 49 multiplications, which works over any field...AlphaEvolve is the first method to find an
3.
by fdej 1y ago
Just check for the existence of at least one odd digit mod 10^B for some well chosen B. Here is a C program that does the verification up to 2^(10^10) in 30 seconds: https://gist.github.com/fredrik-johansson/8924e10e5d7
4.
by fdej 2y ago
There's no a priori reason why the expected success rate of research projects should be 50% and not, say, 1% or 99%.
5.
by fdej 3y ago
That is the way the FLINT fmpz type does it. The benefit is that you can check for pointers once and then use the operands like ordinary ints without the +1/-1 adjustments. For example, to multiply two integer matrices, you can do O(n^
6.
by fdej 3y ago
This is indeed the issue. Using provable bounds loses too many bits for complex FFTs to make sense for long multiplies.
7.
by fdej 3y ago
This looks quite similar like the "Lagrange models" defined by Joris van der Hoeven in https://hal.science/hal-01188378/document , a version of Taylor models where the constant error term is replaced by an int
8.
by fdej 4y ago
There is an algorithm by Richardson to prove equality of real and complex numbers composed from exponentials and logarithms. (It doesn't have a complete proof of correctness, but it never returns a wrong result: it will loop forever if
9.
by fdej 4y ago
No, this is wrong. Richardson's theorem is about functions, not constants. Equality of constants constructed from exponentials and logarithms is decidable (assuming Schanuel's conjecture) by another theorem (and algorithm!) of Ric
10.
by fdej 4y ago
Author here. I'm only talking about using formalizable and mathematically consistent type definitions in a CAS, not requiring formal proofs in the implementations of types. For example, if you want to prove a+b+c+d=d+b+c+a, you will de
11.
by fdej 5y ago
Correcting myself, the bound is worse than exponential (so read "at least exponential in N"), but the point I wanted to make is that it is explicit. Again, this follows from the general theory of algebraic numbers: the degree and
12.
by fdej 5y ago
Yes, the worst-case complexity is exponential in N, but the wording in the article could lead you to believe that no explicit exponential bound is known, which is false.
13.
by fdej 5y ago
> But how long will we need to look through these sequences of digits before we find the disagreeing digit? It feels intuitively like we should be able to establish some kind of bound on this. Like, maybe we should be able to say “if you
14.
by fdej 5y ago
Yes, indeed, and Strassen is a bad default algorithm because of this. There are specialized situations where the numerical stability isn't an issue though.
15.
by fdej 5y ago
What makes you say that? I've had good speedups with Strassen multiplication in variable precision (or with floating-point, in case you meant fixed-point arithmetic).
16.
by fdej 5y ago
I'm the poster. I think you misunderstood the followup post -- the same library is definitely used in the Cloud (same as the standalone Mathematica).
17.
by fdej 5y ago
Indeed. There's no way for users of Wolfram Cloud, for example, to see that information though.
18.
by fdej 5y ago
My number one wish would be the ability to read definitions from .h files automatically. Other than that, I've had some issues with memory management with ctypes (objects being deallocated prematurely) that I never had with Cython, but
19.
by fdej 5y ago
I'd like to see optimizations targeting ctypes, or a successor to ctypes. I wish I could write elegant, performant C wrappers in pure Python. Right now the best choices are Cython, which is a hassle (separate, slow compilation, various
20.
by fdej 5y ago
This version of CM looks too thin. The version that comes with KaTeX ( https://github.com/KaTeX/katex-fonts ) looks great in the browser though. Would be nice if someone packaged that font in a more user-friendly way.
21.
by fdej 6y ago
I don't know why people complain about the new design. It has been a very effective cure for my reddit addiction.
22.
by fdej 6y ago
Chick Corea was my gateway drug to jazz as a teenager, after my guitar teacher gave me Spain to practice. A lot of musicians have the playing chops but few do truly interesting and original work as composers. Chick Corea was one of those. S
23.
by fdej 6y ago
That's a great question. Of course, you can express the computation as a function or a symbolic expression and evaluate it using a function that recomputes with greater precision automatically (or automatically compiles efficient code
24.
by fdej 6y ago
Should be fixed now. Thanks!
25.
by fdej 6y ago
The library doesn't support this directly. What you can do for normed vector spaces over R (or C) is to use the number types of Arb for the coordinate vectors, implementing your own norm and metric functions for the vector space on top
26.
by fdej 6y ago
I think the name "ball arithmetic" is Joris's idea. I don't have a good reference at hand, but I believe the idea of using a centered form of intervals is as old as interval arithmetic itself. Ball arithmetic has been us
27.
by fdej 6y ago
Good point. I added an RSS feed link to https://fredrikj.net/blog/ . I just hacked together some quick code to generate it, so let me know if it doesn't work.
28.
by fdej 6y ago
This has various names: double-double, quad-double (etc.) arithmetic; floating-point expansions. It's definitely the best way to do arithmetic at precision up to a couple of hundred digits on modern hardware, though traditional arbitra
29.
by fdej 6y ago
For anyone wondering about the difference between endpoint-based interval arithmetic ([a,b]) and midpoint-radius ([m +/- r]) arithmetic (ball arithmetic): they are often interchangeable, but they have different tradeoffs. Roughly speak
30.
by fdej 6y ago
Author here. I will take the opportunity to advertise my blog at https://fredrikj.net/blog/ where I post occasional development updates about Arb and other projects. Some improvements not covered in the 2016 preprint i

More ›