Ersatz für modulo

[Henry (Gast)]

Hallo und guten Morgen,
ich bin auf der suche danach die Modulo Funktion zu ersetzen, durch eine 
Berechnung von Hand ohne Gleitkommazahlen.
Könnt ihr mir dort weiterhelfen?
Zum Hintergrund, ich möchte eine long Variable in ASCII Zahlen umwandeln 
und habe bis jetzt folgendén Code benutzt
for(i = 0;i <= 9; i++)
  {
  Buffer[10-i] = (Value % 10) + 48;
  Value = Value / 10;
  }
Dieser benötigt jedoch eine viel zu lange Zeit um Verarbeitet zu werden.
Durch probieren habe ich die Zeile mit der Modulo Berechnung als Grund 
hierzu identifizieren können.
Deswegen die Frage nach einer anderen schnellen Lösung.

[Läubi .. (laeubi)]

Also die Division ist auch "nicht ohne" aber machs doch so:
Wenn der Controller ne Hardware Divisionseinheit hat geht das recht gut.

for(i = 0;i <= 9; i++) {
 x=Value/10;
 y=x*10;
 Buffer[10-i] = x-y + 48;
 Value=x;
}

Ansosnten gibt es (je nach wertebereich/ram/flash) verschiedene 
schnellere Varianten das zu lösen.

Für 8 bit Zahlen mach ich das so:
(Pseudocode)

TABELLE_DIV10={0,0,0,0,0,0,0,0,1....9,9,9}

if Zahl >= 200 {
 Ziffer3 = 2;
 Zahl = Zahl -200;
} else 
if Zahl >= 100 {
 Ziffer3 = 1;
 Zahl=Zahl-100;
} else {
 Ziffer3=0;
}
Ziffer2=TABELLE_DIV10[Zahl];
x=Ziffer2*10;
Ziffer1=Zahl-x;

Braucht etwas flasch (100bytes) kann auch durch ein DIV10 ersezt werden 
wenn man kein Flash hat, oder man packt die Tabelle ins RAM oder oder 
oder...

[Willi W. (williwacker)]

ich denke Du kannst eine Division durch eine Multiplikation ersetzen, 
etwa so:

long old
long new
long digit

new = old / 10;
digit = old - (new*10);
old = new;

usw.

Ciao

[Johannes M. (johnny-m)]

Division und Modulo macht ein vernünftiger Compiler aber i.d.R. sowieso 
in einem Rutsch, sofern das Programm es zulässt. Wenn man eins von 
beiden weglässt, ist immer noch das andere da. Zur Ermittlung des 
Divisions-Restes muss nunmal eine Division durchgeführt werden. Und 
Divisionen durch Zahlen, die keine Zweierpotenzen sind, sind nunmal 
etwas länglich.

[Peter D. (peda)]

Subtraktionsmethode:

Beitrag "Zahlenausgabe"


Peter

[Seff (Gast)]

Ein modulo duerfte sogar schneller als eine division sein. Eine division 
ist schieben und subtrahieren. Eine modulo ist eigentlich dasselbe, 
abgesehen davon, dass man das resultat nicht zusammensetzten muss, 
sonder nimmt was uebrig bleibt.

[Falk B. (falk)]

@ Johannes M. (johnny-m)

>Division und Modulo macht ein vernünftiger Compiler aber i.d.R. sowieso
>in einem Rutsch, sofern das Programm es zulässt. Wenn man eins von

Und wenn der Compiler nicht schlauch genaug dazu ist, kann man die 
Division mit Rest auch als Bibliotheksfuntkion per Hand verwenden.

Ist AFAIk sogar eine Standardfuktion in allen C-Compilern in stdlib.h

div_t div (int __num, int __denom)

Gibts zumindest beim AVR-GCC

Ausserdem, wieviel Zahlen musst du denn in welcher Zeit umwandlen? Du 
machst das doch hoffentlich nicht in einem Interrupt?
Für normale Anzeigen ist eine Wiederholrate von ~5Hz allemal 
ausreichend. Und niemand liest hundert Werte pro Sekunde.

MFg
Falk

[maddin (Gast)]

was ist mit den funktionen

atoi() usw..

m.

[Tippgeber (Gast)]

> Berechnung von Hand ohne Gleitkommazahlen.

> for(i = 0;i <= 9; i++)
>   {
>   Buffer[10-i] = (Value % 10) + 48;
>   Value = Value / 10;
>   }

