thxg

Then in January 2022, the NYT bought Wordle, and started tweaking both lists, first shrinking the secret word list to 2309 entries, but leaving the logic otherwise intact. Fast forward to today, I looked up the current code [1], and it seems that there are now 14855 allowed words. The first 12546 are ordered alphabetically (0: "aahed", 12545: "zymic"), and the next 2309 are not. This may suggest that the latter are the secret words, but the logic for picking them has changed: I found no obvious sequence, when compared to the last few days' secret words. So it's either a more complex sequence, or the secret word is picked server-side.

In any case, I guess they decided to re-shuffle the list now at day 1689 / 2309 in order to avoid giving particularly assiduous player an additional bit of information: they can exclude all previous secret words. (To be accurate, I think this would be 1.897 bits, but my information theory is rusty.)

[1] https://www.nytimes.com/games-assets/v2/9003.896ec900f2a1ce8...

They indeed report being 5x slower than Gurobi at 1e-8 precision on Mittelmann instances, which is great. Then again, Mittelmann himself reports them as 15x off COpt, even when allowed to do 1e-4. This is perfectly explainable (COpt is great at benchmarks; there is the presolve issue above; the Mittelmann instance set is a moving target), but I would regard the latter number as more useful from a practitioner's perspective.

This is not to diminish PDLP's usefulness. If you have a huge instance, it may be your only option!

1. They compare their solver with a 1e-4 error tolerance to Gurobi with 1e-6. This may seem like a detail, but in the context of how typical LPs are formulated, this is a big difference. They have to do things this way because their solver simply isn't able to reach better accuracy (meanwhile, you can ask Gurobi for 1e-9, and it will happily comply in most cases).

2. They disable presolve, which is 100% reasonable in a scientific paper (makes things more reproducible, gives a better idea of what the solver actually does). If you look at their results to evaluate which solver you should use, though, the results will be misleading, because presolve is a huge part of what makes SOTA solvers fast.

PDLP is targeted at instances for which factorizations won't fit in memory. I think their idea for now is to give acceptable solutions for gigantic instances when other solvers crash.

[1] https://plato.asu.edu/ftp/lpfeas.html

> Note that the top 56 bits in rax are not zeroed – they contain junk. This is fine b/c the compiler will only make callers check the lowest bit of a register for boolean operations. This is why changing the compiler’s “understanding” (ie the cast) is necessary.

... and yet, the function ABI is clearly i386 (fetching arguments from stack) and indeed everything is compiled with -m32 [2] (i.e. 32-bit SysV ABI). This is a strange contradiction in 2023. On the Intel/AMD side, x86_64 has been prevalent (and the default) for... more than 15 years?

It does not invalidate the article's point. But it is slightly confusing....

[1] https://dxuuu.xyz/

[2] https://godbolt.org/z/ff8r44nKn

