Electronic – Does anyone remember this article about the Euclidean Algorithm


In the 70's I had a stack of old Amateur Radio magazines (50s-60s), and for a long time I saved an article about using the Euclidian Algorithm to combine a number of resistors to achieve a specific value. Does anyone recall and have a copy of this article, or know how the Euclidean algorithm is applied to solve this problem?

Best Answer

It's actually based on the theory of continued fractions, which is closely related to Euclid's method for finding the GCD between two numbers.

Here's an example: Suppose you have a bunch of 10K precision resistors, and you need a resistance value of 27K for your project. You need some combination of the 10K resistors in series and/or parallel to produce that resistance.

Start by writing the ratio of the two resistances:

27K / 10K = 2.7

This means you need two resistors in series with some combination that gives 0.7 of a resistor.

Using the concept of continued fractions, you can rewrite the number 2.7 as 2 + 1/1.42857. Furthermore, you can break up the number 1.42587 into 1 + 1/2.3333.

Now, if you look at the first fraction again, it can be written as

$$\frac{1}{1.42857} = \frac{1}{\frac{1}{1}+\frac{1}{2.3333}}$$

Note that this happens to be the expression for two resistors in parallel; in this case, one resistor in parallel with 2.3333 resistors.

How do you come up with 2.333 resistors? You could iterate through the algorithm again, but it should be obvious by inspection that you need two resistors in series with the parallel combination of three more resistors. The final network ends up looking like this, and it has a resistance of exactly 27K.


simulate this circuit – Schematic created using CircuitLab

Obviously, not all examples will work out this nicely. In general, you have to decide when to stop iterating based on when the precision of the network you have so far is "close enough".

The generalized form of the algorithm goes like this: Determine the ratio X = Rdesired / Ravailable. Write X as a continued fraction, where A, B, C, D, E, etc. are all integers:

$$X = A + \frac{1}{B + \frac{1}{C + \frac{1}{D + \frac{1}{E + \frac{1}{...}}}}}$$

Build your network with

  • A resistors in series with ...
  • B resistors in parallel with ...
  • C resistors in series with ...
  • D resistors in parallel with ...
  • E resistors in series with ...

... and so on, until you either get a sub-expression that has no fractional part, or you get "close enough" to the desired result.

Note that if X is less than one to begin with, then A will be zero, which simply means that you're starting out with a parallel combination of resistors and proceeding from there. Note also that as long as X is a rational number, the sequence of continued fractions will be finite.