Division großer Integerzahlen

[Toellner (Gast)]

Hallo,

ich möchte folgende Berchnung möglichst genau durchführen.
Wichtig es gehen nur Integer bzw. Unsigned Integer Zahlen.

uint_Input = 32786        //Input kann zwischen 5190...61047 liegen

uint_Dmin = (5190);
uint_Dmax = (61047);

// Meine gewünschte Berechnung:
uint_Output = (uint_Input-uint_Dmin)/(uint_Dmax-uint_Dmin)*65535

Ich weis das ich die Berechnung in mehrere Einzelberechnungen 
unterteilen muss und auch irgendwie mit Modulo (%) rechnen muss. Aber 
wie der genaue Algorithmus aussieht um ein möglichst Ergebnis zu 
erhalten.

Ich hoffe mir kann das jemand erklären.
Danke schon im Vorraus!!!

[Matthias (Gast)]

na zuerst mal beide Differenzen getrennt errechnen..
PS: wäre es nicht sinnvoller, mit 65536, statt 65535 zu multiplizieren??
Weil dann könntest jetzt
die Division durchführen (siehe Anhang)
und die Mult. mit 65536 = 2^16 kannst dir sparen,
weil du das ganze nur um zwei Byte nach links schiebst...

und modulo brauchst hier nicht...

[Toellner (Gast)]

Ja, Multiplikation mit 65536 ist Richtig (war falsch von mir)

Also:

uint_temp1 = uint_Input - uint_Dmin

uint_temp2 = uint_Dmax-uint_Dmin

uint_Output = uint_temp1/uint_temp1 -> ???
                                    -> avr200.asm
                                    -> Ich habe zwar momentan einen AVR 
zum Testen das ganze soll später auf einen Freescale MC ;(
Gibt es ne andere (C-)Lösung?

Aber schon mal Danke!

[Matthias (Gast)]

in C kannst du ruhig das schreiben:
uint_Output = ( (uint_Input-uint_Dmin)/(uint_Dmax-uint_Dmin) ) << 16 );

Wobei, wie gesagt, lass das schieben um 16bit, oder mult. mit 65536 
einfach weg, und mach nur:
uint_Output = (uint_Input-uint_Dmin)/(uint_Dmax-uint_Dmin)
und "denke" dir die zwei nullen einfach hinten dran..

alternativ:
uint_temp1 = uint_Input - uint_Dmin
uint_temp2 = uint_Dmax-uint_Dmin
uint_Output = uint_temp1/uint_temp1



Oder was meinst jetzt?

[Rahul, der Trollige (Gast)]

>Freescale MC

Sollten die mit 32-Bit-Zahlen nicht sowieso zurechtkommen?

Assembler (AVR 200 umgesetzt):
Beitrag "DIVISION 32 BIT / 32BIT Beispiel (Assembler) ATmega8"

in C:
Beitrag "Re: Zahlenausgabe"

[Rahul, der Trollige (Gast)]

Was vergessen:
Es ist natürlich sinnvoll, erst mit 65536 zu multiplizieren und dann zu 
dividieren. Da kommt dann vermutlich etwas mehr raus...

[Karl H. (kbuchegg)]

> und "denke" dir die zwei nullen einfach hinten dran..

Wieso 2 Nullen. Hex vielleicht, aber dezimal sind
da keine 2 Nullen.

Als erstes:
* Grundregel: Divisionen schiebt man in der Verarbeitungs-
  kette soweit nach rechts wie möglich.

  uint_Output = ( (uint_Input-uint_Dmin)/(uint_Dmax-uint_Dmin) ) << 16 );

Wenn die Division schon 0 ergeben hat, kannst du nach links
schieben soviel du willst, das bleibt trotzdem 0.

Also Divisionen nach hinten:
Aus
  uint_Output = (uint_Input-uint_Dmin)/(uint_Dmax-uint_Dmin)*65536
wird
  uint_Output = (uint_Input-uint_Dmin)*65536/(uint_Dmax-uint_Dmin)

Wobei sich jetzt natürlich das Problem ergibt, dass die
Multiplikation in int, bzw. unsigned int gemacht wird und
somit einen Overflow produzieren kann. Um das zu vermeiden
stellen wir erst mal sicher, dass die Multiplikation
als long Multiplikation durchgeführt wird.

  uint_Output = (uint_Input-uint_Dmin)*65536UL/(uint_Dmax-uint_Dmin)

Bei einer Berechnung werden immer beide beteiligte Operanden
auf gleiche Datentypen gebracht. Ist einer der beiden long, wird
auch der andere zu long und die Operation wird dann als long
Operation durchgeführt. 65536UL ist ein long (genauer:
ein unsigned long), ergo: die Multiplikation wird komplett
in unsigned long durchgeführt und das Ergebnis ist ebenfalls
ein unsigned long.


Somit sind Overflows soweit gebannt.

Ach ja. Das Schieben um 16 Bit anstatt der Multiplkation.
Diese Optimierung überlassen wir besser dem Compiler. Das
können die seit 30 Jahren zuverlässig.

[Mark Toellner (Gast)]

Hallo Karl Heinz,

ich habe es heute nach deiner Vorabe mit Long umgesetzt. Es funktioniert 
prima! :)

Danke an alle Helfer!