Brute-Force oder Formel?

[theo]

Hallo

Ich habe hier mal eine Frage, die wohl eher theoretischer Natur ist.

Zusammengefasst: Man hat für ein überschaubares Problem eine "Brute-Force" Lösung gefunden (erschöpfende Suche).
Wie erkennt man, ob sich das Problem auch mit einer Funktionsgleichung (nennt ihr das so?) lösen lässt und wie entwickelt man die? (Ich bin in Theorie/Mathe nicht gerade bewandert).

Mein konkretes Problem ist die Steuerung der Software eines Signalgenerators.
Dieser hat im sog. "Integer-Modus" drei Parameter um die Ausgangsfrequenz zu definieren.

M: Einen Multiplikator für die Frequenz des Quarzes (Q: 25MHz). Werte sind erlaubt von 15 bis 39 (Also 375MHz bis 975MHz)
T1: Einen ersten Teiler (Mögliche Werte 4/6/8).
T2: Einen zweiten Teiler (Mögliche Werte: 0..7 werden zu 1/2/4/8/16/32/64/128).

Die Funktion soll nun eine "Wunschfrequenz" entgegennehmen und die Werte liefern für die möglichst nahe Endfrequenz.

Die Funktion mit der erschöpfenden Suche liefert also bspw. das:
Wunsch: 9.000MHz
Bestmögliches Resultat: 8.984MHz ( Q * M / T1 / 2^T2 => 25 * 23 / 4 / 2^4 )

Es geht also darum, mit den vorhandenen Einstellungsmöglichkeiten das beste Resultat zu finden.

Im Prinzip scheint das Problem recht überschaubar, sodass ich mich frage, ob man daraus eine "Formel" programmieren kann, ohne alles durchrechnen zu müssen.

Mir fehlen dazu aber das Wissen bzw. die Erfahrung. Ich kann auch nicht beurteilen, ob sich das ggf. "lohnt".

Kann hier jemand Licht hinein bringen?

Danke!

P.S. Das ist kein "echtes" Problem für mich, weil die erschöpfende Suche gut und schnell genug funktioniert.
Bei mir ist einfach diese Frage aufgekommen.

[Jorg3000]

Hi!
Habe nur Schulkenntnisse in Mathe, aber ich glaube eine Formel mit 3 Unbekannten bringt dich nicht weiter. Zumal der Wert jeder Variablen nicht eine beliebige gebrochene Zahl sein darf.

Drei verschachtelte Schleifen lösen das Problem in 600 Durchläufen (25*3*8 Möglichkeiten), was heutzutage nicht mehr der Rede wert ist. Ich würd's so machen!
Da die Brute-Force-Suche in vielen Bereichen der Informatik eingesetzt wird, hätte ich keine Sorge, dass es an dieser Stelle unprofessionell wirken würde.
Grüße, Jörg

[theo]

@Jorg3000: Danke für die Antwort.
Die "erschöpfende Suche" ist für das praktische Beispiel hier natürlich kein Problem. Für die paar Berechnungen sind Computer bzw. µC ja da!
Ich habe nur festgestellt, dass ich von Fragen dieser Art allgemein wenig Ahnung habe und wollte mir deshalb ein paar Hinweise und Ansichten dazu von euch abholen.

Danke!

[Joh]

oder, je nach Prozessor/Stromverbrauch/Formel: eine Tabelle mit den möglichen Werten erstellen und dann nach dem passenden suchen.

[Niesi]

Hallo

Ich habe hier mal eine Frage, die wohl eher theoretischer Natur ist.

...

M: Einen Multiplikator für die Frequenz des Quarzes (Q: 25MHz). Werte sind erlaubt von 15 bis 39 (Also 375MHz bis 975MHz)
T1: Einen ersten Teiler (Mögliche Werte 4/6/8).
T2: Einen zweiten Teiler (Mögliche Werte: 0..7 werden zu 1/2/4/8/16/32/64/128).

Die Funktion soll nun eine "Wunschfrequenz" entgegennehmen und die Werte liefern für die möglichst nahe Endfrequenz.

Die Funktion mit der erschöpfenden Suche liefert also bspw. das:
Wunsch: 9.000MHz
Bestmögliches Resultat: 8.984MHz ( Q * M / T1 / 2^T2 => 25 * 23 / 4 / 2^4 )

...

Kann hier jemand Licht hinein bringen?

Danke!

P.S. Das ist kein "echtes" Problem für mich, weil die erschöpfende Suche gut und schnell genug funktioniert.
Bei mir ist einfach diese Frage aufgekommen.

Hallo Theo,

ich wüsste nicht, das es für solche eine Anwendung eine Gleichung gibt, denn es ist keine Funktion in dem Sinne von y = f(x) oder auch y = f(x, w, z). Es gibt auch nur eine "Unbekannte", nämlich die sich ergebende Frequenz mit der geringsten Abweichung. Du hast es hier mit Kombinationen oder Variationen zu tun - und da ist Deine Lösung sicher das beste. Eine Gleichung gibt es nur für die Anzahl der möglichen Lösungen - die hat Jörg ja schon gezeigt.
Klar, eine Tabelle ginge auch - jedoch muss auch in einer Tabelle jeder Wert mit dem Wunschergebnis verglichen werden. Und dann kann ich es auch mit Schleifen lösen und sicher sein, jeden möglichen Wert zu beachten. In einer Tabelle kann auch mal ein Wert fehlen oder falsch sein.
Und ich nenne Deine Methode auch nicht "Bruce Force Methode", da das eigentlich eine "Rohe Gewalt Methode" ist - Du kombinierst aber alle Möglichkeiten und suchst dann die beste davon heraus. Das wird zum Beispiel bei Getrieben genauso gemacht, da gibt es nur ganzzahlige Zähnezahlen und Du musst die finden, welche am besten zur verlangten Übersetzung passen ...

