thxg

Just to make things extra clear, the post we are commenting on has

- 99.4% in 6 guesses or less

- 3.64 guesses average

- no attempt of any formal optimality result,

while the one you posted has:

- not just 100% in 6 guesses or less (so 100% wins not 99.4%), but actually 100% in 5 guesses or less!!!

- 3.42 guesses average

- a fairly convincing optimality proof (as far as average is concerned) which was apparently the only hard part computationally.

- it also had 3 upvotes until i cross-references it here, and barely more now.

- the author seems to have plenty of twitter followers, none of which seemed to care much.

And yet if you look at the "new" page, the flow of heuristics keeps coming. Conclude what you will :-).

Ok, I found this one [1] with 100% wins on the whole 12k-word set. But it optimizes for worst-case, not average.

[1] https://www.poirrier.ca/notes/wordle/

This [1] solves it in 3.4212 average guesses 100% of the time and claims optimality, which is 99% of the difficulty it seems. For the limited 2671-word set of possible words, I think the question is now settled (for the whole 12k-word set, I don't think anyone tried anything).

It was posted here four days ago [2].

[1] http://sonorouschocolate.com/notes/index.php?title=The_best_...

[2] https://news.ycombinator.com/item?id=30006724

You're right, I didn't know that. In a quick "long double" vs "double" microbenchmark, I see a negligible penalty for additions and comparisons, and 37% penalty when multiplications are involved.

The article covers ways to obtain smaller error bounds, mainly for testing algorithm stability in practice.

The methods proposed are very varied in nature: blocked algorithms, x87 80-bit arithmetic, AVX2/ARMv8-A fused multiply-add (FMA) operations, and probabilistic bounds.

While the article is otherwise very good, I am unsure about one of those in 2021: 80-bit arithmetic. The corresponding x87 instructions are deprecated by Intel, and their performance is disastrous. For example, the complex algorithms implemented in software by glibc to compute transcendental functions (sin, cos, exp, ...) are faster and more accurate than their single instruction x87 FPU counterparts (FSIN, FCOS, ...)!

I would be very curious to see, in a few algorithms, a comparison of x87 arithmetic with double-doubles and even low-precision MPFR. MPFR, by the way, may have its place here if we're talking about sacrificing some performance for higher precision.

Code using "long double" on x86_64 will compile to x87 instructions (at least with GCC on Linux).

This can be triggered unintentionally. For example, string-to-double conversions in Boost use long doubles.

(I have been bitten by that when using valgrind: Valgrind emulates x87 80-bit registers using 64-bit doubles. As a result, some Boost-using code will have a different behavior under valgrind.)

> FMA is a godsend for writing accurate arithmatic.

True, and the small performance boost (on some platforms) is nice too

> never reordering floating point computations unless you explecitly give permission

Yes, requiring explicit code for FMA and arithmetic grouping/reordering in general seems like the sane approach.

Yes, indeed it is the case with fused multiply-add operations, as I wrote below in another thread. By default at -O3, unfortunately, gcc and icc both take responsibility for deciding whether or not to use FMA instructions when they see (a x b + c) expressions. As a result we can even see slightly different result across compiles!!

However, as far as I understand, specifying a proper language standard (for example -std=c99, -std=c++14, etc.) restores sane behavior (see -ffast-math, and more specifically -fexcess-precision).

Are there other cases where -O3 breaks IEEE754 on modern setups?

This work essentially allows one to go beyond the IEEE754 standard which mandates correctly-rounded elementary operations +, -, x and / : they provide implementations of libm functions (cos, sin, log, exp, etc.) that are also correctly rounded.

This is really nice, not necessarily because anyone cares about the correctness of the last bit in a float. But more importantly, because since there is only one "correct" answer, requiring correct rounding means that those functions are then fully specified and deterministic. No more getting slightly different result when changing platform, OS, or even just updating libm (some transcendental functions are still actively being improved, thus changed, in glibc!). This is amazing for reproducibility.

Since the performance is good (even better than existing libm implementations, they claim), this is a true win-win.

This is obviously made possible by the fact that one can easily enumerate all 32-bit floats. It would be amazing to have something similar, even at a big performance cost, for 64-bit doubles (MPFR can do it of course but the perf cost there is truly massive). Things are much harder with 64 bits, unfortunately.

Nowadays, all major platforms follow IEEE754, which specifies exactly the results of elementary operations (+, -, x, /). You must get bit-for-bit reproducible results across different runs, compiles, libraries, OSes and hardware. Any difference is a bug.

However:

1. As the paper emphasizes, math library functions (sin, cos, log, etc.) are not covered by that standardization, at least not mandatorily and not in practice. This is the problem that the paper tackles.

2. In the bad old days of the x87, the FPU carried out computations on eight 80-bit registers. The problem is that whenever those registers spilled out to the stack, precision was truncated down to whatever type the language actually meant (64-bit double or 32-bit float). Because the register-spilling decision is mostly taken by the compiler, it was largely unpredictable. This resulted in code that was not reproducible, even across compiles! Since x87 was deprecated in favor of SSE/AVX, the precision of operations is always that of the type used in the code. Lower than 80-bits but much better in practice because of consistency and reproducibility.

3. The bad old days are making a comeback with FMA instructions (fused multiply-add). This is a single operation (a x b + c) and so it is correctly rounded to the closest representable number. This number can be different from ((a x b) + c) in which two roundings occur. If we give the compiler freedom to decide whether or not to fuse such expressions, we will again see non-reproducibility across compiles. Unfortunately, gcc and icc both do that by default at -O3 (see -ffast-math, and more specifically -fexcess-precision). Specifying a proper language standard (for example -std=c99, -std=c++14, etc.) restores sane behavior.

The short papers accompanying the submissions are not out yet, but apparently the winning team did not use ML at all:

https://mobile.twitter.com/alexkontorovich/status/1423259110...

General introduction to the TSP problem video by a member of the winning team:

https://m.youtube.com/watch?v=vQMFVLa7yYQ

Video explanation by the very entertaining Bill Cook from the winning team:

https://m.youtube.com/watch?v=vQMFVLa7yYQ

One peculiarity of the winning submission is that, in an ML challenge, they did not use ML at all:

https://mobile.twitter.com/alexkontorovich/status/1423259110...

Yes, although the trick is used in the first place in order to replace a 6-cycle division by a 1-cycle multiplication (on x86_64, assuming no CPU stalls). Roughly, in order to still make it a net positive, we have a 4-cycles budget for additional operations. That's very tight for reversing the bits of a uint32_t.

Hmmm... maybe Zoom devs too use Stack Overflow?

https://stackoverflow.com/questions/3376679/qt-how-to-detect...

^ This is the correct answer.

I installed the Zoom client just to have a look for myself. The syscalls in question emanate from freshly forked processes that immediately execvp() the command `pidof` (on my system it finds it under /usr/bin, so it's the system command, not anything fishy shipped by Zoom). Actually, the command-line argument to the command is, in succession:

gnome-session

gnome-panel

gnome-shell

gnome-session-binary

ksmserver

cinnamon

cinnamon-session

mate-panel

mate-session

xfce-mcs-manage

xfce4-panel

xfce4-session

I suppose Zoom goes through the whole list on my system because it finds none of them. The fact that it stops on parent's system suggests that Zoom stops when it finds one. This hints at a very crude way to determine the desktop environment!

Sorry, we can write

    iterations <= 2N.

We don't even need O() here.

I'm not sure we should answer homework questions here, but this one is cute so...

At first sight it seems like O(N log(N)) at worst, because the outer loop does log(N) iterations.

But you can actually get tighter. The number of inner loop iterations is

       N + (N/2) + (N/4) + ... + 1
    <= N + (N/2) + (N/4) + ...
     = N (1 + 1/2 + 1/4 + ...)
     = N 2

so we can write O(2N).

Also, the article concludes that FMA hurts accuracy, and this is at best misleading (FMA is better in the worst case). But the example given does highlight something important:

Depending on the case, the accuracy gains can be tiny (so much so that in this example the FMA version does indeed return larger errors in most runs), and the performance gains can be small too.

On the other hand, the price to pay for letting the compiler freely decide whether/when to fuse * and + is huge: reproducibility. Since x87 was deprecated, having floating-point results be bit-for-bit consistent across platforms, compilers and optimization flags has been amazing for debugging. Losing that is a step back and a recipe for headaches.

I was surprised that gcc enables -fexcess-precision=fast by default (in GNU mode), hence enabling transparent FMA and potential headaches. Specifying the standard (e.g. -stdc=c17) fixes that.

Okay I got nerdsniped by this, reimplemented and reproduced it. As others mentioned, the article does not show a flaw in the M1's FMA. The results are the same on x86_64. It is just due to how this particular formula interacts with floating-point rounding, and it all depends on the order of magnitude of the numbers.

The basic operation here is

    x = (((a * b) + c) - c) / b

which would yield (x == a) in exact arithmetic.

Let's denote by fp(y) the floating-point number closest to y. If you don't use FMA, then the middle of the formula is essentially fp(fp(M + c) - c) for some M. When you pick the natural choice of initial a, b and c having the same order of magnitude, this gives exactly M in 99.99% of cases. Then you're just measuring the difference between a and (a * b) / b. Instead, FMA gives you x = fp(fp(fp(a * b + c) - c) / b), which is admittedly more complex to study.

But as you pick larger and larger c values, you can observe that FMA becomes more accurate compared to the other version. When c reaches about 0.5e+6 times larger than a and b, FMA starts winning. Note that a is incremented 1M times as the proposed algorithm iterates, so this corresponds to (a * b) and c having the same orders of magnitude on average, as the loop progresses.

You can probably go much more in-depth in studying this, and explain it better. But essentially this is a non-issue, just floating-point being floating-point.

If you want to play with the code, you can find it here:

https://godbolt.org/z/WWqdcrzdh

gcc will avoid FMA if you specify `-std=c17` (or another C standard, instead of the default "GNU" variant). Note that it has to avoid FMA in that case because fusing (a * b) + c would not comply with the C17/IEEE-754 spec (see -fexcess-precision in the manual).

> Are there flaws in some ARM64 instructions?

The result of (IEEE 754) operations -- including PLUS, MINUS and FMA -- is specified bit-for-bit, at least for `isnormal()` numbers. It is not a matter of vaguely "more precise" or "less precise".

The test performed brings no information towards answering the question, because the loss of precision precision in one particular complex algorithm can perfectly well happen despite one individual operation having better worst-case precision.

To check the unlikely event of a flaw in M1's FMA, one would need to compare the output of invidual FMAs with MPFR's output on the same operands.

> ARM64 v Intel: I haven’t attempted to look at Intel processor fused instructions

Instead, this test could have been a clue. FP64 results follow the spec and hence must be bit-for-bit equal across platforms (as long as one avoids legacy x87 on Intel).

> (it's NP-complete after all)

Protein folding is a physical/biological phenomenon. AFAIK we don't currently have a proper exact mathematical formulation of the problem that would let one determine its complexity.

You may be referring to this paper [1]. It only claims that one particular optimization problem, believed to give a solution to protein folding problems, is NP-hard. So, even if a suitable exact formulation exists, it is not yet proven that protein folding is hard, although it for sure seems plausible.

By the way, it is perfectly possible today to solve some very large-scale NP-hard problems (think millions of variables and constraints) in reasonable amounts of time (think minutes or hours). Examples are knapsack problems, SAT problems [2], the Traveling Salesman Problem [3] or more generally Mixed Integer Programming [4].

[1] "Complexity of protein folding", 1993, by Aviezri S. Fraenkel

[2] http://www.satcompetition.org

[3] http://www.math.uwaterloo.ca/tsp/

[4] http://plato.asu.edu/bench.html

Very subtle glitch example at about second 10 of this video, against the blue background:

https://m.youtube.com/watch?v=AJtLAYmdgTw

I don't know how they do it, although the reddit commenters do mention IR emitters/reflectors in the ad panels being used to create a mask.

What I did notice is that the system commonly has very slight glitches around player bodies if you pay very close attention. This is most visible in close-up shots from mid-height cameras. The effect is similar to how video call blur filters imperfectly detect hair boundaries. The ad boards sometimes cover small parts of players' faces.

In essence, this seems to be Amazon's AWS Lumberyard engine going from source-available (but proprietary) to Apache 2.0

Sorry, I meant that those two books seem to be "classics" that are often used as references in graduate courses.

For theoretical continuous/nonlinear/convex optimization, your #1 is the bible, together with

"Convex Optimization" by Boyd & Vandenberghe.

However, beware that both are grad textbooks. They can be tough going at times. Unfortunately, I never found undergrad textbooks I liked much, for theory.

If you're interested in discrete optimization too (the other half of math optimization), the classics are:

"Optimization Over Integers" by Bertsimas & Weismantel

"Integer and Combinatorial Optimization" by Nemhauser & Wolsey

I looked for such a tool a couple of years ago and did not find any. As other comments indicate, this one may not yet be fully general-purpose.

Could anyone here point me to an alternative? Something that generates rss or atom from HTML files, and called from the command line. Essentially, something like pandoc, but for rss.

> These "best cases" are hand-tuned for the domain by algorithm experts - right?

Correct. It is arguably more than just "hand-tuned". The algorithm I mentioned, LKH, was entirely designed for TSP, and I'm not aware of it being applicable to much else.

> How big is the performance jump from generic z3 or whatever?

For TSP, an enormous jump. Certainly more than 3 orders of magnitude.