Hi,
ich versuche gerade, Code auf einen ARM-Mikrocontroller ohne FPU zu
portieren, der im Original vom PC kommt. Sämtliche
Fließkommaberechnungen kann ich ausreichend genau ersetzen, in dem ich
alle Werte als int behandle und einfach um den Faktor 1000 größer mache.
Einzig verbleibendes Problem: die Funktion sqrt(). Gibt es dafür
irgendwo einen brauchbar schnellen Ersatzcode? Der mögliche Wertebereich
liegt bei 30..1966020, so dass vorberechnete Tabellen leider wegfallen.
Irgend welche Ideen?
Danke!
Der beste Algo, den ich mal für Int-Sqrt auf dem µC gefunden habe, ist
hier http://xlinux.nist.gov/dads//HTML/squareRoot.html beschrieben. Ist
relativ schnell und gut erweiterbar, also 32bit sind kein Problem,
bleiben ja eh nur 16bit nach der Ausführung übrig.
Für 32bit heisst schnell etwa 1000 Zyklen. Drunter wird es Dir auch ein
anderer Algo ohne Tabelle nicht machen.
Ein Beispiel für PIC gibt es in AN040 von Microchip. Das kann man auf
einen ordentlichen Controller portieren.
Floro schrieb:> Fließkommaberechnungen kann ich ausreichend genau ersetzen, in dem ich> alle Werte als int behandle und einfach um den Faktor 1000 größer mache.
Das könnte ein Problem werden, das du berücksichtigen musst.
Denn die sqrt von 1000 muss ja logischerweise wieder 1000 ergeben.
Karl Heinz schrieb:> Das könnte ein Problem werden, das du berücksichtigen musst.> Denn die sqrt von 1000 muss ja logischerweise wieder 1000 ergeben.
Ja, das ist in dem zu erwartenden Wertebereich bereits enthalten.
Hallo,
je nachdem, wieviel Flash Du noch frei hast, könnte eine Tabelle
durchaus möglich sein, sie würde rund 5,5 kB benötigen.
Die Grundidee wäre dann, bei y=sqrt(x) keine Tabelle für alle "x" mit
Verweis auf "y" anzulegen, sondern eine Tabelle mit den Werten von y^2,
wobei y der Index wäre und dann mit einem Suchalgorithmus die beiden
Indizes zu finden, für die y1^2<x<y2^2 gilt. Danach kann man
entsprechend auf y1 ab- oder auf y2 aufrunden. Sollte ziemlich schnell
sein (jedenfalls deutlich weniger als 1000 Zyklen brauchen).
Schöne Grüße,
Martin
Floro schrieb:> Ja, das ist in dem zu erwartenden Wertebereich bereits enthalten.
Das Näherungsverfahren muß den Faktor aber auch berücksichtigen. Wie
Karl Heinz schon schreibt:
Karl Heinz schrieb:> Denn die sqrt von 1000 muss ja logischerweise wieder 1000 ergeben.
Ohne Berücksichtigung des Faktors 1000 käme ca.31 raus statt 1000. Damit
wäre die Wurzel von 1 nicht 1, sondern 0,031.
Floro schrieb:> Karl Heinz schrieb:>> Das könnte ein Problem werden, das du berücksichtigen musst.>> Denn die sqrt von 1000 muss ja logischerweise wieder 1000 ergeben.>> Ja, das ist in dem zu erwartenden Wertebereich bereits enthalten.
SChon klar.
Aber waruf ich raus will ist, dass dir ein normaler Wurzelalgorithmus
als sqrt(1000) das Ergebnis 31 liefern wird (oder 32 wenn er rundet).
Das kannst du aber nicht brauchen. sqrt(1000) muss 1000 als Ergebnis
haben.
Ich würde mein Heil zuerst mal wahrscheinlich in der Digit-Methode
suchen. Deine int sind 32 Bit groß? dann ist klar, dass das Ergebnis
nicht größer als 16 Bit sein kann.
Nacheinander dann, beginnend vom MSB eines 16 Bit Wertes (den ich mal x
nenne), testweise ein 1 Bit setzen, die Kontrollmultiplikation machen
und nachsehen ob x*x größer als die Zahl ist, von der die Wurzel gezogen
werden soll. Wenn größer, dann das Bit wieder auf 0 setzen und das
nächstkleinere Bit betrachten. Durch deine Spezialmultiplikation, die
die besonderheiten der Fixed Point Arithmetik schon berücksichtigt,
sollte da dann auch das richtige rauskommen
pseudo
1
int fix_sqrt( int a )
2
{
3
int result;
4
int i;
5
6
for( i = 0; i < 16; ++i )
7
{
8
result |= ( 1 << ( 15 - i ) );
9
if( fix_mult( result, result ) > a )
10
result &= ~( 1 << (15 - i ) );
11
}
12
13
return result;
14
}
ungetester Code, aber so ungefähr müsste das klappen.
PS: die 1000 waren keine gute Idee. DU halst damit deinem µC mehr Arbeit
auf als notwendig. 10-er Potenzen sind zwar für uns Menschen intuitiv,
aber das was für uns 10-er Potenzen an Vereinfachungen bringen, das sind
für einen Computer 2-er Potenzen. 1024 wäre programmtechnisch besser
gewesen, auch wenn die Zahlen dann im Debugger anders aussehen.
Blöde Frage, aber hast Du mal versucht, den Code ohne Modifikationen
hinsichtlich fixed point zu portieren?
Man wundert sich manchmal, was so ein kleiner ARM (auch ohne FPU) mit
entsprechender float-lib so leistet. Ich würde auf jeden Fall bei floats
bleiben, solange es irgendwie geht.
Floro schrieb:> Sämtliche> Fließkommaberechnungen kann ich ausreichend genau ersetzen, in dem ich> alle Werte als int behandle und einfach um den Faktor 1000 größer mache.
Ich w"urde die Werte alle um 1024 gr"osser machen.
@ARMdran
Ich w"urde so fr"uh wie m"oglich floats vermeiden, denn eine Addition in
einem Takt und KEIN float-lib aufruf ist schon ein gewaltiger
Unterschied.
Mich wundert manchmal, was so ein kleiner ARM (LPC176x) ohne FPU und
ohne floats so leisten kann. Zum Beispiel in einem 3P-Frequenzumrichter
mit bis zu 70000 samples / Sekunde 3 Kinderpopo-glatte Sinuskurven
(768level, 10bit-Zeit, DDS) mit Amplitude,
Motorbeschleunigungskennlinie, Spannungskennlinie in einer ISR zu machen
und DOCH NOCH ANDERE Sachen tun...
An Festkomma muss man sich echt gew"ohnen, aber daf"ur geht der Proz
dann ab dass man beim Messen der Geschwindigkeit fast aus den Latschen
kippt.
Klar ist fixed point schneller, aber ich seh das so:
Man designed ein Gerät ja nach den Anforderungen. Und wenn man die
Anforderungen mit floats heutzutage nicht erreichen kann, hat man mit
großer Wahrscheinlichkeit den falschen Prozessor selektiert.
Fixed points zu verwenden nur weil es schneller ist (obwohl man die
Systemanforderungen mit floats auch erreichen könnte) macht keinen Sinn.
ARMdran schrieb:> Fixed points zu verwenden nur weil es schneller ist (obwohl man die> Systemanforderungen mit floats auch erreichen könnte) macht keinen Sinn.
Doch. Macht es.
Es macht den Sinn der geringeren Materialkosten, des geringern
Strombedarfs, des geringern Speicherbedarfs ( = schon wieder Strombedarf
und Kosten).
Es macht den Sinn, dass manche Integer-Arithmetik genauer ist als
floats. Schau die mal die mickrige Mantisse von 'ne 4-byte float an.
Okay dann halt double und der n"achste Prozessor bitte...
Wir sind heutzutage st"andig versucht, alle Prozessorleistung mit
Schnickschnack abzufackeln, nur damit nix "ubrig bleibt um mal die
eigentliche Aufgabe BESSER zu l"osen als das fr"uher ging.
Rolf Magnus schrieb:> Ohne Berücksichtigung des Faktors 1000 käme ca.31 raus statt 1000. Damit> wäre die Wurzel von 1 nicht 1, sondern 0,031.
Wenn man das ergebniss dann mal Wurzel(1000) rechnet kommen am ende auch
wieder ca. 1000 raus. Das problem sind halt die Kommastellen, die
verloren gehen. Besser wäre wohl ein anderer Faktor, der auch eine
Ganzzahlige wurzel hat, dann ist der Fehler am ende kleiner.
Marc P. schrieb:> ARMdran schrieb:>> Fixed points zu verwenden nur weil es schneller ist (obwohl man die>> Systemanforderungen mit floats auch erreichen könnte) macht keinen Sinn.>> Doch. Macht es.> Es macht den Sinn der geringeren Materialkosten, des geringern> Strombedarfs, des geringern Speicherbedarfs ( = schon wieder Strombedarf> und Kosten).
Entwickelst du in Stückzahlen > 1000? Ok, dann mag das Sinn machen. Der
Speicherbedarf geht kaum in den Strombedarf ein.
> Es macht den Sinn, dass manche Integer-Arithmetik genauer ist als> floats. Schau die mal die mickrige Mantisse von 'ne 4-byte float an.> Okay dann halt double und der n"achste Prozessor bitte...
Das mag für bestimmte Fälle gelten. Dafür sind die Entwicklungskosten
für die fixed-point-Entwicklung i.d.R höher. Und nicht jeder
Codegenerator beherrscht fixed points sinnvoll.
>> Wir sind heutzutage st"andig versucht, alle Prozessorleistung mit> Schnickschnack abzufackeln, nur damit nix "ubrig bleibt um mal die> eigentliche Aufgabe BESSER zu l"osen als das fr"uher ging.
Eine Aufgabe ist dann gelöst, wenn die Requirements erfüllt sind.
Wenn Du '/' hast, dann kannst Du auch mal ganz grob sowas machen:
Eingabe: x
w = x/2;
for (int i=0; i<Geduld; i++) w = (w + x/w) / 2
Ausgabe w.
Die alte Rekursionsformel zieht auch ganz sch"on schnell an....
Floro schrieb:> Sämtliche> Fließkommaberechnungen kann ich ausreichend genau ersetzen, in dem ich> alle Werte als int behandle und einfach um den Faktor 1000 größer mache.
Wie bitte???
Das funktioniert nur mit Addition und Subtraktion. Bei Multiplikation
und Division wirst du dein blaues Wunder erleben. Wenn schon, dann 1024
und Shifts nach allen entsprechenden Operationen.
Ansonsten lies dir mal was zum Thema Pseudodivision und
Pseudomultiplikation durch. Klug eingesetzt kann das ein netter Weg für
transzendente Funktionen und Ähnliches sein.
W.S.
Marc P. schrieb:> Die alte Rekursionsformel zieht auch ganz sch"on schnell an....
Geduld = 13 reicht in deinem Wertebereich.
Glaubt man gar nicht, dass die so schnell konvergiert, oder?
@Floro: vernachl"assig mal deinen Fredd nich so! ;-)
Was macht denn deine Festpunkt-Umsetzung? Welche Wurzel?
Marc P. schrieb:> Ich w"urde die Werte alle um 1024 gr"osser machen.
ich m"ochte meine Aussage revidieren: Ich w"urde seit gestern die Werte
alle um (den Faktor) 65536 (2^16) gr"osser machen.
Ich habe die vergangenen Tage u.a. meine Festpunkt-Ausgaberoutinen auf
einen besseren Stand gebracht. Da ich auch den Cortex-M0 benutze muss
ich in letzter Zeit wieder etwas mehr darauf achten, keine unn"otigen
Divisionen zu machen. Und weil der M0 auch keinen 'long multiply'
(SMULL, UMULL) hat, kann er nur 16x16 => 32 bit sehr schnell
multiplizieren. So ergibt sich letztendlich, dass Festkommazahlen mit
Komma zwischen bit15 und bit16 ab besten dezimal auszugeben sind - 4..5
MAL so schnell wie andere: 25 700 Konvertierungen/s @ 12MHz Takt, um
mal einen absoluten Wert in den Raum zu stellen. Das sind 467 Takte pro
Konvertierung (5vor dem Komma, 4nach dem Komma, inclusive padding) mit
der Luxus-Routine.
Marc P. schrieb:> mal einen absoluten Wert in den Raum zu stellen. Das sind 467 Takte pro> Konvertierung (5vor dem Komma, 4nach dem Komma, inclusive padding) mit> der Luxus-Routine.
Du wandelst eine 32bit-Zahl in eine 5+4stellige Dezimalzahl um? Und das
soll 500 Takte dauern?
Wie machst Du das?
Marc P. schrieb:> w = x/2;> for (int i=0; i<Geduld; i++) w = (w + x/w) / 2
Ist das Gleiche, nur mit einem anderen Startwert und weniger schwer
verst"andlichen Zuweisungen und einem sehr kleinen Geduldsfaktor ;-)
Timm Thaler schrieb:> Du wandelst eine 32bit-Zahl in eine 5+4stellige Dezimalzahl um? Und das> soll 500 Takte dauern?>> Wie machst Du das?
Du verunsicherst mich. Entweder bin ich so grottenschlecht
(50Takte/digit) und hab's bloss bisher nicht kapiert, oder Du findest es
tats"achlich schnell!?
Lad dir mal bei:
http://www.windscooting.com/softy/software.html
das c-linux-r89.tar.bz2 runter und schau nach in:
c-linux/lib/c-any/{printFixedPoint.h,printFixedPoint-sliced.c,uint16Div.
h}
Nimm an, dass USE_MX16DIV10 '#defined' ist, wenn Du f"ur einen Cortex-M0
compilierst.
Timm Thaler schrieb:> Der beste Algo, den ich mal für Int-Sqrt auf dem µC gefunden habe, ist> hier http://xlinux.nist.gov/dads//HTML/squareRoot.html beschrieben. Ist> relativ schnell und gut erweiterbar, also 32bit sind kein Problem,> bleiben ja eh nur 16bit nach der Ausführung übrig.>> Für 32bit heisst schnell etwa 1000 Zyklen. Drunter wird es Dir auch ein> anderer Algo ohne Tabelle nicht machen.
16-Bit Wurzel aus einer 32-Bit Zahl...
"3 cycle/bit, 51 cycle total ARM code routine"
http://www.finesse.demon.co.uk/steven/sqrt.html
Arc Net schrieb:> 16-Bit Wurzel aus einer 32-Bit Zahl...> "3 cycle/bit, 51 cycle total ARM code routine"
Ich hab das damals auf dem ATmega8 gemacht. Da sind diese Befehle nicht
verfügbar. Setzt man die Routine für den Mega8 um, dürfen auch ein paar
mehr Zyklen rauskommen.
Ich die Rountine nochmal rausgekramt und getestet. Durchlauf für 32bit
ist relativ unabhängig von der Größe der Zahl zwischen 250 und 280
Zyklen. Die 1000 waren wohl etwas hoch geschätzt...
