Hacker News: fdej

New comment by fdej in "AlphaEvolve: A Gemini-powered coding agent for designing advanced algorithms"

fdej — Wed, 14 May 2025 22:36:09 +0000

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.

New comment by fdej in "AlphaEvolve: A Gemini-powered coding agent for designing advanced algorithms"

fdej — Wed, 14 May 2025 21:03:51 +0000

> 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 algorithm to multiply two 4 × 4 complex-valued matrices using 48 multiplications."

...but Waksman's algorithm from 1970 [1] multiplies two 4 x 4 complex-valued matrices using only 46 multiplications (indeed, it works in any ring admitting division by 2).

Sloppy by DeepMind and by Nature to publish such a claim - did they not ask someone knowledgeable about matrix multiplication to review the work?

[1] https://doi.org/10.1109/T-C.1970.222926

New comment by fdej in "Powers of 2 with all even digits"

fdej — Thu, 20 Mar 2025 21:31:04 +0000

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/8924e10e5d74e39109...

Edit: made it multithreaded, goes up to 2^(10^12) in nine minutes on 8 cores.

New comment by fdej in "Author-paid publication fees corrupt science and should be abandoned"

fdej — Sat, 24 Aug 2024 07:54:52 +0000

There's no a priori reason why the expected success rate of research projects should be 50% and not, say, 1% or 99%.

New comment by fdej in "What is gained and lost with 63-bit integers? (2014)"

fdej — Sat, 12 Aug 2023 09:20:29 +0000

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^2) pointer checks and then do O(n^3) arithmetic operations without overhead. But if the pointer check is done each operation then the representation doesn't make much difference; whether you use the LSB or MSB as a tag, what kills performance is checking and branching based on a tag bit in the first place. What you'd want is a sufficiently smart compiler (TM) that can eliminate as many such checks as possible.

New comment by fdej in "Large Multiplication"

fdej — Fri, 14 Jul 2023 09:47:07 +0000

This is indeed the issue. Using provable bounds loses too many bits for complex FFTs to make sense for long multiplies.

New comment by fdej in "Beyond automatic differentiation"

fdej — Fri, 14 Apr 2023 17:30:27 +0000

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 interval multiple of x^n.

Representing functions locally is a very interesting problem: there are lots of possible approaches using intervals, Taylor series, Chebyshev series, etc. Big open design space if you ask me.

New comment by fdej in "Now I’m calculating with constructive reals"

fdej — Wed, 27 Apr 2022 08:45:01 +0000

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 iff it encounters a counterexample to Schanuel's conjecture.)

It can also be extended to higher transcendental functions, but it gets harder to guarantee termination.

I have a library for exact reals/complexes with an incomplete implementation of Richardson's algorithm: https://fredrikj.net/calcium/

New comment by fdej in "Now I’m calculating with constructive reals"

fdej — Wed, 27 Apr 2022 08:34:11 +0000

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 Richardson.

New comment by fdej in "Things I would like to see in a computer algebra system"

fdej — Thu, 21 Apr 2022 07:57:35 +0000

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 define a, b, c, d as elements of a type R implementing the "additive abelian group" interface (or an extension of this interface, like "ring"); R = integers, for example. The CAS can then use builtin techniques for abelian additive groups to prove the property efficiently. It will not have to prove those properties from first principles.

In the distant future there could perhaps be some kind of convergence between CASes and proof assistants to completely rule out implementation errors, but this would require breakthroughs in proof automation for the reason you mentioned.

New comment by fdej in "A surprisingly hard CS problem: sums of square roots (2018)"

fdej — Tue, 25 Jan 2022 11:26:57 +0000

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 height of a sum, product or root of algebraic numbers can be bounded explicitly (resultants + Mignotte bound for factors), and finally root separation bounds can be applied to the resulting polynomial.

New comment by fdej in "A surprisingly hard CS problem: sums of square roots (2018)"

fdej — Mon, 24 Jan 2022 17:22:45 +0000

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.

New comment by fdej in "A surprisingly hard CS problem: sums of square roots (2018)"

fdej — Mon, 24 Jan 2022 14:32:25 +0000

> 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 add two lists of n numbers, each of which has d digits, then they can’t disagree for more than k * n * d digits” for some k. But no-one’s been able to prove anything like this.

You can write down a completely explicit bound here using the Mahler-Mignotte root separation bound. More generally, for any algebraic expression involving algebraic numbers, you can bound a priori the number of digits you need to check to determine its sign.

When you involve transcendental numbers, things do get much harder though.

New comment by fdej in "Matrix Multiplication Inches Closer To Mythic Goal"

fdej — Sat, 18 Dec 2021 12:52:34 +0000

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.

New comment by fdej in "Matrix Multiplication Inches Closer To Mythic Goal"

fdej — Sat, 18 Dec 2021 08:05:01 +0000

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).

New comment by fdej in "Launching Version 13.0 of Wolfram Language and Mathematica"

fdej — Thu, 16 Dec 2021 17:03:16 +0000

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).

New comment by fdej in "Launching Version 13.0 of Wolfram Language and Mathematica"

fdej — Thu, 16 Dec 2021 16:51:38 +0000

Indeed. There's no way for users of Wolfram Cloud, for example, to see that information though.

New comment by fdej in "Faster CPython Ideas – Issue Tracker for Faster CPython Project"

fdej — Fri, 14 May 2021 09:22:18 +0000

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 that may just be my own fault. I agree about the lack of interop with Python ints.

New comment by fdej in "Faster CPython Ideas – Issue Tracker for Faster CPython Project"

fdej — Thu, 13 May 2021 12:27:32 +0000

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 warts), and ctypes, which is slow (and has some design problems of its own). Julia's ccall alone is a major selling point over Python right now.

New comment by fdej in "Using Computer Modern on the web (2013)"

fdej — Wed, 12 May 2021 13:30:40 +0000

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.