Archiv verlassen und diese Seite im Standarddesign anzeigen : kleinere zahl ermitteln
Tesseract
2009-12-03, 15:08:07
vielleicht kann mir ja jemand helfen:
gegeben sind 2 zahlen (genauer gesagt 2 integer jeweils >= 0).
ich bräuchte eine methode, die von diesen 2 zahlen die kleinere returniert, allerdings ohne dabei bedingte anweisungen (z.B. if-else, switch usw.) zu verwenden.
kennt irgendjemand eine möglichkeit, wie man das z.B. rein auf arithmetischer ebene oder sonst wie lösen kann?
wahrscheinlich gibt es irgendeine total triviale lösung dafür die mir gerade einfach nicht einfallen will.
Neomi
2009-12-03, 15:25:35
Hier mal ein Beispiel in C++ mit normalen Integern:
int BranchFreeMin(int a, int b)
{
int mask = (a - b) >> 31;
return (a & mask) | (b & ~mask);
}
Der Shift ist ein arithmetischer Shift, der bei vorzeichenbehafteten Zahlen das höchste Bit repliziert, um das Vorzeichen beizubehalten. Damit hast du dann die Maske, um mit weiteren bitweisen Verknüpfungen das Resultat zusammenzubauen. Bei anderen Größen entsprechend andere Shiftweite und bei vorzeichenlosen Zahlen nach der Subtraktion casten, dann klappt das auch mit beliebigen anderen Integertypen. Wenn allerdings die Differenz größer ist als der maximal darstellbare vorzeichenbehaftete Wert (z.B. 2147483647 und -42 mit int als Typ), funktioniert es logischerweise nicht mehr.
Tesseract
2009-12-03, 16:40:17
thx, genau sowas habe ich gesucht. :)
Wahrscheinlich ist ein min = ((a < b) ? a : b); sogar schneller, zumindest wenn der Compiler ordentlich optimiert =>
mov min, a
sub b, a
skip if >0 flag (fällt mir grad nicht ein wie die Instruktion lautet)
mov min, b
=> 4 Instruktionen, höchstens skip braucht 2 Takte (auf ner SEHR primitiven Architektur) => max 5 Takte. Deutlich weniger Assembler-Instruktionen als die ganzen arithmetischen und logischen Verknüpfungen.
Aber ich nehme mal schwer an, dass ganze war ohnehin ein akademisches Beispiel. Wenn man in einem Programm keine Zeit mehr für einen Branch hat, hat man sowieso anderswo groben Schwachsinn angestellt.
mfg,
zgep
Tesseract
2009-12-03, 17:38:18
Wahrscheinlich ist ein min = ((a < b) ? a : b); sogar schneller, zumindest wenn der Compiler ordentlich optimiert
das ist leider ebenfalls eine bedingte anweisung, auch wenn der compiler eventuell etwas anderes draus macht.
und ja, es ist ein akademisches beispiel. die performance ist total egal.
jupp, klar ist der ?-Operator ein bedingter Sprung (wird ja in meinem ASM-Code auch zu einem). Mir ging's eher darum zu demonstrieren, dass das Vermeiden von solchen performancetechnisch nix bringt. sry dass ich das nicht besser ausgedrückt habe.
mfg,
zgep
btw, wer ist denn Bundespräsident von D? als Österreicher muss ich jedesmal bei der Frage zwei mal auf 'Antworten' klicken :D
Hab mir grad folgendes überlegt:
int BranchFreeMin(int a, int b)
{
int arr[] = { a, b };
return arr[(a>b)];
}
Ich kenn mich mit C nicht gut aus, weiss nicht ob (a>b) in 0 bzw. 1 gecasted wird oder ob man das explizit machen muss.
Edit:
Ich hoffe (a>b) ist keine bedingte Anweisung :D
Auf x86 zumindest nicht. CMP/SETG geht z.B. ohne Sprung.
Ich bin mir nicht sicher, ob garantiert ist, dass TRUE den Wert 1 ergibt. Wenn ich mich richtig erinner war nur garantiert 0 <=> FALSE und "nicht 0" <=> TRUE.
Hab mir grad folgendes überlegt:
int BranchFreeMin(int a, int b)
{
int arr[] = { a, b };
return arr[(a>b)];
}
Ich kenn mich mit C nicht gut aus, weiss nicht ob (a>b) in 0 bzw. 1 gecasted wird oder ob man das explizit machen muss.
Edit:
Ich hoffe (a>b) ist keine bedingte Anweisung :D
nice! auf jeden Fall einfacher lesbar als auf Bitebene und ohne die Einschränkungen!
auf Programmiersprachenebene definitiv ohne Sprung, auf Assembler-Ebene je nach Architektur. Aber auch die meisten RISCs sollten ohne Sprung auskommen (MIPS hat zB 'set on less than')
in C++ ist (int)true auf jeden Fall 1, in C weiß ich es ehrlicherweise nicht. Ab C99 schätze ich aber mal, dass das auch so ist.
mfg,
zgep
mov min, a
sub b, a
skip if >0 flag (fällt mir grad nicht ein wie die Instruktion lautet)
mov min, b
das geht schlauer
das geht schlauer
nur zu, ich lerne gerne was dazu ;)
btw, can u spot the bug? mir ist er erst jetzt grade aufgefallen :D
mfg,
zgep
ab 686 gibt es bedingte schiebebefehle cmov
von x86 hab ich wenig Ahnung, ich arbeite fast ausschließlich mit Architekturen aus dem Embedded-Bereich. Von daher kenne ich nur RISC-Befehlssätze.
cmov wäre auf x86 dann wahrscheinlich überhaupt die optimale Lösung.
@bug:
ich hab b mit sub b, a überschrieben und danach (bedingt) auf min zugewiesen -> großer schwachsinn
richtig wäre so:
mov min, a
sub a, b
skip if <0-flag set (ich weiß immer noch nicht wie die Anweisung heißt ;D )
mov min, b
auf x86 mit cmov wäre wahrscheinlich das ideal:
mov min, a
cmovb min, b, a
bin mir aber nicht sicher, ob ich cmovb hier richtig verwende...
anyway, enough ASM for the day ;)
mfg,
zgep
sub a, b
skip if <0-flag set (ich weiß immer noch nicht wie die Anweisung heißt ;D )
das macht man eher mit dem cmp befehl, der das carry (jc-bedingter sprung) und zero-flag (jz bedingter sprung) beeinflußt
jz und jc brauchen aber mehr CPU-Takte als die skip-Instruktion (auf AVR8, mit dem arbeite ich im Moment für ein Projekt bei dem sowas wichtig ist. wie's auf MIPS oder ARM aussieht müsste ich in meinen Unterlagen nachsehen)
auf x86 gibts kein skip imo und der rest zählt nich :tongue:
Vor allem wäre "skip" auch ein bedingter Sprung. Hilft auch nicht wirklich weiter.
Ich bin mir nicht sicher, ob garantiert ist, dass TRUE den Wert 1 ergibt. Wenn ich mich richtig erinner war nur garantiert 0 <=> FALSE und "nicht 0" <=> TRUE.
Dann schreibt man halt "(a > b) & 1". Das &1 wird eh wegoptimiert.
robobimbo
2009-12-04, 16:19:38
http://graphics.stanford.edu/~seander/bithacks.html
r = y ^ ((x ^ y) & -(x < y)); // min(x, y)
bzw.
r = y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); // min(x, y)
Vor allem wäre "skip" auch ein bedingter Sprung. Hilft auch nicht wirklich weiter.haben wir schon vor ein paar Posts festgestellt ;)
Dann schreibt man halt "(a > b) & 1". Das &1 wird eh wegoptimiert.das löst das Problem leider nicht (falls es denn wirklich existiert. Ich denke mal auch in älteren C-Standards war (int)true schon immer 1), da wenn (int)true eine gerade Zahl ergeben würde immer a zurückgegeben würde (jede gerade Zahl & 1 = 0), auch wenn b kleiner ist...
mfg,
zgep
Err, richtig. Brainfart.
Soweit ich weiß muss int(true) aber immer 1 ergeben. Es sind aber alle Zahlen >0 in einem Statement true.
Hab mal die Standards rausgesucht, die logischen Operatoren in C haben Rückgabetyp int und ergeben 1 bei wahr und 0 bei falsch.
Womit das Problem keins ist und die Lösung mit dem Array gültig und meiner Meinung nach recht elegant ist.
Ja, bei C, aber nicht bei C++. Dort ist es def. bool
Probier's aus:
#include <iostream>
#include <typeinfo>
int main()
{
int a, b;
std::cout << typeid(a > b).name() << std::endl;
}
MSVC++ spuckt "bool" aus, GCC "b" - was auch für bool steht.
In C++ gilt:
4.5.4 An rvalue of type bool can be converted to an rvalue of type int, with false becoming zero and true becoming one.
(a>b) entspricht für mich einem vergleich, weil im maschinencode zumindest nen cmp vorkommt
es macht doch keinen unterschied ob ich das mit nem array löse, oder mittels (a>b)?b:a löse
Natürlich macht das nen Unterschied. Deine Variante erzeugt einen bedingten Sprung solang kein CMOV verwendet werden kann.
Die Variante mit dem Array wird dies nie tun.
die Array-Variante erzeugt mit MINGW
mov eax,[ebp+08h]
mov edx,[ebp+0Ch]
mov [ebp-08h],eax
mov [ebp-04h],edx
mov eax,[ebp+08h]
cmp eax,[ebp+0Ch]
jle L004012B3
mov dword ptr [ebp-0Ch],00000004h
jmp L004012BA
L004012B3:
mov dword ptr [ebp-0Ch],00000000h
L004012BA:
"meine" Variante
mov eax,[ebp+08h]
cmp eax,[ebp+0Ch]
jle L004012DA
mov eax,[ebp+0Ch]
mov [ebp-04h],eax
jmp L004012E0
L004012DA:
mov eax,[ebp+08h]
mov [ebp-04h],eax
L004012E0:
Compiler sind halt nicht immer so schlau, wie man sich das wünscht
Wie gesagt, MSVC++ erzeugt CMP/SETG ohne Branch. Der MS-Compiler ist gar nicht so übel wie immer getan wird, vor allem bei solchen Dingen.
GCC hat da aber aufgeholt, welche Version ist das?
Mir ist grad noch ne Methode eingefallen, habs für ein paar Fälle gerechnet, bin mir aber nicht sicher obs allgemeingültig ist für alle a,b >= 0
int BranchFreeMin(int a, int b)
{
int x = a - b;
int min = a - ( (abs(x) + x) / 2 );
return min;
}
Fraglich auch ob abs (sollte der absolut-operator: |x| sein) so in C gibt.
Edit:
Stimmt, falsch vom Schmierzettel abgeschrieben :)
Danke pest
da ist ne klammer falsch, aber die idee ist gut
das ist auch korrekt, so weit ich das überblicke,
und die erste (rein arithmetische) lösung
sind a,b reelle Zahlen, und d=|a-b|
dann ist für a<b
a-1/2(d-d)=a
für a>b ist
a-1/2(d+d)=a-(a-b)=b
Pinoccio
2009-12-05, 17:35:50
aber die idee ist gutNaja, abs(x) versteckt die Entscheidung.
Andererseits: es ist ein akadamisches Beispiel, wenn if und switch verboten sind und abs erlaubt, ist die Lösung gültig.
Ebenso ist es irgendwie mit allen anderen "Lösungen": boolsche Operationen auf Bitmustern sind irgendwie ja auch Fallunterscheidungen, ebenso binäre Arithmetik.
Naja, akademische Probleme halt ...
das ist auch korrekt, so weit ich das überblicke,
und die erste (rein arithmetische) lösung
sind a,b reelle Zahlen, und d=|a-b|
dann ist für a<b
a-1/2(d-d)=a
für a>b ist
a-1/2(d+d)=a-(a-b)=bNaja, x^y ist irgendwo auch Arithmetik. :ugly:
Denn wie ist |a-b| definiert? ...
mfg
ich glaube das war's was ich in post #26 ausdrücken wollte,
aber die letzte lösung entspricht dem, was ich eigentlich erwartet habe
Naja, x^y ist irgendwo auch Arithmetik. :ugly:
Denn wie ist |a-b| definiert? ...
ja mei, ich bin kein informatiker, und ~x^y ist für mich keine arithmetik mehr
streichen wir "arithmetik" und setzen "mathematisch elegant"
aber nunja, wie ist der betrag definiert, welch überraschung eine fallunterscheidung
http://upload.wikimedia.org/math/8/8/a/88a1e35f8d752b2f04e563a3beff6d54.png
pest, heute gänzlich unakademisch
Pinoccio
2009-12-05, 17:43:58
ich glaube das war's was ich in post #26 ausdrücken wollte,
aber die letzte lösung entspricht dem, was ich eigentlich erwartet habeEine imho eher arithmetische Lösung wäre abs(x) durch sqrt(x^2) zu ersetzen.
mfg
jut, macht für den "beweis" zum glück keinen unterschied
p.s.:
ich wäre gern auch so ein korinthenkacker :D - aber meine freundin mag meine bestehenden züge schon nicht :(
Ich dachte bis jetzt eigentlich immer, dass abs(x) so definiert ist wie Pinoccio schrieb. :freak:
im Komplexen funktioniert das nicht mehr, meine angegebene Betragsfunktion allerdings auch nicht
hm, warum definiert man das so, es ist einleuchtender, und die Wurzelfunktion kommt in Ana I imo später als der Betrag :D
es gibt sicher einen sinnvollen Grund
abs() dürfte wohl kaum erlaubt sein, da höchstwahrscheinlich mittels bestimmten sprung implementiert. ansonsten könnte man ja gleich min() nehmen.
mit einer eigenimplementation für abs() wie von pinoccio beschrieben wäre es aber sicher wieder gültig.
mfg,
zgep
ist interessant zu verfolgen, was für lösungsmöglichkeiten so daherkommen
jetzt hatten wir schon bitoperationen, tricks mit indizes und eine rein auf unterstufenmathematik basierende lösung
Tesseract
2009-12-05, 19:37:52
das ganze beispiel (wesentlich umfangreicher) war ohne bedingte sprachkonstrukte zu lösen. meine imho sehr elegante lösung kommt allerdings nicht ohne diese methode aus, von der ich aber sowieso ausgangen bin, dass sie sich arithmetisch implementieren lässt. ob abs() erlaubt ist würde wohl davon abhängen wie es implementiert ist. eventuell könnte ich sogar direkt min() verwenden, aber eigentlich wollte ich auf externe methoden sowieso komplett verzichten.
die sprache ist btw. java, was aber eh keine rolle spielen sollte.
Naja, x^y ist irgendwo auch Arithmetik. :ugly:
Denn wie ist |a-b| definiert? ...
du musst allerdings zugeben, das für den beweis der "mathematischen" variante, die durch den betrag induzierte metrik verwendet werden sollte
vBulletin®, Copyright ©2000-2024, Jelsoft Enterprises Ltd.