Doubling is cheaper than adding

A term of the expansion asks for $m\alpha + n\beta + \varphi$, and the gadgets supply addition, negation and doubling. Getting from those to an arbitrary whole-number multiple is a small piece of arithmetic with a surprising answer.

The obvious way, and what it costs #

Multiply by $n$ by adding the angle to itself $n-1$ times. Each addition is a mean and a reflector — two gadgets, five bars, three joints. For $n = 8$ that is seven additions, fourteen gadgets, thirty-five bars.

That is the construction anybody writes first, and it is linear in $n$. For a curve of degree five it would mean multiplying up to five, which is four additions, and nobody would notice. It matters here for a different reason: it is the wrong shape, and the right shape says something about what these machines are.

Doubling is one gadget #

The reflector reflects an input in a mirror, and both of its arguments are angles. Give it the input $0$ — the frame direction, a link that is simply bolted down — and the mirror $\theta$, and the output is

$$2\theta - 0 = 2\theta.$$

One reflector. Three bars, one rail, two joints. A doubling costs less than half an addition, because the mean is not needed: there is only one angle going in.

That single observation reorganises everything, because a whole number can be reached by doubling and adding one. Write $n$ in binary and walk it: $2k$ is one doubling of $k$, and $2k+1$ is one addition of $k$’s result and the original angle. The number of steps is the number of bits, not the size of the number.

The jaggedness is the point #

Look along that lower line and it does not rise smoothly.

Eight costs three gadgets — double, double, double. Seven costs six — reach six by doubling three, and three by adding two and one, with an addition at each odd step. Seven is smaller than eight and costs twice as much, and the same happens at every power of two: sixteen is four gadgets and fifteen is eight.

This is the ordinary behaviour of addition chains and it is not a quirk of the mechanism. What is worth noticing is that a linkage is showing it. The cost of a mechanical operation is following the binary representation of a number, which is not something a bar knows about; the connection runs through the fact that the only two operations available compose the way arithmetic composes.

The site has met a related pattern once before, in a different field. A clock train is a factorisation: a ratio of 3600:1 is realised as a product of tooth ratios, and which factorisation is chosen decides how many wheels the movement has. There the arithmetic is multiplicative and the mechanism is gears; here it is additive and the mechanism is rhombi. Both are cases of a machine’s size being set by a number-theoretic property of its specification rather than by the specification’s magnitude.

Negation, and the sign that costs one gadget #

Half the frequency pairs in a typical expansion have a negative entry — the cubic’s include $(1,-2)$ and $(2,-1)$ — so negation is not an afterthought.

It is one reflector: reflect the input in the frame direction and the output is $-\theta$. The same three bars and a rail that double, wired the other way round, with the roles of mirror and input exchanged. Whether a gadget doubles or negates is a fact about which of its two arguments is the moving one, and the two machines are identical objects.

There is a small piece of bookkeeping in it worth stating because the compiler gets it right and a reader working by hand would not. A negative multiple $-k$ is built as the negation of $+k$, so it shares the whole chain that produced $+k$ and adds one gadget. A machine needing both $2\beta$ and $-2\beta$ therefore contains one doubler and one negator, not two doublers. On the cubic that saves five gadgets out of twenty-three.

The alternative — building $-k$ directly by negating first and then doubling — costs the same and produces a different machine. Both are correct and the compiler picks one and stays with it, because a construction that made a different choice on different runs would produce different bar counts for the same curve, and every count in this field would then be a count of whichever machine happened to be built that day.

Sharing, which is where the real saving is #

A curve of degree $d$ needs multiples of $\alpha$ up to $d$ and multiples of $\beta$ up to $d$ — but it needs several of them, and it needs some of them more than once.

The cubic’s eight terms use the frequency pairs $(0,1)$, $(1,0)$, $(0,3)$, $(1,-2)$, $(1,2)$, $(2,-1)$, $(2,1)$ and $(3,0)$. Written out, that is: $\alpha$ once, $2\alpha$ twice, $3\alpha$ once, $\beta$ once, $2\beta$ twice, $3\beta$ once. If each term built its own multiples the machine would contain three separate doublers producing $2\alpha$.

