Lineare Funktion implementieren

[Chandler B. (chandler)]

Hallo,

ich stehe gerade auf dem schlauch eine funktion in c zu entwickeln. Die 
Sprache ist hierbei sogar noch egal.

ich habe zwei Punkte (-5|0)(25|100) und möchte hier eine lineare 
Funktion zu bilden um dazwischen die Werte zu ermitteln.

Jetzt sehe ich nur die Möglichkeit zunächst die steigung M zu berechnen, 
dann den Y-Achsenabschnitt B um damit die Gleichung zu bekommen, mit der 
ich den gewünschten Punkt berechnen kann.

uint8 m, b, y;
m = (100 / (25 - (-5)); // = 3,3333 (uint8) = 3
b = m * (-(-5)); // = 16,6666 (wegen uint8  = 15)
y = m * x + b;
return y;

das ganze würde funktionieren (wenn auch sehr ungenau, oder ich würde 
die Datentypen auf real abändern). Aber muss ich wirklich erst m und b 
berechnen? Oder gibt es da nicht eine einfachere Lösung zu?

[Oliver S. (oliverso)]

https://de.wikipedia.org/wiki/Geradengleichung

Such dir halt eine Form der Geradengleichung aus, die dir am besten 
gefällt.

Oliver

[Ingo L. (corrtexx)]

Rechne es doch einfach in float oder scaliere um den Faktor 10 höher, 
wenn es unbedingt in 8-Bit ausgeführt werden soll und teile das Ergebnis 
später wieder durch 10

[Rolf M. (rmagnus)]

Ingo L. schrieb:
> Rechne es doch einfach in float oder scaliere um den Faktor 10 höher,
> wenn es unbedingt in 8-Bit ausgeführt werden soll und teile das Ergebnis
> später wieder durch 10

Faktor 10 wird bei einem Wert von 100 und 8 Bit schwierig. Aber ja, 
float bzw. double würde sich anbieten, gerade auf dem PC.

[A. S. (rava)]

https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

noch nicht benutzt, aber kommt ohne division oder multiplikation aus. 
Kann aber natürlich nur Werte an integer-x-stellen ermitteln

[Christoph S. (mr9000)]

Auch wenn es aus der Arduinowelt kommt, finde ich das hier sehr 
nützlich:

int32_t map(int32_t x, int32_t in_min, int32_t in_max, int32_t out_min, 
int32_t out_max) {
  return (x - in_min) * (out_max - out_min) / (in_max - in_min) + 
out_min;
}

bei dir wäre
in_min = -5
in_max = 25
out_min = 0
out_max = 100
und x der Wert den du haben willst. Mit Integergenauigkeit beim Rechnen 
und ohne zwischenspeichern (mit Fließkomma!) von Steigung und 
Achsenabschnitt.

[Jan K. (jan_k776)]

Das ist genau die Koordinatendarstellung der Zweipunkteform:
https://de.wikipedia.org/wiki/Zweipunkteform#Darstellung

Durchaus praktisch, braucht aber eine Division.

[M. K. (sylaina)]

Chandler B. schrieb:
> Aber muss ich wirklich erst m und b
> berechnen? Oder gibt es da nicht eine einfachere Lösung zu?

Naja, würde man auf dem Papier ja auch so machen.
Mit einem höheren Wertebereich könnte man durchaus genauer werden, ich 
sehe aber noch nicht, warum du dich überhaupt auf 8 bit festdübelst? Das 
würde man ja nicht mal auf einem Mikrocontroller machen, wenn man es 
entsprechend genau bräuchte und hier sind wir im PC-Forum ;)

Wenn der Rückgabewert zwingend uint8_t sein muss würde ich es so lösen:

uint8_t linearFunction(uint8_t x){
  return (uint8_t)((float)(0-100)/(-5-25) * (x + 5)));
}

Ich sehe halt noch nicht, warum man sich hier freiwillig auf uint8_t 
festgedübelt hat.

