ubuntuusers.de

Ich suche nach einem Algorithmus, mit dem man, wenn möglich, das Verhältnis zweier Zahlen als Bruch zweier ganzer Zahlen darstellen kann, wobei das die kleinst möglichen Zahlen sein sollen. Um das zu verdeutlichen mal ein Beispiel aus der Praxis:

48000:44100 => 160:147

Gibt es so etwas?

Du willst also einfach den gekürzten Bruch haben, richitg? In welcher Sprache soll's denn sein?

Im Endeffekt musst Du beide Zahlen in ihre Primfaktoren zerlegen und bei beiden Zahlen vorkommende Faktoren streichen...

Man kann es rekursiv lösen:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def ggt (z: Int, n: Int) : Int = {
  if (n == 0) { println ("Div by zero"); ??? }
	if (z == 0 || n == 1 || z == 1) z else 
	if (n > z) ggt (n, z) else
	if (z % n == 0) n else 
	ggt (n, z % n)
}

def kuerzen (z: Int, n: Int) : (Int, Int) = {
  val faktor = ggt (n, z) 
  (z/faktor, n/faktor) 
}

kuerzen (196, 63)
// res9: (Int, Int) = (28, 9)

Hoppla - sehe, für (0/7) fehlt in kuerzen noch das Auffangen der 0 um auch dort div/0 zu verhindern.

In C gibts das auch im FFmpeg Sourcecode: https://github.com/FFmpeg/FFmpeg/blob/master/libavutil/rational.h

Dakuan schrieb:

Ich suche nach einem Algorithmus, mit dem man, wenn möglich, das Verhältnis zweier Zahlen als Bruch zweier ganzer Zahlen darstellen kann, wobei das die kleinst möglichen Zahlen sein sollen. ...

Gibt es so etwas?

Ja, schau mal hier → die Geschichte mit dem größten gemeinsamen Teiler.
Brauchst Du gar nicht neu zu erfinden, sondern kannst du direkt dort abschreiben. (oder ggf. umschreiben)

LG,

track

Also das mit der Primfaktor Zerlegung ist mir auch eingefallen, aber das hätte bedeutet, dass ich auch noch einen Primzahlgenerator irgendwo abschreiben muss.

Von Euklid hatte ich in meiner Schulzeit schon mal etwas gehört, aber diesen Algorithmus kannte ich noch nicht (da war ich wohl geistig abwesend). Ist aber genial einfach, genau das was ich gesucht hatte.

In C gibts das auch im FFmpeg Sourcecode:

Die wollen wohl auch Abtastraten umwandeln.

Danke an alle Beteiligten!

Dakuan schrieb:

In C gibts das auch im FFmpeg Sourcecode:

Die wollen wohl auch Abtastraten umwandeln.

Rationale Zahlen gibts leider in wenigen Sprachen direkt eingebaut und sind in einigen Fällen deutlich komfortabler, als alles in Int umzurechnen und vor allem genauer als Float/Double. Und bei rationalen Zahlen kommt man dann automatisch zum Kürzen.

MisterIgo schrieb:

Rationale Zahlen gibts leider in wenigen Sprachen direkt eingebaut und sind in einigen Fällen deutlich komfortabler, als alles in Int umzurechnen und vor allem genauer als Float/Double. Und bei rationalen Zahlen kommt man dann automatisch zum Kürzen.

Ruby hat das z.B.

1
2
3
4

$ ruby -r rational -e 'p Rational(10,6)'
(5/3)
$ ruby -r rational -e 'p(10.to_r/6)'
(5/3)

Hatte ich schon mal erwähnt, dass Ruby die coolste Skriptsprache ist? 😉

Naja - wenn es nicht eingebaut ist, dann schreibt man es sich selbst. Eine praktische Übung beim Erlernen einer neuer Sprache ist es sowieso.

Hatte ich schon mal erwähnt, dass Ruby die coolste Skriptsprache ist? 😉

Nicht direkt, aber ich hatte es bereits vermutet.

Dakuan schrieb:

Hatte ich schon mal erwähnt, dass Ruby die coolste Skriptsprache ist? 😉

Nicht direkt, aber ich hatte es bereits vermutet.

😀