Erinnert sich jemand an diesen Artikel über den euklidischen Algorithmus?

20

In den 70er Jahren hatte ich einen Stapel alter Amateurfunk-Magazine (50er-60er Jahre) und lange Zeit habe ich einen Artikel über die Verwendung des Euklidian-Algorithmus gespeichert , um eine Reihe von Widerständen zu kombinieren, um einen bestimmten Wert zu erreichen. Erinnert sich jemand an diesen Artikel und hat eine Kopie davon oder weiß, wie der euklidische Algorithmus angewendet wird, um dieses Problem zu lösen?

Gene M.
quelle

Antworten:

38

Es basiert tatsächlich auf der Theorie der fortgesetzten Brüche , die eng mit Euklids Methode zum Auffinden der GCD zwischen zwei Zahlen verwandt ist.

Hier ein Beispiel: Angenommen, Sie haben eine Reihe von 10K-Präzisionswiderständen und benötigen einen Widerstandswert von 27K für Ihr Projekt. Sie benötigen eine Kombination der 10K-Widerstände in Reihe und / oder parallel, um diesen Widerstand zu erzeugen.

Schreiben Sie zunächst das Verhältnis der beiden Widerstände:

27 K / 10 K = 2,7

Dies bedeutet, dass Sie zwei Widerstände in Reihe mit einer Kombination benötigen, die 0,7 eines Widerstands ergibt.

Unter Verwendung des Konzepts der fortgesetzten Brüche können Sie die Zahl 2.7 als 2 + 1 / 1.42857 umschreiben. Außerdem können Sie die Zahl 1.42587 in 1 + 1 / 2.3333 aufteilen.

Wenn Sie sich den ersten Bruch noch einmal ansehen, kann er wie folgt geschrieben werden

11.42857=111+12.3333

Beachten Sie, dass dies der Ausdruck für zwei parallele Widerstände ist. in diesem Fall ein Widerstand parallel zu 2.3333 Widerständen.

Wie kommen Sie auf 2.333 Widerstände? Sie könnten den Algorithmus erneut durchlaufen, aber es sollte sich bei der Überprüfung herausstellen, dass Sie zwei Widerstände in Reihe mit der Parallelkombination von drei weiteren Widerständen benötigen. Das endgültige Netzwerk sieht dann so aus und hat einen Widerstand von genau 27K.

schematisch

simulieren Sie diese Schaltung - Schaltplan erstellt mit CircuitLab

Offensichtlich funktionieren nicht alle Beispiele so gut. Im Allgemeinen müssen Sie entscheiden, wann Sie die Iteration beenden möchten, basierend darauf, ob die Genauigkeit des Netzwerks, über das Sie bisher verfügen, "nahe genug" ist.

Die verallgemeinerte Form des Algorithmus lautet wie folgt: Bestimmen Sie das Verhältnis X = R erwünscht / R verfügbar . Schreiben Sie X als fortgesetzten Bruch, wobei A, B, C, D, E usw. ganze Zahlen sind:

X=EIN+1B+1C+1D+1E+1...

Bauen Sie Ihr Netzwerk mit

  • Ein Widerstände in Reihe mit ...
  • B-Widerstände parallel zu ...
  • C-Widerstände in Reihe mit ...
  • D Widerstände parallel zu ...
  • E-Widerstände in Reihe mit ...

... und so weiter, bis Sie entweder einen Unterausdruck erhalten, der keinen Bruchteil enthält, oder Sie dem gewünschten Ergebnis "nahe genug" kommen.

Beachten Sie, dass wenn X zu Beginn kleiner als Eins ist, A Null ist, was einfach bedeutet, dass Sie mit einer parallelen Kombination von Widerständen beginnen und von dort aus fortfahren. Beachten Sie auch, dass die Folge fortgesetzter Brüche endlich ist, solange X eine rationale Zahl ist.

Dave Tweed
quelle
Diese Konstruktion (bei Verwendung gleichwertiger Widerstände) wird als Stern-Brocot-Baum- Approximation bezeichnet. Ich frage mich allerdings, wie ich es auf mehr als einen Wert im Teilebehälter verallgemeinern kann ...
Fizz