It contains one. The multiples are computed once and shared, cached by which multiple they are, and every term that needs $2\alpha$ takes the same link. That is the ordinary optimisation any compiler makes — a shared subexpression — and it is available here because a link at a fixed pivot can be an input to any number of gadgets at that pivot without being copied.

A link is a value that can be read many times. That is the one respect in which a linkage behaves like a program, and it is worth naming because so much of this field is about the respect in which it does not: a link cannot be read anywhere but at its own pivot, and every reading somewhere else costs a parallelogram per unit of distance.

What the arithmetic costs in total #

Add it up for the largest machine in this field’s catalogue.

The quintic’s eighteen terms use frequencies up to five in each variable. Computing $1$ through $5$ of each by doubling and adding, sharing everything shareable, comes to twenty-four reflectors and a handful of means — call it a hundred bars including the rigid offsets that set each term’s phase and length.

The machine has four hundred and thirteen bars.

So the arithmetic is a quarter of the smallest useful machine and a quarter of the largest, and in between it is falling as a fraction. The growth rates are the reason: the arithmetic goes like the number of distinct multiples, which is $2d$, times the bits in each, which is $\log d$. The transport goes like the square of the number of terms, which is $d^4$.

The algebra of a high-degree curve is not what makes its machine large. Nothing in this rung is a bottleneck. It is here because the absence of a bottleneck is the finding — the natural suspicion, that a construction producing four-hundred-bar machines must be doing something expensive with the arithmetic, is wrong, and knowing that it is wrong is what points at the transport.

A machine with no loops in its arithmetic #

There is a structural fact hiding in the sharing that is worth surfacing, because it makes the arithmetic half of a compiled machine an unusually simple object.

The multiples form a tree. $2\alpha$ is built from $\alpha$; $4\alpha$ from $2\alpha$; $3\alpha$ from $2\alpha$ and $\alpha$. Nothing is ever built from something that was built from it, because the numbers strictly decrease at every step of the recursion. So the arithmetic part of a compiled machine is a directed acyclic graph of gadgets, each determinate, each reading links that already exist.

That is why the whole thing can be placed joint by joint rather than solved as a system. Given the arm, every gadget’s output is fixed by parts already in place; given every term’s link, every chain vertex is fixed by the one before it. A compiled machine of two hundred and forty joints unwinds completely, and the only thing in it that has to be solved as a pair is the arm and the parallelogram that carries $\beta$ home.

The topology field has spent a phase on exactly this question — which subchains cannot be taken apart into dyads — and its smallest example is the four-bar, at four links. A compiled machine is a thousand times larger and structurally trivial, which is a pairing of adjectives worth keeping: size and structural depth are different axes, and this field’s machines are extreme on one and unremarkable on the other.

Two things the multiplier cannot do #

It cannot multiply by a non-integer. Nothing in the doubling-and-adding scheme reaches $\alpha/2$ or $\pi\alpha$. The mean gadget produces a half — it is a bisector, after all — but its output is a line rather than a link of known length, and the construction that turns a bisector into a usable input runs straight into the reflector’s singularity at exactly the wrong place. In any case the expansion only ever asks for integers, which is the whole reason the arm’s coordinates were written as Laurent polynomials: exponents add, and adding whole numbers gives whole numbers.

It cannot multiply an angle that is not a link at its own pivot. Every gadget in the chain reads links from one point, so a multiplier is built where its input is, and its output is a link from that same point. Moving the result anywhere is transport.

Both restrictions are consequences of the same fact and neither is a limitation of this particular construction. A bar states a distance; a rhombus states an angle relation between links sharing a vertex; and integer arithmetic on angles at a common pivot is the largest vocabulary those two sentences support.

Where an integer multiple already appears on this site #

Angle multiplication by whole numbers is not new here, and the three places it has appeared are worth putting side by side, because they use three different mechanisms for the same relation and none of them can be swapped for another.

A gear pair multiplies an angle by the ratio of its tooth counts, which is a rational number and is exact — an integer count is the only thing in the subject that cannot drift. It is the cheapest angle multiplier there is, one pair of wheels, and it is unavailable here: a universality result for linkages that used gears would be answering a question nobody asked.

A planetary train multiplies by a ratio that is a difference of counts, and can reach a hundred to one from a difference of one. Also gears, also unavailable, and it is the standard example of a mechanism whose ratio is not the ratio of anything that can be pointed at.

