961
New
The latest blog posts to take off on Hacker News. 2,851 posts.
962
Verifying GCC optimizations using an SMT solver
This post describes the implementation of pysmtgcc. See “GCC Translation Validation” for background information.
963
Visualizing Diffs: The Myers difference algorithm (2020)
In 1986, Eugene Myers published An O(ND) Difference Algorithm and Its Variations , which unified the problems of finding the longest common subsequence of two sequences (the LCS of "driftwood" and "artwork" is "two") and finding the shortest edit script for transforming one sequence into another. Myers showed that…
964
965
Markov chain Monte Carlo without the bullshit (2015)
I have a little secret: I don’t like the terminology, notation, and style of writing in statistics. I find it unnecessarily complicated. This shows up when trying to read about Markov Chain Monte Carlo methods. Take, for example, the abstract to the Markov Chain Monte Carlo article in the Encyclopedia of…
966
Ssss: Shamir's Secret Sharing Scheme (2006)
Shamir's Secret Sharing Scheme
967
SHA-3 Buffer Overflow
Update: This result appeared in the proceedings of CT-RSA 2023. A preprint is available.
968
The Mystery of 355/113 (2010)
Today's date is a good excuse to memorize a few more digits of 3.1415926 53589793 23846264 33832795....
969
Emulating double precision on the GPU to render large worlds
One of the problems with developing games with large game worlds is that objects start to jitter and teleport around as you move away from the world origin. This post is about how we overcame one challenge in particular and what we did.
970
Math with Bad Drawings
Now available for preorder.
971
Seven sins of numerical linear algebra
In numerical linear algebra we are concerned with solving linear algebra problems accurately and efficiently and understanding the sensitivity of the problems to perturbations. We describe seven si…
972
Simulating Wind on Procedural Terrain Using Lattice Boltzmann Method
Note: The full source code for this article can be found here (summarized version). Individual sections contain references to specific code snippets below.
973
On AlphaTensor’s new matrix multiplication algorithms
Two acquaintances independently asked about this today, so it seems worth a write-up: recently (as of this writing), DeepMind published a new paper about a new practical fast matrix multiplication …
974
Discovering Novel Algorithms with AlphaTensor
In our paper, published today in Nature, we introduce AlphaTensor, the first artificial intelligence (AI) system for discovering novel, efficient, and provably correct algorithms for fundamental tasks such as matrix multiplication. This sheds light on a 50-year-old open question in mathematics about finding the…
975
Knuth's Art of Computer Programming, V 4B, has gone into print
(I'm still looking for the catchiest way to appreciate the number MMXXVI. Exercise 7.2.1.6–122 gives 1234+.5*6+789 and -1+2345*6/7+8+9 and 1+(2/3)*45*67.8-9 ; other suggestions are welcome. The most elegant that I've seen so far is a beauty that was suggested independently by Arnaud Lefebvre and by Evangelos…
976
What Are the Odds?
An unusual lottery result made the news recently: on October 1, 2022, the PCSO Grand Lotto in the Philippines, which draws six numbers from $latex {1}&fg=000000$ to $latex {55}&fg=000000$ a…
977
An Algorithm for Polygon Intersections
In this post we'll work our way towards an algorithm that can compute convex polygon intersections. We'll also explore a method for intersections between axis-aligned rectangles, a function that can determine the intersection of two line segments, as well as a point in polygon test.
978
Explained from scratch: private information retrieval and homomorphic encryption
This is a from-scratch explanation of private information retrieval built using homomorphic encryption. I try to assume only a general math / computer science background. To simplify things, my explanations may not always match academic definitions. You can check out this paper or code for more.
979
Turns are better than radians
Switching away from radians makes code simpler, faster, and more precise.
980
Using GPT-3 to pathfind in random graphs
I wondered how GPT-3 might do on the following problem: given a partially-connected graph, find a path between two nodes, or determine that no path exists. I wrote some code to automate generating …
981
982
Number theory explained from first principles
A lot of modern cryptography builds on insights from number theory, which has been studied for centuries.
983
The definitive guide to “modulo bias” and how to avoid it (2020)
The Latest News from Research at Kudelski Security
984
Death by hockey sticks
You may be familiar with the term “hockey stick curve,” used describe a trend that has been flat/stable for a very long time, but shoots up at the end of the series in dramatic fashion, resembling the shape of a hockey stick. Hockey can be a violent sport, and it’s easy to get hurt by even one well-aimed swing…
985
Gödel, Escher, Bach: an in-depth explainer
[Thanks to Jacob Falkovich, Eric Neyman, and my LessWrong reviewer, among others, for their feedback on earlier drafts.] …
986
Parallel Curves of Cubic Béziers
Blog of Raph Levien.
987
Ramanujan Factorial Approximation (2012)
Ramanujan came up with an approximation for factorial that resembles Stirling's famous approximation but is much more accurate. As with Stirling's approximation, the relative error in Ramanujan's approximation decreases as n gets larger. Typically these approximations are not useful for small values of n. For n = 5…
988
Someone’s Been Messing with My Subnormals
TL;DR: After noticing an annoying warning, I went on an absurd yak shave, and discovered that because of a tiny handful of Python packages b...
989
Busy Beaver Updates: Now Even Busier
Way back in the covid-filled summer of 2020, I wrote a survey article about the ridiculously-rapidly-growing Busy Beaver function. My survey then expanded to nearly twice its original length, with …
990
Converting a fisheye image into a panoramic, spherical or perspective projection
The source code implementing the projections below is only available on request for a small fee. It includes a demo application and an invitation to convert an image of your choice to verify the code does what you seek. For more information please contact the author .