[Purzel H. (hacky)]

Wie rechnet man mit gebrochenen Steigungen ? Um sie zu einmalig 
berechnen kann man ja einmalig eine Floatingpoint Division verwenden. 
Nachher bei der Anwendung verwendet man einen 32bit Multiplikator und 
eine Division, welche nur shifts sind also zB div 65536, dh shift 16, dh 
niederwertiges word weg.

[Peter D. (peda)]

Nimm float, selbst auf 8-Bittern (AVR) geht das für viele Anwendungen 
ausreichend schnell. Den ganzen Ärger mit Rundungsfehlern und Überläufen 
muß ich nicht mehr haben.

[M. K. (sylaina)]

Peter D. schrieb:
> Nimm float, selbst auf 8-Bittern (AVR) geht das für viele Anwendungen
> ausreichend schnell. Den ganzen Ärger mit Rundungsfehlern und Überläufen
> muß ich nicht mehr haben.

Genau das denke ich mir halt auch, warum sich festnageln auf uint8_t? 
Das sehe ich hier halt aktuell auch noch nicht.

[Daniel A. (daniel-a)]

Aber genau mit float hat man dann doch Rundungsfehler?

[Rolf M. (rmagnus)]

Daniel A. schrieb:
> Aber genau mit float hat man dann doch Rundungsfehler?

Aber bedeutend weniger als mit einem Integer.

Chandler B. schrieb:
> m = (100 / (25 - (-5)); // = 3,3333 (uint8) = 3
> b = m * (-(-5)); // = 16,6666 (wegen uint8  = 15)

Mit float wäre der Wert eher 16.6666660, was sehr viel näher am 
richtigen Wert ist als 15.

[Bruno V. (bruno_v)]

Christoph S. schrieb:
> return (x - in_min) * (out_max - out_min) / (in_max - in_min) +
> out_min;

Das ist ein idealer Rechenweg in integer. Ich möchte Runden hinzufügen:

((x-in_min)*(out_max-out_min)+(in_max+1-in_min)/2)/(in_max-in_min)+out_m 
in;

und die üblichen dx (=in_max - in_min) und dy (out_max-out_min) 
einführen:

return ((x-in_min)*dy+(dx+1)/2)/dx)

Genauer geht es auch nicht mit float. Allerdings kann es überlaufen, 
wenn der halbe Wertebereich oder mehr verwendet wird (es ist safe, wenn 
keine Differenz > 127 und dx > 0) Bei beliebigen Vorzeichen halt jeweils 
abs()

[Yalu X. (yalu) (Moderator)]

Bruno V. schrieb:
> ((x-in_min)*(out_max-out_min)+(in_max+1-in_min)/2)/(in_max-in_min)+out_m in;

Wozu ist das "+1" in der Mitte des Ausdrucks? Das gehört doch weg, oder?

Also so:

  ((x-in_min)*(out_max-out_min)+(in_max-in_min)/2)/(in_max-in_min)+out_min 
;

Beispiel, wo der Unterschied zum Tragen kommt:

out_max-out_min=8, in_max-in_min=7 und x-in_min=3

[Christoph S. (mr9000)]

Rolf M. schrieb:
> Daniel A. schrieb:
>> Aber genau mit float hat man dann doch Rundungsfehler?
>
> Aber bedeutend weniger als mit einem Integer.

Der Vorteil ist, dass ich zu 100% immer genau weiß, wie groß dieser 
Rundungsfehler ist. ;-) Bei floats stochert man immer irgendetwas im 
Dunkeln oder ignoriert es einfach.

[Bruno V. (bruno_v)]

Yalu X. schrieb:
> Das gehört doch weg, oder?

Uups. Ja. Danke.

Also return ((x-in_min)*dy+dx/2)/dx + out_min

oder, mit c1 = dx/2 + out_min*dx -in_min*dy (und c1 = 16-bit)

