Moin
Ich bastel an einem PC-programm (simulator) und muss leider folgende Integer-Gleichung (=keinerlei Kommazahlen) lösen:
ABm + Ap + Bq = c
Bekannt sind m, p, q und c. Gesucht ist irgendein A,B-Paar.
Bekannt ist ausserdem:
Alle Werte sind positive Zahlen ohne Komma.
p >> m
B >>> m
A hat die gleiche Grössenordnung wie B.
Wie macht man das möglichst schnell/elegant ?
Danke
Gilson Laurent
hi,
Ich bastel an einem PC-programm (simulator) und muss leider
folgende Integer-Gleichung (=keinerlei Kommazahlen) lösen:ABm + Ap + Bq = c
Bekannt sind m, p, q und c. Gesucht ist irgendein A,B-Paar.
Bekannt ist ausserdem:
Alle Werte sind positive Zahlen ohne Komma.
p >> m
B >>> m
A hat die gleiche Grössenordnung wie B.Wie macht man das möglichst schnell/elegant ?
ich würde umformen auf
B = (c-Ap)/(q+Am)
und dann in einer tabellenkalkulation m, p, q und c vorgeben und mir dazu zu vielen A die entsprechenden B berechnen lassen.
damit das alles positiv ist, muss der zähler übrigens positiv sein, d.h. dass c > Ap oder c/p > A sein muss.
hth
m.
Moin
ich würde umformen auf
B = (c-Ap)/(q+Am)und dann in einer tabellenkalkulation m, p, q und c vorgeben
und mir dazu zu vielen A die entsprechenden B berechnen
lassen.
Von der Idee her gut, nur leider würde das den Speicherplatz ein bisschen sprengen: m wird zwischen 500.000 und 1.500.000 schwanken. A und B werden wohl >10^150 sein. Und allein durch Stichproben komm ich mit meinem Wissen nicht weiter…
Danke.
Hallo.
Ich hätte noch die Idee, die genannte Gleichung „A*B*m + A*p + B*q = c“ mit den transponierten Matrizen von A und B (und A*B) zu multiplizieren. Es sei denn, es dürfen irgendwelche numerischen Tricks benutzt werden… ? Immerhin implizieren die >>>>,… das immerhin.
Schau’n mer mal ins Buch…
Und Matrizeninversion wäre wohl ein bisschen hart, oder ?
HTH
mfg M.L., der auch noch was dazu sucht 
Moin
Ich hätte noch die Idee, die genannte Gleichung „A*B*m + A*p +
B*q = c“ mit den transponierten Matrizen von A und B (und A*B)
zu multiplizieren.
huh ? Ich kann dir gerade nicht folgen, da fehlen mir ein bisschen die Grundlagen. Ich soll also die Zahlen A, B, A*B als Matrix darstellen (?), transponieren (OK) und dann mit der Gleichung multiplizieren(?).
Wie macht man aus einer Zahl eine Matrix ? 1x1-Matrix kann’s ja wohl nicht sein, oder ?
Und wie multipliziert man eine Matrix mit einer Gleichung ? OK, wenn ich wüsste wie die Matrixen aussehen könnte ich das noch hinbekommen. Also, wahrscheinlich…
Es sei denn, es dürfen irgendwelche
numerischen Tricks benutzt werden… ? Immerhin implizieren die
>>>>,… das immerhin.
Ich hab die Gleichung so vorgesetzt bekommen. K.A. aus was die rausfällt und wieso die Zahlen so sind wie sie sind. Das >> hab ich aus den Testzahlen geschlossen.
mfg M.L., der auch noch was dazu sucht
Ist die Formel Teil eines bekannten Problems ?
Ich weiss schon wieso ich Info und nicht Mathe studiert habe…
Danke
Hallo.
Ok, das mit dem Transponieren war wie folgt gemeint:
A*x = b (A ist unterbestimmt)
-> A(trans) * A * x = A(trans) * b (wenn das Multiplizieren erlaubt ist, ansonsten A*A(trans) rechnen !)
—> A(trans) * A = n x n - Matrix (so in etwa dargestellt…)
Aber ich befürchte wir brauchen noch ein paar Zusatzinfo’s: sind m, p, q und c Matrizen, Vektoren, einfache Zahlen, …? Welche Dimension n haben A und B ? Und ich vermute, dass eine Umformung gemacht werden soll um A und B -durch m, p, q und c ausgedrückt- exakt auszurechnen ? Irgendwelche Werte für m, p, q und c vorgegeben ? Bisheriger Kenntnisstand in Mathematik (Numerik, Algebra,…) ?
Ich hab die Gleichung so vorgesetzt bekommen. K.A. aus was die
rausfällt und wieso die Zahlen so sind wie sie sind. Das
>> hab ich aus den Testzahlen geschlossen.
toll…
Ist die Formel Teil eines bekannten Problems ?
Ich weiss schon wieso ich Info und nicht Mathe studiert
habe…
Tja, das war Dein Fehler >:wink:
Dann schreib mal fleissig
mfg M.L.
Moin
Ok, das mit dem Transponieren war wie folgt gemeint:
A*x = b (A ist unterbestimmt)
-> A(trans) * A * x = A(trans) * b (wenn das
Multiplizieren erlaubt ist, ansonsten A*A(trans) rechnen !)
—> A(trans) * A = n x n - Matrix (so in etwa
dargestellt…)
OK, den Teil hab ich verstanden, aber das bringt in dem Fall nix.
Aber ich befürchte wir brauchen noch ein paar Zusatzinfo’s:
sind m, p, q und c Matrizen, Vektoren, einfache Zahlen, …?
Alles nur positive Zahlen (ohne Komma, falls das hilft). Auch A und B sind nur einfache Zahlen, keine Matrizen.
Lass mich raten: der Begriff „Gleichungssystem“ war falsch ?
cu
*Kopf raucht wg. beschränkter Phantasie*
Mahlzeit.
Alles nur positive Zahlen (ohne Komma, falls das hilft). Auch
A und B sind nur einfache Zahlen, keine Matrizen.
…was die Sache wider Erwarten nicht einfacher macht.
Lass mich raten: der Begriff „Gleichungssystem“ war falsch ?
Eigentlich nicht. Immerhin stellt z.B. die Zahl ‚45‘ eine 1x1-Matrix dar. Aber die ganze Gleichung muss man doch irgendwie durch einen gemeinsamen Faktor kürzen können. Wenn 500.000
hi,
ABm + Ap + Bq = c
Bekannt sind m, p, q und c. Gesucht ist irgendein A,B-Paar.
wie „bekannt“ sind die? bloß (gegenseitige) größenordnung(en) oder mehr?
m.
Hallo,
die „Lösung“ eines unterbestimmten Gleichungssystems ist selbst eine Gleichung, die die Lösungspunkte erfüllen müssen. Mehr lässt sich auch nicht berechnen, daher heisst das System ja auch unterbestimmt. Um diese Gleichung zu bestimmen, sind Computer allerdings eher ungeeignet.
In diesem Fall ist die Lösungsmenge eine 2dimensionale Kurve. Würde man die Gleichung dieser Lösungskurve kennen, könnte man ihr „ansehen“, wie sie sich verhält (Minima,Maxima,Nullpunkte…) oder z.B. durch Differenzieren mehr erfahren. Da der Computer so nicht arbeitet, könnte man als Ansatz zu einer numerischen Lösung die Achsen abklappern nach zulässigen Wertepaaren, z.B. in der Reihenfolge X (bzw. A) = 0,+1,-1,+2,-2…, dann findet man kleine Zahlen zuerst und kann vor der Unendlichkeit rechtzeitig abbrechen. Das Problem ist bloss, dass das nicht funktionieren muss: eine zulässige Lösungskurve wäre z.B. eine senkrechte (=parallel zur Y-Achse) Gerade durch +Pi; da Pi nicht rational ist, würde man bei keiner beliebigen Unterteilung der X-Achse einen Punkt auf dieser Kurve finden.
Ich fürchte, zu jeder numerischen Strategie lässt sich ein solches Gegenbeispiel konstruieren. Die Schrittweite kann ja nicht beliebig klein sein, also passt ein Kreis mit kleinerem Durchmesser immer dazwischen.
Vereinfacht heisst die Aufgabe: gegeben ist eine beliebige Kurve, finde einen Punkt in der Ebene, der auf der Kurve liegt. Es gibt aber schrecklich viele Kurven und schrecklich viele Punkte auf der Ebene, und dicht daneben ist auch vorbei.
Gruss Reinhard
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Moin
Die Schrittweite kann ja
nicht beliebig klein sein, also passt ein Kreis mit kleinerem
Durchmesser immer dazwischen.
Da muss ich widersprechen: Es sind alles ganz Zahlen und ich brauchte nur eine Lösung (nicht alle). D.h. die minimale Schrittweite ist 1. Wenn man lange genug Zeit hat (und tatsächlich überhaupt eine Lösung existiert) muss ein Rechner sie durch würfeln finden.
Mir geht es um die Eingrenzung des Suchraums und die Beschleunigung der Berrechnung. Also eben um Minima, Maxima,… Und dafür reicht mein Matheverständniss nicht aus.
Aber heute ist eh Sonntag, heute wird nicht gearbeitet. Ich knobel morgen weiter. Wenn ich was hab, frag ich nochmal nach.
cu
Aber heute ist eh Sonntag, heute wird nicht gearbeitet. Ich
knobel morgen weiter. Wenn ich was hab, frag ich nochmal nach.cu
Hallo,
falls noch Interesse besteht, wie wärs mit folgenden beiden Punkten:
A = 0 | B = c/q
A = c/p | B = 0
Gruss Reinhard
Moin
falls noch Interesse besteht, wie wärs mit folgenden beiden
Punkten:
A = 0 | B = c/q
A = c/p | B = 0
Ja, kann man machen, wär die Triviallösung. Allerdings gilt :„A hat die gleiche Grössenordnung wie B“ und „A >>> m“. D.h. A und B sollten gar nicht 0 werden (oder beide 0, aber da c != 0…)
Hab einen anderen Ansatz, bin aber noch nicht ganz durch:
A*B*m + A*p + B*q = c
Da A und B viel grösser sind als alles andere muss der Term A*B viel, viel grösser sein als B*q und B*p. Ergo ist A*B ±= c.
Annahme/Näherung: AB = X, X bekannt (weil nahe c). Jetzt kann man die Gleichung in eine (eigentlich 2) quadratische Gleichung verwandeln (A^2p + AX + Xq - c = 0). Aus der kann man minima und maxima für X rausziehen. Das schränkt die Sache schonmal ein. Dann den Rechner dumm-doof Werte für X durchtesten lassen.
Da alle Zahlen ganze, positive Zahlen sind kann man aus den Formeln die möglichen Werte für X (X = A*B) nochmals einschränken (Teil der alten französiche Formel für quadratische Gleichungen):
Delta = X^2 - 4*A^2*X
Wenn das Resultat ganzzahlig sein soll muss sqrt(delta) eine rationale Zahl ergeben (siehe Frage weiter oben). Und wenn man annimmt: 4*A^2*X = Y^2, dann steht da:
Delta = sqrt (X^2-Y^2) = (X-Y)(X+Y)
Wenn aber Y (= sqrt(4*A^2*X)) irrational ist kann das nix mehr werden.
Das alles zusammen (wenn’s denn klappt) bringt mich runter von 10^299 als Suchbereich auf etwa 10^80. Noch 2-3 solche Schritte und das ganze wird hoffentlich machbar.
danke für die Anregnung.
cu
… nicht nachgedacht …
Der letzte Teil mit sqrt() war Blödsinn, das geht so nicht.
Ich sollte so spät abends keine Mathe mehr machen…
cu
Der letzte Teil mit sqrt() war Blödsinn, das geht so nicht.
Ich sollte so spät abends keine Mathe mehr machen…
cu
Hallo pumpkin,
nur abends?
Du schreibst, meine Lösungen gefallen dir nicht, weil A und B nicht in die Nähe von 0 kommen sollen - das ist eine mathematisch ganz und gar sinnleere Aussage, A und B sind die Variablen, und die lassen sich nicht von dir verbieten, dass hier die Lösungskurve die Achsen schneidet, sondern höchstens von der Gleichung selbst.
Noch schlimmer: sie lassen sich auch von dir nicht befehlen, dahin zu springen, wo du sie gerne hättest - die Gleichung beschreibt eine Hyperbel, also eine Kurve mit der Grundgleichung y = 1/x, woran man gleich sieht, dass für betragsmässig grosse x y immer kleiner wird, und umgekehrt. Wie gefordert x und y in gleicher Grössenordnung kann daher nur in der Umgebung des Nullpunkts vorkommen, wobei die Parameter bestimmen, wieweit man diese Umgebung zu verstehen hat. Die geforderten sehr grossen A und B mit A ~ B existieren daher nicht, und es ist folglich irrelevant, wieviel Rechenoperationen deine Algorithmen zu ihrer Bestimmung brauchen.
Ich hatte deine zusätzlichen Angaben zur Grössenordnung zuerst als Erwartungen verstanden - dann sind sie halt falsch. Es hört sich jetzt aber eher so an, als seien das Forderungen, aber das ist auch eine sinnleere Ausdrucksweise - laut Definition sind m,p,q und c gegeben, und an etwas Gegebenes kann man keine Forderungen stellen. Falls du das jedoch so meinst, dann sind diese Forderungen eben mit der Gleichung unvereinbar.
In jedem Fall bist du auf einem ganz falschen Dampfer.
Gruss Reinhard