pervognsen

I came across Fabian's nice old blog post on quaternion differentiation:

https://fgiesen.wordpress.com/2012/08/24/quaternion-differentiation/

I wanted to write a quick note on some of the broader context, which hopefully makes the quaternion case look less special.

Given any associative algebra where you can define what exp means, it's always true that d/dt exp(at) = a exp(at), which means the unique solution of x' = ax is x(t) = exp(at) x(0) = exp(a)^t x(0). In fact, it's true even if you work with formal power series, where you treat t as a formal symbol and interpret differentiation as the operator that shifts t^n down to n t^(n-1).

pervognsen

(Originally written as a reply to an HN submission of this article: https://www.cs.virginia.edu/~lat7h/blog/posts/434.html)

There's a simple recipe for arithmetically encoding recursive algebraic data types (in the functional programming sense) which is related to this.

What you might have seen is Goedel numbering where a finite sequence of natural numbers a_0, a_1, ..., a_n (where n isn't fixed but can vary per sequence) is mapped bijectively onto p_0^a_0 a_1^p_1 ... a_n^p_n where p_0, p_1, ... is an enumeration of the primes.

However, if you want to represent trees instead of sequences, you have a better, simpler option. The key is the existence of a bijective pairing function between N^2 and N, which you can write as <m, n> for m, n in N.

You have a lot of choices for how to construct the pairing function. But a curious fact is that there is essentially one polynomial pairing function and it's the one you saw in class when you learned that the rationals are countable: https://en.wikipedia.org/wiki/Fuet

pervognsen

#define _CRT_SECURE_NO_WARNINGS
#include <string.h>
#include <stdio.h>
#include <windows.h>
#pragma warning (disable: 4146)
#include <stdint.h>

#ifdef _DEBUG
#define Assert(x) \
    if (!(x)) { MessageBoxA(0, #x, "Assertion Failure", MB_OK); __debugbreak(); }

pervognsen

#include "mu.h"

#define _CRT_SECURE_NO_WARNINGS
#include <malloc.h>
#define _USE_MATH_DEFINES 
#include <math.h>
#define _NO_CRT_STDIO_INLINE
#include <stdio.h>
#include <stdarg.h>
#define NO_STRICT

pervognsen

Theorem (Smooth Invariance of Domain). Let f : R^n -> R^n be continuously differentiable and injective.
Then for every open set U, its image f(U) is an open set. In other words, f is an open mapping.

Proof. Let y_0 be a point in f(U) with y_0 = f(x_0) for some x_0 in U. We must show that we can fit
an open ball around y_0 that fits entirely within f(U).

Since U is open, there is some radius r > 0 such that the sphere S with center x_0 and radius r is
contained within U. Consider the function d(x) = |f(x) - y_0| defined on S. Because S is compact and
d is continuous, it attains its minimum m. As f(x_0) = y_0 and f is injective, it follows that d must
be strictly positive and hence m > 0. Then by construction we have |f(x) - f(x_0)| >= m for all x in S

pervognsen

This is a brief comment on this article on API design principles:

  https://gist.github.com/vurtun/192cac1f1818417d7b4067d60e4fe921
  
I've called that style of API a coroutine, iterator, state machine, push/pull or client/server API
depending on what seems most appropriate for the context, but they are all variants of the same idea.

It's particularly superior in many cases as an alternative to callback-based APIs, which are the more
common way of providing this kind of fine-grained interleaving between library code and user code.
Callbacks can still be superior in usability for context-free operations like memory allocation,

pervognsen

Suppose we want to compute the frequency spectrum of an n-point sampled signal. That is,
we want to compute the signal's discrete Fourier transform. Taking a cue from multi-rate
signal processing, let's try a divide-and-conquer approach where we downsample the signal
by 2:1 and recursively compute the spectrum of that. There are two possible downsamplings,
corresponding to the even and odd phases.

By the Nyquist sampling theorem, assuming the signal has no upper half-band frequencies,
i.e. its top n/2 frequency bins are zero, the spectrum can be perfectly reconstructed
from the spectrum of _either_ the even subsignal or the odd subsignal, without any aliasing.

pervognsen

import libc {...}

struct StrLinesIter {
    next: char const*;
    start: char const*;
    end: char const*;
}

func str_lines(str: char const*): StrLinesIter {
    return {next = str};

pervognsen

Von Neumann is credited with a method for generating fair coin flips from repeated tosses of a bent coin with unknown probability p via rejection sampling: In each round, toss the bent coin twice. Map (heads, tails) to heads and (tails, heads) to tails. For (heads, heads) and (tails, tails), repeat the process.

Since (heads, tails) has probability p*(1-p) and (tails, heads) has probability (1-p)*p, this generates the same distribution as a fair coin flip, but the process has a random running time.

1. What is the expected running time in number of rounds?
2. If you forcibly terminate the process after n rounds and return heads/tails arbitrarily, what is the bias?
3. If you're given a bound on p (say you know the bent coin is no more biased than p = 0.9) and a maximum tolerated bias for that generated output, what is the minimum value of n that reduces the bias below that level?

pervognsen

A quadratic space is a real vector space V with a quadratic form Q(x), e.g. V = R^n with Q as the squared length. The Clifford algebra Cl(V) of a quadratic space is the associative algebra that contains V and satisfies x^2 = Q(x) for all x in V. We're imposing by fiat that the square of a vector should be the quadratic form's value and seeing where it takes us. Treat x^2 = Q(x) as a symbolic rewriting rule that lets you replace x^2 or x x with Q(x) and vice versa whenever x is a vector. Beyond that Cl(V) satisfies the standard axioms of an algebra: it lets you multiply by scalars, it's associative and distributive, but not necessarily commutative.

Remarkably, this is all you need to derive everything about Clifford algebras.

Let me show you how easy it is to bootstrap the theory from nothing.

We know Cl(V) contains a copy of V. Since x^2 = Q(x) for all x, it must also contain a copy of some nonnegative reals.