- a single array of floats with all the nonzero matrix entries, ordered row-by-row:

  double values[nnz];

  int columns[nnz];

  int start[m + 1];

  for (int i = 0; i < m; i++) {
    index = start[i]; // where
    count = start[i + 1] - start[i]; // number of nonzeros in row i
    
    for (int t = 0; t < count; t++) {
       j = columns[index + t];
       v = values[index + t];
       printf("element (%d, %d) has value %g\n", i, j, v);
    }

[1] https://en.wikipedia.org/wiki/Sparse_matrix#Compressed_spars...

I am not very familiar with the latest trends, could anyone else chime in here? Do Julia coders use fonts with ligatures? That could indeed be one case where confusion is possible. Or maybe not?

- the quality of the solutions found (in the best case: optimal solutions)

- the presence or absence of optimality guarantees (for example, some algorithms provide optimal solutions very often, but cannot guarantee it 100%)

- the time (or computational cost) needed to find such solutions

Furthermore, the state-of-the-art (SOTA) is well known for most types of optimization problems. In this article, they present a list of real and practical applications, so let us have a look at them one by one:

1.1 Traffic flow optimization

Simple flow problems can be solved in polynomial time (and quickly in practice), so there is no need for anything fancy. Once you introduce additional constraints or discrete variable, the SOTA is mixed-integer programming for offline problems. For online problems it's more complicated. In both cases, I am not aware of any application in which MemComputing can reach SOTA.

1.2 Vehicle routing & scheduling

Here, depending on your computing time constraints, needs for solution quality and/or optimality guarantees, the SOTA can be constraint programming (gecode, OptaPlanner), local search heuristics (LocalSolver), or mixed-integer programming (CPLEX/XPress/Gurobi) with column generation. MemComputing is nowhere to be seen again.

1.3 Supply chain optimization

This is a very broad field, but in general mixed-integer programming is king here.

2.1 Protein folding

Here there is quite an objective measure: the biennal CASP competition. This is where AlphaFold made a splash in 2022. MemComputing has never participated.

2.2 Genome sequencing

I am not knowledgeable enough to comment here.

2.3 Radiotherapy treatment

I am not very knowledgeable here either, but last I looked mixed-integer programming approaches were favored.

3.1 Portfolio risk optimization

Various types of branch-and-bound solvers. Mixed-integer linear/quadratic/convex programming. No MemComputing.

3.2 Detecting market instabilities

No idea.

3.3 Optimizing trading trajectories

No idea.

4.1 Training neural networks

Many people here know how this is done. Stochastic gradient descent on GPUs or TPUs. No MemComputing involved. How can they even claim to be active in this field?

4.2 Detecting statistical anomalies

Vague.

4.3 Classifying unstructured datasets

No idea.

The problem is that if you invent a new optimization algorithm, it is very easy to find one instance of one problem for which your algorithm works well. They did literally that in a paper [1]: They took a library of mixed-integer programming problem instances containing 270 benchmark problems, and published a whitepaper showing that they beat a SOTA solver on one of them. A single instance out of 270!

The really hard part is the opposite: given a class of problems, find an algorithm that beats the SOTA. MemComputing has never done that. Combined with their propensity for grand claims backed by misleading evidence, MemComputing have accumulated a lot of badwill from the academic community over the years. My suspicion is that, while on the surface this post seems to put their approach in contrast to quantum computing, what they really try to do here is ride on the quantum computing hype wave.

[1] https://arxiv.org/abs/2003.10644

Before people draw links to recent large language model breakthroughs: Although they do use techniques from computational linguistics, there are no neural networks involved. This is more like old-school AI.

They have essentially a giant optimization problem, and they (approximately) model it as a lattice parsing problem, with a stochastic context-free grammar. They can solve that to optimality in O(n^3), which is too slow for some applications. So they propose a O(n) heuristic (hence no optimality guarantees, but the model was approximate to begin with anyways, and the heuristic is a lot faster), which is the reason for the name of their code: "LinearDesign".

[1] https://www.nature.com/articles/s41586-023-06127-z

Working link in case you are interested:

https://www.youtube.com/watch?v=ujjkbLZETHs

This shortcut in explaining NP-completeness is frustratingly widespread. It is also very wrong. A 49-city TSP was solved (to provable optimality) by hand by 1954 [1]. Concorde [2] can solve TSP instances with more than a hundred thousand cities [3]. In practice, for a graph with a few hundred points, you will most likely find an optimal tour in minutes on an iPhone (yes, there is an app for that [4]).

And it's not just about TSP. SATs [5] and MIPs [6] with hundreds of thousands of variables are solved every day to provable optimality. How? Well, sure, the best-known algorithms for NP-complete problems are of course exponential in the worst-case. But they are definitely not "essentially searching for a solution from all possible answers", that would indeed be prohibitively costly. We have algorithms that perform much better on practical instances (dynamic programming, backtracking, branch-and-bound, etc.).

[1] https://www.math.uwaterloo.ca/tsp/uk/history.html

[2] https://www.math.uwaterloo.ca/tsp/concorde/index.html

[3] https://www.math.uwaterloo.ca/tsp/star/about.html

[4] https://apps.apple.com/us/app/concorde-tsp/id498366515

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

[6] http://plato.asu.edu/ftp/milp.html

I don't have access to a Windows machine, but isn't it possible to achieve the same by writing `cmd.exe` directly to a text file in Notepad? Or is Notepad typically off limits as well in such locked down systems?

On Linux it can be argued that CLOCK_MONOTONIC_RAW should be used for durations. From the Linux man page:

       CLOCK_MONOTONIC_RAW (since Linux 2.6.28; Linux-specific)
              Similar  to CLOCK_MONOTONIC, but provides access to
              a raw hardware-based time that is  not  subject  to
              NTP adjustments or the incremental adjustments per‐
              formed by adjtime(3).  This clock  does  not  count
              time that the system is suspended.

       CLOCK_BOOTTIME (since Linux 2.6.39; Linux-specific)
              A  nonsettable  system-wide clock that is identical
              to CLOCK_MONOTONIC, except that  it  also  includes
              any time that the system is suspended.  This allows
              applications to get a suspend-aware monotonic clock
              without  having  to  deal with the complications of
              CLOCK_REALTIME, which may have  discontinuities  if
              the  time is changed using settimeofday(2) or simi‐
              lar.

At 5:55 the interviewee claims that the high back pressure allows them to blow the air through IP68 filter material. It seems dust-proofing is one of their marketing points.

I don't know what to make of this, so just a few random points: The interviewee is actually the founder and CEO. Has a CS PhD from UT Dallas and mostly a high-level management carreer, most lately VP at Qualcomm. They just came out from stealth mode (December) and announced they raised $100M [1].

[1] https://www.nasdaq.com/articles/frore-systems-emerges-from-s...

By default, GCC generates FMA instructions on Haswell and later:

https://godbolt.org/z/GKb7G4nW9

but it does not with -std=c99 on the command line:

https://godbolt.org/z/KTnqcT6aW

Similarly on 32-bit x86, floating-point uses x87 by default, and some intermediate calculations are in 80-bit arithmetic:

https://godbolt.org/z/4q31oEe14

With -std=c99 instead, we can see additional load/stores, which round down results to 64 bits:

https://godbolt.org/z/qdf4hceca

The C and C++ standards mandate that floating-point operations follow IEEE-754 spec. For example, the result of any elementary operation (+, -, , /) must be the floating-point number "closest" to the exact result of the operation, for some definition of "closest" (i.e., according to a user-modifiable rounding mode). If we denote this rounding operation by fp64(), then the C code

    double x = a + b

    x := fp64(a + b)

    double y = a + b * c

    y := fp64(a + fp64(b * c))

    y := fp64(a + fp80(b * c))

    y := fp64(a + b * c)

    -fexcess-precision=standard is not implemented for languages other than C.

[1] From the man page:

    -ffp-contract=style
           -ffp-contract=off disables floating-point expression
           contraction.  -ffp-contract=fast enables floating-point
           expression contraction such as forming of fused multiply-
           add operations if the target has native support for them.
           -ffp-contract=on enables floating-point expression
           contraction if allowed by the language standard.  This is
           currently not implemented and treated equal to
           -ffp-contract=off.
           
           The default is -ffp-contract=fast.

[3] https://godbolt.org/z/KTnqcT6aW

[4] https://godbolt.org/z/4q31oEe14

[5] https://godbolt.org/z/qdf4hceca

Yes! Different people can make different performance-vs-correctness trade-offs, but I also think reproducible-by-default would be better.

Fortunately, specifying a proper standard (e.g. -std=c99 or -std=c++11) implies -ffp-contract=off. I guess specifying such a standard is probably a good idea independently when we care about reproducibility.

Edit: Thinking about it, it the days of 80-bit x87 FPUs, strictly following the standard (specifically, always rounding to 64 bits after every operation) may have been prohibitively expensive. This may explain gcc's GNU mode defaulting to -ffast-math.

[1] https://news.ycombinator.com/item?id=27880461

    void type_init(type *t, [...]);
    void type_clear(type *t, [...]);

However, if we are constrained to a C API, it does have one important practical quality in my experience: Because it is always the same, it eases the mental load on both the API's user and the API's implementer, especially if there are many such types involved.

[1] See e.g. https://gmplib.org/manual/Initializing-Integers

... if you specify an ISO language standard (e.g. -std=c99). By default, in GNU mode, gcc will happily emit FMA at -O3. From the man page:

By default, -fexcess-precision=fast is in effect; this means that operations may be carried out in a wider precision than the types specified in the source if that would result in faster code, and it is unpredictable when rounding to the types specified in the source code takes place. [...] [-fexcess-precision=standard] is enabled by default for C if a strict conformance option such as -std=c99 is used.

> Unfortunately compilers can't emit FMA instructions without specifying [-ffast-math]

I would argue that it would have been fortunate if FMA was disabled by default. And that it is unfortunate that it is not.

Yes, FMA has a performance boost and (usually) better accuracy... But it comes at the cost of bit-for-bit reproducibility. If we let the compiler automatically decide when to apply FMA, then a compiler upgrade or even unrelated code changes could lead to slightly different results as rounding is performed at different points in the computation. For numerical codes in which small perturbations can yield wildly different solution paths, debugging can become a nightmare.

Of course this is a subjective preference and it strongly depends on the application domain. I agree that for some people defaulting to best performance at -O3 is the right choice.

Floating-point numbers form a finite set. It is thus impossible for them to represent all real numbers. The correct rounding of a real number x is the unique floating point number that is closest to x, according to a user-chosen definition of "closest" (possibly always rounding up or down, and including precise rules for ties). IEEE-754 is the standard for floating-point maths, followed by most programming languages. It mandates correct rounding for elementary operations (+, -, ×, ÷), but not for transcendental functions (exp, log, sin, cos,...), or at least that is the situation in practice now (the truth is a bit more subtle, see Q3 in FAQ link below). Correct rounding for transcendental functions was generally thought to require arbitrary precision arithmetic and hence to be prohibitively expensive. Still, if performance is not the priority, it is attainable (the MPFR library does it, and at arbitrary precisions, not just 32 and 64 bits).

The main practical advantage of correct rounding is the uniqueness of the return value for math functions (for every input, there is at most one possible correct output). For debugging, it is amazing to have bit-for-bit reproducibility across builds, compilers, hardware and platforms. With incorrect rounding, instead, every implementation does it differently, and we lose reproducibility across platforms. Worse, every time the maths library (e.g. libc/libm) is updated (say, fixing a performance bug in a corner case), we can also get slightly different answers.

Recently, there has been a renewed push for fast correctly-rounded transcendental functions (see, e.g., RLIBM and CRLIBM). Verifying correctness is fairly straightforward for 32-bit float functions with one argument, because we can perform complete enumeration over inputs, then check outputs with MPFR. Proofs for correctly-rounded 64-bit float functions can be much more involved.

CORE-MATH is an attempt to create a repository of math functions that are

- open-source and permissively-licensed

- correctly-rounded

- fast enough to be a drop-in replacement for standard library functions

- API-compatible with standard library functions (wrt. rounding modes in particular)

- at various bit widths, mostly 32 for now, but also 64, 80 and 128 bits.

Crucially, CORE-MATH is not a library. Their objective is explicitly to get the code from the repository included into other libraries. Their long-term objective (see abstract in paper link below) is to get to a point where fast correctly-rounded implementations are available for all transcendental functions. Then, the IEEE-754 standard committee could consider mandating correct rounding for everything in the next revision of the standard.

Paper: https://hal.inria.fr/hal-03721525/

Gitlab: https://gitlab.inria.fr/core-math/core-math

FAQ: https://core-math.gitlabpages.inria.fr/faq.html

Exactly! The author already has all the infra necessary (rdtsc for each call). Measuring time inside the game would be more accurate and simpler. Why did the author do things this way? I must be missing something.

(By the way, the author even seems to know about this issue since they added code that simulates using the allocated blocks (touching one byte for every allocated 4k), but that does not feel like it's nearly enough.)

> grab the call stack as well

Maybe this part could be done with no code with VTune / Linux perf? Sure, those only gather stochastic measurements (so not ideal for the original latency measurement). But to get a rough idea of where the costly allocations come from, it could be an easy way.

> I’m well aware of banker’s rounding, and rounding up, and round down, and rounding towards zero, and rounding towards signed infinity, etc.

MPFR supports most of those rounding modes you mentioned:

https://www.mpfr.org/mpfr-current/mpfr.html#Rounding

> But “correct” as a formal modifier is new to me

It just means that once you select a rounding mode, it is guaranteed (modulo bugs) to give you the correct answer rounded according to your selected rounding mode.

At first one can think: "obviously, who wants incorrect rounding?". And indeed all recent floating-point hardware implements correct rounding... But only for 32- or 64-bit floats, and only for addition, subtraction, multiplication and division.

By contrast, most libc/libm implementations do not have correct rounding for transcendental functions (cos, sin, tan, exp, log, etc.). There are some exceptions (Rlibm, CRlibm).

MPFR implements correct rounding

- at any bit width and

- for all transcendental functions.