return (x*dy+c1)/dx

[Daniel A. (daniel-a)]

Ich würde sogar soweit gehen zu behaupten, dass es, wenn man es richtig 
macht, mit Integren gar keinen Fehler gibt. Der Wert der rein geht, und 
der Wert der raus kommt sind diskret. Man bekommt also hier für jedes x 
genau ein y. Bei einer Linie wie hier, muss man also zwangsweise 
festlegem, was als auf der Linie zählt. Abrunden, Aufrunden, etc. kann 
man hier nur mir Integern immer exakt machen. Legt man anhand dessen 
fest, was auf der Gerade liegt, kann man das also auch nur mit integren 
exakt abbilden, und hat dort wirklich 0 Fehler.

Jenachdem, was man hier vor hat, ist es aber eventuell etwas 
unglücklich, nur x als Input zu betrachten. Denn die Funktion gibt ja 
nur einen Punkt für jedes x zurück, und wenn Δx < Δy, muss es an manchen 
x eigentlich mehr punkte auf der Linie geben als nur einen.

Da gibt es aber viele Wege darum herum. Man kann z.B. ein halboffenes 
Intervall aus 2 y werten machen, einen für das Minimum, einen für das 
Maximum. Oder man kann einen anderen Eingabebereich nehmen, 0<=t<Δx*Δy 
statt nur Δx<Δy, so dass man die Funktion für x und y als input 
verwenden könnte (indem man diese zuerst mit Δy bzw. Δx multipliziert).
Oder falls man nur über jeden Punkt einmal drüber will, könnte man 2 
Funktionen machen, eine für x, eine für y, und dann abhängig davon, ob 
Δx<Δy entweder die eine oder die andere nehmen.

[Oliver S. (oliverso)]

Daniel A. schrieb:
> Jenachdem, was man hier vor hat,

ist jede Lösung mehr oder weniger falsch. Und da wir nicht wissen, was 
der TO vorhat, kann man alles raten, mehr aber auch nicht.

Oliver

[Purzel H. (hacky)]

Ein 32 bit Integer hat eine bessere Aufloesung wie ein 32bit float. Denn 
der 32bit integer kann -2^31 .. +2^31 darstellen, was 9 signifikanten 
Stellen plus vorzeichen entspricht.
Der 32bit float hat 24 bit Mantisse was 6 signifikanten Stellen 
entspricht. Der Rest ist Exponent mit Vorzeichen. Der 32bit float hat 
einen groessen dynamischen Bereich. Allerdings fliegt die Genauigkeit 
bei einer Subtraktion zum Fenster raus.
Fuer uebliche Geschichten komme ich mit 32bit integer durch. Allerdings 
bin ich auch sattelfest mit Mathematik und was schiefgehen kann mit 
Mathematik zusammen mit Informatik

[Rolf M. (rmagnus)]

Daniel A. schrieb:
> Ich würde sogar soweit gehen zu behaupten, dass es, wenn man es richtig
> macht, mit Integren gar keinen Fehler gibt. Der Wert der rein geht, und
> der Wert der raus kommt sind diskret. Man bekommt also hier für jedes x
> genau ein y. Bei einer Linie wie hier, muss man also zwangsweise
> festlegem, was als auf der Linie zählt.

Ja, aber das ist doch gerade der Fehler, den man zwangsläufig macht. Die 
Werte können nicht exakt auf der Linie liegen, weil sie nicht 
darstellbar sind, also muss man sich eben am Raster der möglichen Werte 
ausrichten.
5/2 ist in Integer eben 3. Wenn ich das wieder mit 2 multipliziere, 
kommt ich nicht wieder bei 5 raus, weil ich einen Rundungsfehler gemacht 
habe.

> Abrunden, Aufrunden, etc. kann man hier nur mir Integern immer exakt
> machen.

Was verstehst du unter "exakt" im Zusammenhang mit Rundung? Runden ist 
etwas, das man tut, weil es nicht exakt geht oder zu aufwändig wäre.

