|
|
|
|
Modifizieren sie die beiden Funktionen zur so, dass sie anstelle der Summe, das Produkt errechnen. Bauen Sie Programm zusätzlich mit dem Optimierungsflag „-O3“ und versuchen Sie mittels Dissassembler zu erklären, warum die c Version nun um ein Vielfaches schneller ist, bzw. sogar in konstanter Zeit läuft.
Das ist meine Aufgabe. Die beiden Funktionen, um die es geht, machen eine Fakultaetsberechnung. Einmal in C und einmal in Assembler. Dazu hab ich mehrere Dateien.
Eine heisst framework.c
|
Code: |
// c reference implementation
int gauss (int a){
int x = 1;
for (;a;a--){
x=x*a;
}
return x;
}
__attribute__((fastcall)) extern int function(int a); // fastcall is needed for similar calling conventions between Windows and Unix
int main (){
uint64_t time = rdtsc();
int i = function(30);
time = rdtsc() - time;
printf("Function ASM returns %i - in %llu \n",i,time);
time = rdtsc();
i = gauss(30);
time = rdtsc() - time;
printf("Function C returns %i - in %llu \n",i,time);
return 0;
} |
|
Die extern aufgerufene Funktion ist die Assembler Variante. Die steht in der assembler.S
|
Code: |
.intel_syntax
.globl function
.globl _function
.text
#simple add function
_function:
function: # parameter oder is ecx, edx, than stack
push %ebp # save basepointer
mov %ebp, %esp # stack pointer to basepointer
# remember not to change ebx or save it!
# registers
mov %eax, %ecx # init
dec %ecx
1:
imul %eax,%ecx
dec %ecx
jnz 1b
pop %ebp # restore basepointer
ret # Return value is in %eax |
|
Ich bin dann verfahren wie in der Aufgabe gefordert und hab das Ding compiliert und angeschaut. In der Tat ist die Variante in C immer schneller und laeuft in konstanter Geschwindigkeit. Der Dozent meinte in der Vorlesung, das sich das Optimierungsflag so auswirkt, dass konstante Ausdruecke (wie sie ja die Fakultaetsfunktion mit dem fest vorgegebenem Wert meiner Meinung nach ist) einfach ausgewertet und nur das Ergebnis gespeichert wird. Ich hab dann disassembliert, konnte aber in der framework.s keinen Hinweis auf einen festen Wert finden.
framework.s
|
Code: |
.file "framework.c"
.text
.p2align 4,,15
.globl _rdtsc
.def _rdtsc; .scl 2; .type 32; .endef
_rdtsc:
pushl %ebp
movl %esp, %ebp
pushl %ebx
/APP
pushl %ebx
xorl %eax,%eax
cpuid
rdtsc
/NO_APP
movl %eax, %ecx
/APP
popl %ebx
/NO_APP
xorl %ebx, %ebx
xorl %eax, %eax
orl %ebx, %edx
popl %ebx
orl %ecx, %eax
popl %ebp
ret
.p2align 4,,15
.globl _gauss
.def _gauss; .scl 2; .type 32; .endef
_gauss:
pushl %ebp
movl $1, %eax
movl %esp, %ebp
movl 8(%ebp), %edx
testl %edx, %edx
jmp L11
.p2align 4,,7
L13:
imull %edx, %eax
decl %edx
L11:
jne L13
popl %ebp
ret
.def ___main; .scl 2; .type 32; .endef
.section .rdata,"dr"
.align 4
LC0:
.ascii "Function ASM returns %i - in %llu \12\0"
.align 4
LC1:
.ascii "Function C returns %i - in %llu \12\0"
.text
.p2align 4,,15
.globl _main
.def _main; .scl 2; .type 32; .endef
_main:
pushl %ebp
movl $16, %eax
movl %esp, %ebp
pushl %edi
pushl %esi
pushl %ebx
subl $44, %esp
andl $-16, %esp
call __alloca
call ___main
/APP
pushl %ebx
xorl %eax,%eax
cpuid
rdtsc
popl %ebx
/NO_APP
movl %eax, -24(%ebp)
xorl %esi, %esi
movl $30, %ecx
movl $0, -20(%ebp)
movl -24(%ebp), %ebx
orl %esi, %ebx
movl -20(%ebp), %esi
orl %edx, %esi
call @function@4
movl %eax, %edi
/APP
pushl %ebx
xorl %eax,%eax
cpuid
rdtsc
/NO_APP
movl %eax, %ecx
/APP
popl %ebx
/NO_APP
movl %ecx, -32(%ebp)
xorl %eax, %eax
movl -32(%ebp), %ecx
movl $0, -28(%ebp)
movl %edi, 4(%esp)
orl %ecx, %eax
movl -28(%ebp), %ecx
movl $LC0, (%esp)
orl %ecx, %edx
subl %ebx, %eax
sbbl %esi, %edx
movl %eax, 8(%esp)
movl %edx, 12(%esp)
call _printf
/APP
pushl %ebx
xorl %eax,%eax
cpuid
rdtsc
popl %ebx
/NO_APP
xorl %ecx, %ecx
movl %eax, %esi
xorl %edi, %edi
movl %ecx, %eax
orl %edi, %edx
orl %esi, %eax
movl %eax, -40(%ebp)
movl $1, %esi
movl $30, %eax
movl %edx, -36(%ebp)
.p2align 4,,15
L21:
imull %eax, %esi
decl %eax
jne L21
/APP
pushl %ebx
xorl %eax,%eax
cpuid
rdtsc
/NO_APP
movl %eax, %ecx
/APP
popl %ebx
/NO_APP
movl %esi, 4(%esp)
movl %edx, %edi
xorl %edx, %edx
movl $LC1, (%esp)
xorl %ebx, %ebx
orl %ecx, %edx
orl %ebx, %edi
subl -40(%ebp), %edx
sbbl -36(%ebp), %edi
movl %edx, 8(%esp)
movl %edi, 12(%esp)
call _printf
leal -12(%ebp), %esp
xorl %eax, %eax
popl %ebx
popl %esi
popl %edi
popl %ebp
ret
.def _printf; .scl 3; .type 32; .endef
|
|
Kann mir jemand auf die Spruenge helfen?
|
|
|
|
|
|
|
| Zitat von DogfishHeadcrab
| Zitat von otters
| Zitat von DogfishHeadcrab
| Zitat von DogfishHeadcrab
| Zitat von DogfishHeadcrab
Wollte mal grundlegende kleine Elektroniksachen löten und dabei eben mein eTechnik-Wissen erweitern.
Gibts da gute Bücher/ Sets/ Einsteigerempfehlungen?
| |
| |
meeeep
| |
worum gehts dir? Ums Löten, Bauteile, Schaltungen?
| |
Schaltungen löten können, also zum beispiel einen kleinen Radiotransmitter, Lichtschranke, etc.
Und wo ich grad am Problem sitz:
|
Code: |
6. Two vector are given:
u = 4i + 9j - 5k and v = -3i + 6j - 7k
Use MATLAB to calculate:
a = 1/2u
|
|
Matlab-Noob. Wie geb ich i,j und k als Element R an/ wie löse ich das?
usw.
| |
Die Aufgabe ist komisch... Was ist denn nun i,j,k? Einheitsvektoren? Das i,j,k irgendwelche reellen Zahlen sein sollen macht doch garkeinen Sinn.
Falls i,j,k einheitsvektoren sein sollen dann:
a = 1/2 * [4 9 -5] ;
|
|
|
|
|
|
|
| Zitat von MCignaz
Modifizieren sie die beiden Funktionen zur so, dass sie anstelle der Summe, das Produkt errechnen. Bauen Sie Programm zusätzlich mit dem Optimierungsflag „-O3“ und versuchen Sie mittels Dissassembler zu erklären, warum die c Version nun um ein Vielfaches schneller ist, bzw. sogar in konstanter Zeit läuft.
[...]
Kann mir jemand auf die Spruenge helfen?
| |
Mal unabhängig von der Aufgabe: Wievieltes Semester ist das? Aber in -O3 compilierten noch irgendwas im Assembler zu erkennen ist eher ne Strafe (find ich , da bei -O3 ja doch schon ziemliche viele "Tricks" erlaubt sind. Unter http://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html steht übrigens was alles an Optimierungsflags bei -O3 aktiviert ist. Ist es auch bei -O2 bzw. -O schneller? Egal ob ja oder nein, beides hilft weiter bestimmte Optimierungstechniken auf der Website dann auszuschließen (insbesondere wenn es bei -O bzw -O2 langsamer ist).
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von mc.smurf am 13.05.2011 0:08]
|
|
|
|
|
|
Hey danke.
Die C-Funktion ist schon ab O1 fast gleichauf, noch dichter bei O2 und erst ab O3 ist sie wirklich schneller. Die Ergebnisse sind aber immer recht stabil.
Wuerde als Erklaerung denn dieser Ansatz reichen, dass durch die Optimierungen die Funktionen mit ihren konstanten Eingabewerden durch das Ergebnis ersetzt werden? Allerdings sehe ich da zwei Widerspruechlichkeiten:
- Die Geschwindigkeiten sind nicht voellig konstant. Gelegentlich gibt es Ausreisser auf einen zweiten Wert, sowohl von der Assembler als auch von der C-Version
- Wenn die Funktion wirklich "wegoptimiert" wird, warum wird die C Version so deutlich schneller waehrend die Assembler Variante auf nahezu einem Level bleibt. Muesste die nicht auf optimiert werden?
Ach und: 2tes Semester Rechnerarchitektur
|
|
|
|
|
|
|
Um verlässliche Messergebnisse zu bekommen muss die Programmlaufzeit erstmal hoch genug sein damit Effekte wie im Hintergrund laufende Prozesse nicht weiter bei den Zeitmessungen auffallen (hier wird ja nur bis 30 die Multiplikation durchgeführt, also wird die Programmlaufzeit wohl sehr kurz sein). Am besten man macht drei Testläufe und nimmt dann einfach den niedrigsten Wert, das sollte dann reichen. Evtl. (bzw. sogar sicher kommen durch solche Hintergrundprozesse auch diese Ausreiser zustande, es könnte z.B. der L1 Instruktionscache teilweise durch andere Anweisungen überschrieben werden oder es muss eben allgemein ein Kontextswitch auf dem Prozessor durchgeführt werden da eine anderen Anwendung die CPU belegt. Dann müssen erst wieder die nächsten Instruktionen von deinem Programm neu in den Cache geladen werden. Könnte man übrigens auch messen (z.B. mit pfmon), aber das wäre dann wohl etwas Overkill
gcc optimiert nur den C Code, der manuell eingefügte Assembler Code wird nicht optimiert.
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von mc.smurf am 13.05.2011 0:54]
|
|
|
|
|
|
Arrr damit. Ok, also verschiedene Durchlaeufe hab ich jeweils gemacht und mich dann am jeweils haeufigsten Wert orientiert. Dass der Assembler Code nicht optimiert wird, erklaert natuerlich einiges. Wie koennte ich das denn im dissassemblierten File herauslesen? Ziemlich gemeine Aufgabe.
/Ok, ich schau mir gerade die dissassemblierten Dateien mit und ohne Optimierung an. Die Assemblerfunktion wird jeweils nur mit "call &function&4" aufgerufen, waehrend die C-Funktion "gauss" da drin als Block vorkommt und sich in den Dateien unterscheidet. Das muss reichen als Antwort.
// Viel mehr als 30! ging leider nicht, bei 50! hat er als Berechnungsergebnis immer nur 0 ausgespuckt.
|
[Dieser Beitrag wurde 2 mal editiert; zum letzten Mal von MCignaz am 13.05.2011 1:31]
|
|
|
|
|
|
50! ist auch ein wenig groß, über 200 Binärstellen ...
|
|
|
|
|
|
|
Haha, eben in der Vorlesung wieder so einen "WTF?"-Moment gehabt, der Mathematik so großartig macht
Ging um FFT (Fast Fourier Transform, numerisches Verfahren um effizient Fouriertransformationen zu berechnen). Dabei hat man einen Vektor . Diesen unterteilt man in zwei Vektoren . Jeden dieser Vektoren unterteilt man wieder nach dem selben Schema, und macht das immer wieder, bis man bei Vektoren der Länge Eins angekommen ist.
Die Frage ist jetzt: In welcher Reihenfolge müssen die Indizes am Ende stehen, damit es stimmt? (also anders formuliert: Wenn man das ganze in ein Baumdiagramm malt, welches y_k steht in der letzten Spalte an oberster Stelle, an zweiter, etc)
Dozent: Ja, da gibt es eine sehr schöne Merkregel. Sie schreiben alle Indizes untereinander in eine Tabelle (Bsp.: 0, 1, 2, 3)
Studenten: Okay.
Dozent: Dann übersetzen Sie jede Zahl in ihre Binärdarstellung (00, 01, 10, 11).
Studenten:
Dozent: Dann machen Sie eine Bitumkehrung (00 -> 00, 01 -> 10, 10 -> 01, 11 -> 11) und übersetzen die Zahlen zurück (0, 2, 1, 3).
Studenten:
Dozent: Das ist die Reihenfolge der Zahlen in der letzten Spalte und klappt auch für jedes größere N.
Studenten:
|
[Dieser Beitrag wurde 4 mal editiert; zum letzten Mal von Newb1e am 13.05.2011 12:35]
|
|
|
|
|
|
| Zitat von DogfishHeadcrab
| Zitat von otters
| Zitat von DogfishHeadcrab
| Zitat von DogfishHeadcrab
| Zitat von DogfishHeadcrab
Wollte mal grundlegende kleine Elektroniksachen löten und dabei eben mein eTechnik-Wissen erweitern.
Gibts da gute Bücher/ Sets/ Einsteigerempfehlungen?
| |
| |
meeeep
| |
worum gehts dir? Ums Löten, Bauteile, Schaltungen?
| |
Schaltungen löten können, also zum beispiel einen kleinen Radiotransmitter, Lichtschranke, etc.
| |
Ich wollt das noch mal aufgreifen, hat da keiner ne Empfehlung?
Die Sache würde mich auch interessieren..
|
|
|
|
|
|
|
Ich hab' immer noch nicht so ganz verstanden, was eigentlich gewünscht wird. Selber Schaltungen entwickeln oder nur etwas fertiges nachbauen?
Aber ich werf' einfach mal Burkhard Kainkas Bastelecke in den Raum
|
|
|
|
|
|
|
Also ich hatte einfach nur Gedanken wie "Wie geht das?" im Kopf.
Z.b. Wie bau ich eine Reihe von LEDs, die Nacheinander leuchten?
So Zeugs halt. Ein bisschen allgemeine Theorie, wie denn so eine Schaltung / Ein Schaltplan aussieht und was was bedeutet wäre auch nicht verkehrt.
Ideal wäre ein gutes Theoriebuch mit interessanten Praxisbeispielen.
|
|
|
|
|
|
|
Vielleicht einfach mit so einem Arduino Board anfangen? Da muss man zwar auch die Grundlagen beherrschen, aber kommt -soweit ich das verstanden habe- schneller zu etwas, das funktioniert. Und man kann das Teil wohl recht easy am PC programmieren.
|
|
|
|
|
|
|
Jap, einfacher als mit nem Arduino gehts wohl nicht. Kostet ja auch nicht die Welt. hier klicken.
|
|
|
|
|
|
|
Ich weiß nicht was sich Dogfish vorgestellt hat, aber ich hatte da was anderes im Kopf, noch simpler um ehrlich zu sein. Auch ein Buch mit etwas Theorie zu Schaltplänen halt. Wie liest man so Schematics usw.
Bei den Arduinos z.B. hab ich das Problem, dass ich das Zeug zwar programmieren, bei den Schaltplänen aber nicht wirklich viel rauslesen kann. Mir geht es also wirklich um die Grundlagen und nicht darum schnell zu etwas funktionierendem zu kommen.
|
|
|
|
|
|
|
Vielleicht interessiert Dich ja dieses Buch hier: klick
Da steht zwar noch viel mehr drin, aber eventuell trifft das auch Deinen Geschmack.
|
|
|
|
|
|
|
Hab meinen Morsecode endlich so gut wie fertig. Ich hab nur noch ein Problem, und zwar sagt mir mein Programm beim verlassen der Funktion das mein Stack corrupted wäre...
Was bedeuted das genau?
|
Code: |
#include "stdafx.h"
void MorsezuBuchstaben(char* pt_speicher)
{
//Variablen
int i = 0;
char speicher[6];
char* pt_array_sp;
char tabellemorse[36][6]={ "-----" /*0*/, ".----" /*1*/, "..---" /*2*/, "...--" /*3*/, "....-" /*4*/, "....." /*5*/, "-...." /*6*/, "--..." /*7*/,
"---.." /*8*/, "----." /*9*/,
".-" /*a*/, "-..." /*b*/, "-.-." /*c*/, "-.." /*d*/, "." /*e*/, "..-." /*f*/, "--." /*g*/, "...." /*h*/, ".." /*i*/,
".---" /*j*/, "-.-" /*k*/, ".-.." /*l*/, "--" /*m*/, "-." /*n*/, "---" /*o*/, ".--." /*p*/, "--.-" /*q*/, ".-." /*r*/,
"..." /*s*/, "-" /*t*/, "..-" /*u*/, "...-" /*v*/, ".--" /*w*/, "-..-" /*x*/, "-.--" /*y*/, "--.." /*z*/ };
char tabellealpha[36]={'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
//Berechnung der Buchstaben
while(*pt_speicher !=0) //Eingabe überprüfen bis das ende des Eingabestrings erreicht wurde
{
pt_array_sp = &speicher[0]; //Pointer auf das array "speicher"
for(int n = 0; n <= 6; n++) // Schleife um eine Null in die array speicher zu speichern
{
*pt_array_sp = i;
pt_array_sp++;
}
}
return;
} |
|
Hat zufällig jemand noch ne Idee wie ich es umgehen kann, dass ich am string Ende ein Leerzeichen eingeben muss um das Ende zu erkennen?
Vielen Dank schon mal, otters
/EDIT: Meine stümperhaften Kommentare einfach übersehen
/EDIT2: Code gekürzt,da es sich erledigt hat falls es doch noch einen interssiert kann er ihn gern per pm haben
|
[Dieser Beitrag wurde 2 mal editiert; zum letzten Mal von otters am 14.05.2011 15:46]
|
|
|
|
|
|
Das Ende eines Strings ist in C doch mit einer 0 markiert und nicht mit einem Leerzeichen, oder verstehe ich deine Frage gerade nur falsch?
|
|
|
|
|
|
|
| Zitat von WeGi
Das Ende eines Strings ist in C doch mit einer 0 markiert und nicht mit einem Leerzeichen, oder verstehe ich deine Frage gerade nur falsch?
| |
ich brauch das leerzeichen damit er meinen pointer erhöht und somit irgendwann mal zu der 0 kommt....
/EDIT: sonst hab ich quasi in meiner zweiten for-schleife eine Endlosschleife
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von otters am 14.05.2011 0:09]
|
|
|
|
|
|
Kanns sein dass du drüber stolperst dass ganz am Ende des Strings kein Leerzeichen nach dem letzten Morsecode ist?
Wenn ich mich nicht vertue grad sollte die innere for-schleife mit "zaehler" als Variable da einfach... irgendwohin laufen.
|
|
|
|
|
|
|
| Zitat von B0rG*
Kanns sein dass du drüber stolperst dass ganz am Ende des Strings kein Leerzeichen nach dem letzten Morsecode ist?
Wenn ich mich nicht vertue grad sollte die innere for-schleife mit "zaehler" als Variable da einfach... irgendwohin laufen.
| |
ja das auch, aber selbst wenn ich hinter dem letzten morsezeichen ein Leerzeichen schreibe, bekomm ich nach beim return einen Fehler von wegen "stack around the variable speicher was corrupted"
|
|
|
|
|
|
|
|
Code: |
for(int n = 0; n <= 6; n++) // Schleife um eine Null in die array speicher zu speichern
{
*pt_array_sp = i;
pt_array_sp++;
} |
|
Die scheint mir auch 1 zu lang (0-6 statt 0-5).
Warum initalisierst du das Array so kompliziert?
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von B0rG* am 14.05.2011 0:46]
|
|
|
|
|
|
| Zitat von Klappfallscheibe
Ich hab' immer noch nicht so ganz verstanden, was eigentlich gewünscht wird. Selber Schaltungen entwickeln oder nur etwas fertiges nachbauen?
Aber ich werf' einfach mal Burkhard Kainkas Bastelecke in den Raum
| |
Das klingt schonmal interessant. Learning by doing, komplizierter kann man es ja immer machen.
Wäre halt schön, irgendwann auch die Theorie mit zu begreifen, einfach weil ich es als Ingenieur sinnvoll finde.
|
|
|
|
|
|
|
Hab mir mal Mathematica angeschaut. Das ist ja schon sehr krass O_O
|
|
|
|
|
|
|
| Zitat von Tarantula
Ich weiß nicht was sich Dogfish vorgestellt hat, aber ich hatte da was anderes im Kopf, noch simpler um ehrlich zu sein. Auch ein Buch mit etwas Theorie zu Schaltplänen halt. Wie liest man so Schematics usw.
Bei den Arduinos z.B. hab ich das Problem, dass ich das Zeug zwar programmieren, bei den Schaltplänen aber nicht wirklich viel rauslesen kann. Mir geht es also wirklich um die Grundlagen und nicht darum schnell zu etwas funktionierendem zu kommen.
| |
Bücher kann ich selber keine empfehlen, aber vielleicht ist hier ja was für dich dabei: mikrocontroller.net - Wiki: Absolute Beginner
|
|
|
|
|
|
|
| Zitat von B0rG*
|
Code: |
for(int n = 0; n <= 6; n++) // Schleife um eine Null in die array speicher zu speichern
{
*pt_array_sp = i;
pt_array_sp++;
} |
|
Die scheint mir auch 1 zu lang (0-6 statt 0-5).
Warum initalisierst du das Array so kompliziert?
| |
Weil ich nicht weiß wie es einfacher geht..
bin noch Anfänger
/EDIT: Du hattest recht, mein Stack ist jetzt nicht mehr korrupt
Aber warum trat der Fehler immer erst beim Verlassen der Funktion auf? Hab ja schließlich bei jedem Wort das Array falsch initialisiert
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von otters am 14.05.2011 9:54]
|
|
|
|
|
|
| Zitat von Newb1e
Haha, eben in der Vorlesung wieder so einen "WTF?"-Moment gehabt, der Mathematik so großartig macht
Ging um FFT (Fast Fourier Transform, numerisches Verfahren um effizient Fouriertransformationen zu berechnen). Dabei hat man einen Vektor . Diesen unterteilt man in zwei Vektoren . Jeden dieser Vektoren unterteilt man wieder nach dem selben Schema, und macht das immer wieder, bis man bei Vektoren der Länge Eins angekommen ist.
Die Frage ist jetzt: In welcher Reihenfolge müssen die Indizes am Ende stehen, damit es stimmt? (also anders formuliert: Wenn man das ganze in ein Baumdiagramm malt, welches y_k steht in der letzten Spalte an oberster Stelle, an zweiter, etc)
Dozent: Ja, da gibt es eine sehr schöne Merkregel. Sie schreiben alle Indizes untereinander in eine Tabelle (Bsp.: 0, 1, 2, 3)
Studenten: Okay.
Dozent: Dann übersetzen Sie jede Zahl in ihre Binärdarstellung (00, 01, 10, 11).
Studenten:
Dozent: Dann machen Sie eine Bitumkehrung (00 -> 00, 01 -> 10, 10 -> 01, 11 -> 11) und übersetzen die Zahlen zurück (0, 2, 1, 3).
Studenten:
Dozent: Das ist die Reihenfolge der Zahlen in der letzten Spalte und klappt auch für jedes größere N.
Studenten: http://www.abload.de/img/ayaw_are_you_a_wizard-5jo3.jpg
| |
Geil
|
|
|
|
|
|
|
Merkregel.
|
|
|
|
|
|
|
Vielen Dank, das sieht gut aus.
Schön mit den Literatur Angaben.
|
|
|
|
|
|
|
| Zitat von Xerxes-3.0
| Zitat von Newb1e
Haha, eben in der Vorlesung wieder so einen "WTF?"-Moment gehabt, der Mathematik so großartig macht
Ging um FFT (Fast Fourier Transform, numerisches Verfahren um effizient Fouriertransformationen zu berechnen). Dabei hat man einen Vektor . Diesen unterteilt man in zwei Vektoren . Jeden dieser Vektoren unterteilt man wieder nach dem selben Schema, und macht das immer wieder, bis man bei Vektoren der Länge Eins angekommen ist.
Die Frage ist jetzt: In welcher Reihenfolge müssen die Indizes am Ende stehen, damit es stimmt? (also anders formuliert: Wenn man das ganze in ein Baumdiagramm malt, welches y_k steht in der letzten Spalte an oberster Stelle, an zweiter, etc)
Dozent: Ja, da gibt es eine sehr schöne Merkregel. Sie schreiben alle Indizes untereinander in eine Tabelle (Bsp.: 0, 1, 2, 3)
Studenten: Okay.
Dozent: Dann übersetzen Sie jede Zahl in ihre Binärdarstellung (00, 01, 10, 11).
Studenten:
Dozent: Dann machen Sie eine Bitumkehrung (00 -> 00, 01 -> 10, 10 -> 01, 11 -> 11) und übersetzen die Zahlen zurück (0, 2, 1, 3).
Studenten:
Dozent: Das ist die Reihenfolge der Zahlen in der letzten Spalte und klappt auch für jedes größere N.
Studenten: http://www.abload.de/img/ayaw_are_you_a_wizard-5jo3.jpg
| |
Geil
| |
Aber wenn man sowas selber merken und aufschreiben würde, hieße es mit Sicherheit: Jaja, das funktioniert jetzt vllt im Einzelfall, aber das dürfen sie nicht immer anwenden :x
Und zu den elektro-Sachen: sieht super aus, da werd ich gleich mal reinschnuppern Danke!
|
|
|
|
|
|
|
Ich steh immer noch aufm Schlauch.
i,j,k kann ich anscheinend nicht einfach als fixe variable mitnehmen, oder?
|
|
|
|
|
|
Thema: pOT-Informatiker, Mathematiker, Physiker V ( Haaahaaaaahaa...LabView...Hahahahaaa...oh wow ) |
|