Skip to content

Instantly share code, notes, and snippets.

Per Vognsen pervognsen

Block or report user

Report or block pervognsen

Hide content and notifications from this user.

Learn more about blocking users

Contact Support about this user’s behavior.

Learn more about reporting abuse

Report abuse
View GitHub Profile
pervognsen / gist:9503919
Created Mar 12, 2014
earley/cyk duality
View gist:9503919
Anyway, onward to the duality. Using Haskell-style notation for types,
notice that cyk :: (Int, Int) -> Bool and earley :: Int -> Set Int.
Curry cyk's type to get (Int, Int) -> Bool = Int -> (Int -> Bool). But
this Int -> Bool is just the indicator function of a set. (In fact, we
are dealing with bounded integers here, so it's isomorphic to a
Boolean array.) This gives a natural type-level isomorphism between
CYK and Earley that already hints at some of the differences and
similarities between the two algorithms. For example, you'd expect a
specialized set data type (e.g. a hash table or balanced tree) to be
superior for representing sparse sets. In contrast, the blackbox
View gist:9506986
>ok, here's my overview on how to do lagrangian mechanics, hamiltonian
>mechanics, quantum mechanics, statistical mechanics, symplectic
>geometry, contact geometry, calculus of variations, dynamic
>programming, and feynman path integrals.
>dynamic programming teaches us to multiply matrixes of "transition
>costs" using a weird sort of "linear algebra" in which the role of
>addition is played by minimization of costs, and the role of
>multiplication is played by addition of costs. when this technique is
View gist:9800778
For given values of x and y, define the following function of a real parameter t:
f(t) = cos(tx) cos(x + y - tx) - sin(tx) sin(x + y - tx)
Note that f(0) = cos(x + y) and f(1) = cos(x) cos(y) - sin(x) sin(y), so this is a
smooth deformation between the two sides of the cosine addition formula. The addition
formula will follow if we can prove df/dt = 0. Let us compute:
d/dt cos(tx) cos(x + y - tx) = -sin(tx) cos(x + y - tx) + cos(tx) sin(x + y - tx))
d/dt sin(tx) sin(x + y - tx) = cos(tx) sin(x + y - tx) - sin(tx) cos(x + y - tx)
View gist:9866317
8.7 Circle through a point P and tangent to a line L with a given radius R.
Their solution: Three pages of formulas and two pages of code.
Geometric solution: The circle center C must lie on the circle with
center P and radius R and on the line resulting from displacing L by
distance R towards P. This is just a circle vs line intersection problem.
View gist:9866444
8.5. Lines tangent to two circles
Their solution: Are you fucking kidding me?
Geometric solution: Let the circles have centers A and B with radii a < b.
Consider an inner tangent with contact points P and Q. The intersection C of
PQ and AB defines a pair of similar right triangles APC and BQC with ratio a/b.
Thus C is the barycentric combination of A with weight b and B with weight a.
The case of outer tangents is similar. This reduces the problem to finding
tangents to a circle through a point (section 8.3).
View gist:9890590
Let D be a finite-dimensional real division algebra.
For any element x of D, we have an associated endomorphism on D that acts by left multiplication.
Since the endomorphism algebra over a finite-dimensional vector space is itself finite dimensional,
the elements 1, x, ..., x^m must eventually develop a linear dependency if we choose m sufficiently
large. Thus there exists real numbers a_i such that
a_0 + a_1 x + ... + a_m x^m = 0
Considering this as a real polynomial, we get a factorization into linear and irreducible quadratic
View gist:9887146
Every time we say 'polynomial' we will mean a polynomial with real coefficients.
Suppose f is a polynomial that is everywhere non-negative, i.e. f(x) >= 0 for all x.
We may assume f is monic. Indeed, we can divide by any positive number
without changing the matter, and after such normalization the leading
coefficient cannot be -1 or f would assume negative values for large enough x.
First suppose f factors completely into linear parts:
pervognsen / gist:9982014
Last active Aug 29, 2015
Variational formulation of SVD without Lagrange multipliers
View gist:9982014
Let V and W be inner product spaces and let T : V -> W be a linear map.
Define a bilinear form B : V x W -> R by B(v, w) = <T(v), w> = <v, T*(w)> and consider its
restriction to the unit spheres in V and W. Since B is continuous and the unit spheres are
compact, it must attain its maximum there. We have <T(v), w> = ||T(v)|| ||w|| cos(T(v), w)
where the two-argument cos denotes the cosine of the angle between two vectors. For fixed v,
B(v, w) is maximized by varying w so as to maximize the cosine factor since ||w|| = 1 is constant.
But the cosine is greatest when the angle is least, reaching zero when T(v) and w are collinear.
Thus at a maximum (v, w), which we know exists, we must have T(v) = ||T(v)|| w. Using the transposed
formula <v, T*(w)>, we also get T*(w) = ||T*(w)|| v. Finally, ||T(v)|| ||w|| = ||v|| ||T*(w)||
View blah.cpp
template<typename C, typename D, typename... Args>
auto make_resource(C constructor, D destructor, Args&&... args)
return std::make_unique_ptr(constructor(std::forward<Args>(args)...), destructor);
pervognsen / gist:11145747
Last active Aug 29, 2015
View gist:11145747
Let's say the cost to shuffle is C1 and the cost to press next/previous is C2,
Consider the space of songs as a continuous interval of length L.
Then the task is to select a strategy parameter r that defines the
radius of attraction: when you get within distance r, you switch to
using next and previous to converge to the target.
Dimensional analysis solution:
The relevant constants are C1, C2 and L, and r is an unknown parameter
You can’t perform that action at this time.