> Legt man anhand dessen fest, was auf der Gerade liegt, kann man das also
> auch nur mit integren exakt abbilden, und hat dort wirklich 0 Fehler.

Was auf der Geraden liegt, ergibt sich mathematisch. Man kann sich 
natürlich auch selber was davon abweichendes als korrekt definieren, 
wodurch dann der Fehler natürlich per Definition 0 wird, aber man hat 
eben trotzdem eine Abweichung von einer echten Geraden. Oder auf das 
obige Beispiel übertragen: Wenn ich definiere, dass 3 das korrekte 
Ergebnis für die Division 5/2 ist, dann führt das noch lange nicht dazu, 
dass die 3 genau in der Mitte zwischen 0 und 5 liegt.

[Bruno V. (bruno_v)]

Daniel A. schrieb:
> Ich würde sogar soweit gehen zu behaupten, dass es, wenn man es
> richtig macht, mit Integren gar keinen Fehler gibt.

Das ist ja m.E. bei Christophs Rechenweg so, auch wenn es mit 
fehlender/falscher Rundung 2 Iterationen bedurfte.

Die Float-Implementierung ist da häufig schneller hingeschrieben, da man 
sich da "keine Gedanken" machen muss. Am Ende ist eine integer 
Implementierung ähnlich kompakt (bezüglich Rechenschritten und 
Operanden).

[Daniel A. (daniel-a)]

Rolf M. schrieb:
>> Abrunden, Aufrunden, etc. kann man hier nur mir Integern immer exakt
>> machen.
>
> Was verstehst du unter "exakt" im Zusammenhang mit Rundung? Runden ist
> etwas, das man tut, weil es nicht exakt geht oder zu aufwändig wäre.

Teilt man einen diskreten Wertebereich, in mehrere beliebige 
Halbintervalle, und schaut sich die Werte an den Enden an, passen diese 
exakt zusammen. Das heisst, nimmt man die Differenz (ende - start) aller 
teile, und zählt es zusammen, erhält man wieder den ursprünglichen 
Wertebereich. Bei anderen Intervallen ist es nicht so.

Es gibt da deshalb auch einige interessante Parallelen zwischen summen 
solcher diskreter Halbintervalle und Integralen, gewisse Klassen von 
Problemen sind dort auch äquivalent. Ich erinnere mich aber gerade nicht 
mehr, was da das Stichwort war. (FDE scheint damit zutun zu haben, aber 
ist nicht ganz was ich meine). Ich muss mal suchen, ob ich das wieder 
finde.

Jedenfalls ist es mit Integern sehr einfach, Wertebereiche so zu 
unterteilen, dass man quasi konsistent am Limit ist. Diese passen dann 
exakt zusammen, die gesamte Menge und die Abstände bleiben konsistent. 
Aber bei Floats kann ich das nicht wirklich machen.

[Rainer W. (rawi)]

Chandler B. schrieb:
> uint8 m, b, y;

Blöde Idee.
x besitzt welchen Typ?

[M. K. (sylaina)]

Rolf M. schrieb:
> 5/2 ist in Integer eben 3.

Also eigentlich ist das 2 in Integer :D

Rolf M. schrieb:
> Runden ist
> etwas, das man tut, weil es nicht exakt geht oder zu aufwändig wäre.

Oder weil es nicht darstellbar ist, vgl. z.B. irrationale Zahlen ;)

[T.U.Darmstadt (Gast)]

Ingo L. schrieb:
> Rechne es doch einfach in float oder scaliere um den Faktor 10 höher,
> wenn es unbedingt in 8-Bit ausgeführt werden soll und teile das Ergebnis
> später wieder durch 10
Das dürfte wohl kaum reichen. Schau dir mal die benötigten 
Multiplikationen an und die Fehler, die bei geringer Aussteuerung 
entstehen.