Wo sind denn da Gleitkommazahlen?

Da sowohl der Quotient, als auch der Rest benötigt wird,
ist eine Integerdivision durchaus ein Rechenzeit-"billiges"
Verfahren.
Wenn der Compiler zu doof ist, sich den Rest zu merken, der bei der 
Division quasi umsonst anfällt, mussts halt in Assembler schreiben.

[Detlef _. (detlef_a)]

atoi() kommt auch um die Division mit 10 nicht rum, das ist relativ 
aufwendig.
Tippgeber hatte in diesem thread
Beitrag "16 bit Div durch 100 bei AVR Mega32"
ne Division durch 10 i.e. Multiplikation mit 0.1 aus ner App note 
vorgestellt. Viel effektiver gehts m.E. nicht.
Ansonsten als Hex ausgeben und/oder sich in einer chirurgischen 
Spezialklinik zu den vorhandenen 10 Fingern 6 weitere annähen lassen, 
zahlt die Kasse aber nicht.

Cheers
Detlef

[Detlef _. (detlef_a)]

Huch, da ist Tippgeber ja schon

[Tippgeber (Gast)]

Die Multiplikation mit 0.1 nützt hier nix, weil der Rest ja auch 
gebraucht wird. Und da ist die klassische einfache Division am besten.

[maddin (Gast)]

naja

atoi wandelt eigentlich einen string in eine integerzahl um.


ich dachte nur, das man evtl. eine ähliche funktion nutzen kann.

das libraries code erzeugen ist nat. klar, nur ich nutze diese 
funktionen selten, keine ahnung wie groß der overhead ist..

m.

[Detlef _. (detlef_a)]

Tippgeber wrote:
> Die Multiplikation mit 0.1 nützt hier nix, weil der Rest ja auch
> gebraucht wird. Und da ist die klassische einfache Division am besten.

Haste ja.
123*0.1 ~ 12
123-10*12=3

Cheers
Detlef

[Tippgeber (Gast)]

Hmm, ich seh da jetzt aber eine unnötige Multiplikation ;-)

123*0.1 ~ 12
123-10*12=3

atoi ist auch keine gute Lösung, die zieht intern eine long-Division.

[Detlef _. (detlef_a)]

Tippgeber wrote:
> Hmm, ich seh da jetzt aber eine unnötige Multiplikation ;-)
>

Ne erstens nicht unnötig und zweitens siehst Du die garnicht:

12*10= (12<<3)+(12<<1)

Cheers
Detlef

[Tippgeber (Gast)]

Naja, zum Takte zählen bin ich zu faul.
Das soll der OP mal machen.

In Assembler geht das mit dem Quotienten und dem Rest völlig schmerzfrei 
und ein DivMod16u o.ä. hat man meist eh schon im Projekt.
Die Funktion heisst nich umsonst DivMod16 :-)
Und aus der purzelt beides ohne Mühe heraus.

[Detlef _. (detlef_a)]

Ja, den Sinn der Frage verstehe ich nicht so richtig. Selbst ein langsam 
getakteter uC produziert mit einem ineffektiven Algorithmus mehr Zahlen 
im Dezimalsystem als der Durchschnittsleser wahrnehmen kann.

Cheers
Detlef

[Uhu U. (uhu)]

Dazu braucht man weder Assembler, noch selbergestrickte Routinen, die 
den Rest 'irgendwie effizienter' bestimmen, als der Compiler das macht.

Das Problem sitzt - wie so oft - vor dem Rechner:

Wenn du statt mit float, mit int rechnest, dann geht alles blitzschnell, 
denn int-Divisionen sind viel billiger, als welche mit float oder 
double. Und wenn du - wie von Falk vorgeschlagen - div benutzt, bekommst 
du Quotient und Rest in einem Schritt.

Falls du gebrochene float-Werte wandeln willst, geht das auch mit int: 
Du verschiebst durch eine Multiplikation das Komma so, daß du die 
Genauigkeit, die du ausgeben willst als int-Wert hast. Dann beginnst du 
zu wandeln und zählst die Stellen mit, um im rechten Augenblick das 
Komma in den Ausgabepuffer zu schreiben.

[Falk B. (falk)]

@ Uhu Uhuhu (uhu)

>Falls du gebrochene float-Werte wandeln willst, geht das auch mit int:
>Du verschiebst durch eine Multiplikation das Komma so, daß du die

Genau

Festkommaarithmetik

MfG
Falk