iczelia - blog feed
Dean Hickerson conjectured ( A126236 ) in 2006 that the following fact holds about Huffman codes: Suppose that [math] is the maximum length of a codeword in Huffman encoding of [math] symbols, where the [math]-th symbol has frequency [math]. Prove that [math]. It's very surprising to me that such a simple problem remained open for so long. I thought that perhaps it's obscure enough to warrant no…
Modern software finds it tempting to liberally use dynamic memory allocation. Most objects die young, so applications often see large amounts of churn. This is mostly harmless for programming languages with copying, generational garbage collectors, as there allocation is essentially free (pointer bump and well-predicted conditional branch), and the running time of the nursery GC pass is…
Suppose that we wanted to query for values of Fibonacci numbers up to [math] for some fixed upfront [math]. Clearly the fastest solution -- [math] query and [math] space -- is via direct tabulation. Conversely, one very fast and popular method (binary; via identities for [math] and [math]) requires only [math] space: typedef unsigned _BitInt ( 1024 ) U ; static U fib_fd ( unsigned n ) { U a = 0 ,…
Hosting a website in 2026 is a huge pain in the ass. Not only you have to update your whole system every other day because someone found more RCEs in nginx, the AI labs are also looking to kill your website through a million of tiny cuts. This week alone, Meta's and Anthropic's bots have caused insurmountable waves of completely pointless requests that hammer static endpoints over and over. Most…
Back in July of 2021 I wrote a blog post that claimed a relationship between the inequality [math] and the Gregorian leap-year rule. More than five years later, a couple of experiences wiser and with some proof assistant advancements available, I decided to formally verify the core claim of that blog post, namely: [math] Here "leap year" means the Gregorian rule: [math] In Lean4, we can formalise…
Before we start. Last week has been quite eventful to me. I taught my first university lecture on information theory. I had to fight my E16 a bit to let me actually finish my slide deck and wrote a short blog post at 5:00 a.m. out of frustration. Then I went to sleep, and by the time I woke up I found out that I am in the news... If you're here looking for my work, keep searching. The E16 bug is…
The editor in chief of this blog was born in 2004. She uses the 1997 window manager, Enlightenment E16 , daily. In this article, I describe the process of fixing a show-stopping, rare bug that dates back to 2006 in the codebase. Surprisingly, the issue has roots in a faulty implementation of Newton's algorithm. Introduction Some may find it weird, but I actually greatly enjoy using Enlightenment…
Many years ago, back when I was in my early teens, I picked up an interest in math. Arguably much more superficial than it is now. My gateway drug to discovering abstract algebra was a YouTube video about the unsolvability of the quintic. Of course, I didn't understand shit after watching it. I think that I got lost somewhere midway the video, where the author decided that the best idea is to keep…
Not that long ago I became aware of Justine Tunney's cosmopolitan libc project. It's a toolkit that allows you to compile C source code into a single binary that runs natively on multiple operating systems, including Windows, Linux, various flavours of BSD, even including booters. Unfortunately, back then the project didn't seem to support GUI interfaces and produces quite swollen binaries. Hence…
Programmers often see regular expressions and the respective matching engines as a complex, almost unattainable blackbox. PCRE spans hundreds of thousands of lines of code. It supports a large and evolving feature set. Lookarounds, backreferences, Unicode properties, and multiple matching modes are all present. On top of this, PCRE includes a JIT compiler that translates patterns into machine code…
Introduction The INSAG-1 report on the Chernobyl accident, published in August 1986, was based on preliminary information available at that time. Since then, a large amount of new data has been collected and analyzed. Statements from experts, as well as from the plant personnel itself, have provided a more comprehensive understanding of the events leading up to and following the accident. The…
Most chat apps are centralised, corporate-owned and unwilling to compromise on client choice. Discord enforces its Terms of Service by actively blocking third-party clients. The company changes and obfuscates its server APIs to detect unauthorized connections, monitor traffic patterns, and identify signatures of non-official software. Once detected, users of these clients face account bans .…
The landscape of computer science, programming, and related careers has changed dramatically since I first took an interest in it. A common pattern I have observed is that (prospective) students are often unsure whether they are cut out for programming, so I will attempt to answer this from my own perspective. The job market When I was younger, I could still hear echoes of the "Learn to Code"…
Introduction The Sophie Germain Prime Project primarily aims to collect, analyse and distribute Sophie Germain primes. I have started this project in order to facilitate research on the Blum-Blum-Shub random number generator and related cryptographic algorithms (like the Blum-Goldwasser cryptosystem). Large Sophie Germain primes (as big as 4096 bits) are used in the BBS generator to fulfill…
Introduction. Blum-Blum-Shub (henceforth referred to as BBS) is a pseudorandom number generator uniquely based on the difficulty of factoring large composite numbers. It was introduced by Lenore Blum, Manuel Blum, and Michael Shub in 1986. It is notable for its so-called provable security under certain assumptions , luring many cryptographers to study it. Let [math] where [math] and [math] are two…
I wrote this blog post to answer a frequent question that I receive from strangers on the internet: why do I choose to implement codecs in C? The answer is far from straightforward; if you are interested in the details, please read on. Introduction to Rust There are many places from which you can learn a lot about the in-depth details of why Rust is an innovative language. I chose to summarise…
Background The computational complexity of an optimal sorting algorithm based on comparisons is [math]. We can prove this by reducing the problem of sorting an array to finding the permutation vector that sorts it. There are [math] possible permutations of the set [math]. Each comparison can at best halve the search space of the sorting algorithm. Hence, the amount of comparisons done by an…
I ordered my Model F keyboard from modelfkeyboards.com on the 10th of September. Unfortunately, the next day I realised that my previous choice of keyboard was missing the F keys, which are somewhat important to my workflow. I received a very prompt response from the store owner, who agreed to change my order to a similar keyboard with the F keys (Ultra Compact FSSK Model F). My order arrived on…
Do we have a problem? It makes sense to think that a particular language runtime is fast or slow. There have been various attempts at quantifying what fast or slow means. Such attempts include for example this or this . However, voices of skepticism have been raised against the validity and representativeness of such comparisons. My personal pet peeves include: Task implementations varying wildly…
Currently we have access to various tools to detect the type of data that we are dealing with. Ranging from file to the fancy and new magika from Google or binwalk . However, sometimes such sophisticated tools either provide us with too much or too little information from the perspective of a data compressor. The purpose of segmentation and file type detection is clear: if we know the precise data…
This blog post will be a bit more relaxed than the previous ones. We will discuss (at least the more interesting topics) ground-up, perform a lot of experimentation and hopefully have fun. An introduction to code golf Code golf is a recreational computer programming activity in which participants strive to write the shortest possible program that accomplishes a certain loosely defined task. It…
In this brief article, I will discuss the preliminaries of polygon triangulation using the APL programming language. Triangulation is an important concept in computational geometry, and it has applications in various fields, such as computer graphics, mesh generation, and finite element analysis. Triangular meshes are often used to represent surfaces in computer graphics, and they are also used in…
Shannon's seminal paper "A Mathematical Theory of Communication" introduced the concept of entropy as a measure of information. The paper is a cornerstone in the field of information theory, and it has had a profound impact on various scientific disciplines. The concept of entropy is widely used in physics, computer science, and statistics, among others. In this blog post, I would like to present…
Programs have semantic and syntactic properties. For example, a syntactic property of a certain program could be that it contains a loop, while a semantic property could be that it halts. A trivial property is satisfied by all programs or none. For example, the property "halts" is non-trivial, as it is satisfied by some programs and not by others. The property "domain has zero or more elements" is…
Preliminaries The Fibonacci numbers are defined by the recurrence: [math] A closed form of this formula is given by Binet's formula: [math] where [math] and [math] are the roots of the characteristic polynomial [math]. There are many alternative proofs for this established fact, but the author's favourite concerns generating functions. Suppose that we want to find [math] such that: [math] In this…
Introduction In high school algebra, it is demonstrated that a rational function (a quotient of two polynomial functions) can be expressed as the sum of partial fractions, which are terms of the form [math] The importance of the partial fraction decomposition lies in the fact that it provides algorithms for various computations with rational functions, including the explicit computation of…
The story In the realm of ancient experimentation, the renowned Greek mathematician and engineer Hero of Alexandria, active in the Roman era, stands as a pioneering figure. He is credited with the invention we examine in this small blog post, earning him recognition as one of antiquity's foremost experimenters. Hero's significant contributions include documenting of a steam-powered apparatus known…
The story Dan Baronet (6 May 1956 - 1 Nov 2016 ) was an APL programmer at Dyalog Ltd. . He gained recognition for his unconventional and ingenious utilization of APL primitive functions, Dyalog's Simple APL Library Toolkit (SALT) and others. Several employees at Dyalog have shared intriguing anecdotes about him: Dan was a bit of a prankster and loved to see what tales he could get away with. He…
Introduction λ calculus is a system for expressing computation, terms of which are built using the following rules: Abstraction: λx. X - an anonymous function definition. Application: (X Y) - applying a function X to the argument Y . Variables: x - a bound or free reference. The following operations are commonly performed on λ terms: α conversion: λx. A[x] → λy. A[y] (renaming bound variables in…
This month I have been introduced to the following curious problem: Take the numbers from 1 to 12. Put them into groups. E.g. (1, 2), (8, 10), (3, 4, 5, 6, 7, 9, 11, 12). Average each group e.g. 1.5, 9, 7.125. Then average those averages: 5.875. How do you group the numbers to get the minimum? In this blog post I will try my best to answer the following questions: What is the solution to the…