A chain of rhombi multiplies by a whole number using nothing but bars and pins. It is far more expensive than either of the others per unit of multiplication and it is the only one made of the parts this construction is allowed.

The comparison is worth making because it locates what the constraint actually is. There is no difficulty multiplying an angle exactly; there is a difficulty doing it with lower pairs of one kind. Every awkwardness in this field traces back to a self-imposed restriction, and the restriction is what makes the result mean anything.

What a multiple looks like when it is running #

A doubler is three bars and a rail, and watching one is the quickest way to see why the arithmetic is exact.

The readout on that figure is the departure — the output angle minus the closed form — and it stays at $10^{-13}$ at every stop. Nothing about it is fitted. A rhombus has four equal sides at every position it can occupy, so the bisection is exact at every position, and the only error is the solver’s.

That the exactness survives chaining is the claim this rung actually makes, and it is checked at the level of the whole machine rather than gadget by gadget. The compiled machine for a quintic contains twenty-four reflectors in stacks up to five deep, and its tracing point satisfies the polynomial to $8.1\times10^{-13}$. Errors that compounded would show there.

The exactness is not fragile in the way chaining usually is #

There is a general reason to distrust a stack of exact relations: exact relations composed numerically are not exact, and a chain five deep multiplying errors by anything would arrive somewhere useless.

That is not what happens, and the reason is worth naming. Every gadget’s relation is enforced by bar lengths, and the bar lengths do not change as the machine runs. A doubler’s rhombus has four sides of length $s$ at every configuration, so it bisects at every configuration; the fact that its input came from another doubler is invisible to it. Errors do not accumulate through the chain because nothing in the chain is computing anything — the whole assembly is solved at once, as one system of constraints, and the only error anywhere is the residual of that solve.

That is a different situation from a numerical pipeline, where each stage consumes the previous stage’s output and inherits its error. A linkage has no stages. It has one configuration, satisfying all its constraints simultaneously, and the depth of the notional computation is a fact about how the constraints were chosen rather than about how they are solved.

The measurement bears it out: five deep on the quintic, and the tracing point sits at $8.1\times10^{-13}$.

Where the number theory stops #

One caution, since the binary expansion is a tempting thread to pull.

Finding the shortest addition chain for a number is a hard problem in general and it does not matter here, because the numbers are small. A curve of degree five needs multiples up to five and the binary route is optimal or within one gadget of optimal for every integer that small. A hypothetical curve of degree fifty would want more care, and a curve of degree fifty is a machine with something like six million bars, so the care would be misplaced.

The honest statement is that the arithmetic is not the constraint, at any degree anybody would compile, and that optimising it is optimising a quarter of a machine whose other three quarters grow twice as fast. The place to look for a smaller universality construction is the transport, and the reason nobody has made the transport cheap is that it is not a shortcoming of the method but a property of what a bar can say.

What this rung leaves for the next one #

Every piece is now in hand. Two angles arrive from an arm. Integer multiples of each are built by doubling and adding, shared where they can be. Each term’s frequencies are combined by an addition, and one triangular link applies the phase angle and the length. The results are carried out along a chain and added head to tail, and the last vertex is held on a line.

The next rung assembles that, positions every joint by a converged solve, drives it, and asks the one question none of its constraints can answer: where is its tracing point, and is the polynomial zero there.

The answer is a number at the floor of double arithmetic, on every curve tried, over the whole of each machine’s working arc. What the phrase working arc is doing in that sentence is the subject of two rungs after it, and it is the honest half of the field.

The cost following the binary expansion rather than the size is the finding, and it has a design reading worth separating from the arithmetic. A designer choosing a multiple should choose one with few ones in it. Multiplying by eight costs three gadgets and multiplying by seven costs six, so a construction that can tolerate a factor of eight where it wanted seven has bought a halving for nothing. That is an unusual kind of design freedom — a discrete cost that is not monotone in the quantity — and it is the same shape as a reverted train’s non-monotone tooth counts and a compound epicyclic’s sparse reductions. In all three the useful instruction is the same: find out what latitude the requirement has before choosing the number, because the cost varies wildly between neighbours and the neighbours are usually acceptable.