Besten Gruß
Harald

https://www.mathebibel.de/kombinatorik

https://www.zum.de/Faecher/Materialien/ ... ombin.html

https://de.wikipedia.org/wiki/Brute-Force-Methode

[Socke]

Klar, eine Tabelle ginge auch - jedoch muss auch in einer Tabelle jeder Wert mit dem Wunschergebnis verglichen werden. Und dann kann ich es auch mit Schleifen lösen und sicher sein, jeden möglichen Wert zu beachten. In einer Tabelle kann auch mal ein Wert fehlen oder falsch sein.

Die möglichen Eingabegrößen sind ja bekannt. Damit lässt sich die Tabelle zu Programmstart erstellen. Die Liste sollte nach Zielfrequenz sortiert sein und die drei Eingabegrößen zurückgeben. Dann findet man über eine binäre Suche sehr schnell das gewünschte Ergebnis.

[Niesi]

Ok, das geht - machst Du mit Schleifen. Und wenn Du in den Schleifen auch noch das am besten passende Ergebnis ermittelst, dann brauchst Du hinterher nicht suchen ...

Edit: wenn das in einer Anwendung oft gemacht werden muss: klar, dann ist eine Tabelle sicher schneller - und die Idee, sie am Anfang zu erzeugen, gut.

[theo]

Danke für alle Antworten. Sehr interessant und lehrreich!

Klar wäre eine Tabelle (noch) schneller, aber man sollte auch noch den Faktor (S)RAM bedenken.
Ein Arduino Uno (oder Nano), welchen man durchaus zur Steuerung so eines Signalgenerators verwenden kann, hat davon bspw. gerade einmal 2kB (Harvard Architektur) afaik.
Das wird dann schnell einmal eng.
Vielleicht würde man die Tabelle in diesem Fall besser direkt in den Code schreiben (Flash Memory / 32kB ).
Nur so als Anmerkung. Bin momentan nicht damit "unterwegs".

Danke!

[Warf]

Ob was einfach zu lösen ist oder nicht kommt immer auf das problem an, du beschreibst hier ein optimierungsproblen, also für ein gegebenes Ergebnis R finde M, T1, T2 sodass (Q * M / T1 / 2^T2) - R (absolut) minimal wird unter dem Ungleichungssystem der Wertebreiche die du angegeben hast.

Ist ein bisschen her als ich das gelernt habe, aber wenn ich mich richtig erinnere, unterscheidet man grob in Linear, Quadratische und Nicht Lineare Optimierungsprobleme. Du hast hier eine Exponentialfunktion drin, also ist das schon mal generell nicht ninear. Und wenn ich mich richtig erinnere ist da die faustregel einfach: "Pech gehabt". Es kann aber sein das es hierfür Numerische Approximationen und Lösungswege gibt die ich einfach nicht kenne. Nur weil was nicht optimal lösbar ist heist es nicht das es nicht im Durchschnitt besser als brute force gelöst werden kann.

Das gesagt, dein Lösungsraum ist so klein, das Bruteforce kein problem sein sollte

PS: Für solche Probleme gibt es tatsächlich auch gerne Solver bibliotheken und Programme die so etwas lösen können. Z3 ist z.B. ein SMT (SAT Modulo Theroy) solver (für den ich schon länger mal bindings für FPC bauen wollte), der Lineare Integer Theorie kann, und lineare (un)gleichungssyteme tatsächlich lösen kann. Aber wie gesagt durch deinen Exponenten da drin glaube ich hast du kein glück mit sowas

[theo]

Danke auch an Warf.

Gut, ich nehme mit, dass für solche Probleme mit kleinen Lösungsmengen eine pragmatische Herangehensweise auch "theoretisch" akzeptabel oder gar unumgänglich ist.

Die Tabelle ist eine Optimierungsmöglichkeit, welche je nach Zusammensetzung des Systems/Hardware zu beurteilen ist.
Ich bleibe wahrscheinlich bei der Funktion ohne Tabelle, da die Berechnung hier ein vergleichsweise seltenes Ereignis darstellt und RAM bei µC nicht im Überfluss vorhanden ist.

Danke nochmals an alle für den theoretischen Hintergrund.

[six1]

Das musst du doch nicht im uC berechnen.
Erstelle eine Tabelle mit Frequenzen und Teilern und übernehme diese in das eeprom.
Du brauchst dann nur noch die nächst liegende Frequenz in der Tabelle finden und hast die Teiler Einstellungen dazu.

[theo]

@six1: Danke, aber das passt schon so.

Hab's gemessen. Der µC benötigt 22ms für die vollständige Berechnung. Das ist schnell genug für eine sporadisch vom User ausgelöste Aktion.
Ich werde keine Zeit in die diesbezügliche Optimierung mehr investieren, da es für mich keinen spürbaren Unterschied machen würde.

Sowieso war das Thema hier eher allgemeiner/theoretischer Natur.
Das "Problem" war eigentlich vorher schon gelöst.