Hallo, bin neulich auf folgenden Wiki-Artikel gestoßen: http://de.wikipedia.org/wiki/Vedische_Mathematik Mit solchen Schnellrechenvorschriften müsste man doch eigentlich auf einem µC von Fall zu Fall viel Zeit und Energie beim Rechnen sparen können... Was meint Ihr?
Mirko schrieb: > Rechnet dein µC im Zehnersystem??? Nein, aber das sollte kein Hinderungsgrund sein, man kann das ganze ja z.B. in C im Dezimalsystem programmieren.
olli schrieb: > man kann das ganze ja > z.B. in C im Dezimalsystem programmieren. Allein das braucht dann mehr Rechenzeit, als eine "normale" Multiplikation im µC ...
es gibt auch Bücher über binäre Mathematik! Leider etwas in vergessenheit geraten da es heutzutage ja schnellere Taktraten gibt. Bestimmte Algorithmen lassen sich so 3-4x schneller abarbeiten als mit nem Top-Compiler.
Bestimmt interessant das mal durch zu spielen- ABER glaubst du nicht, dass die Chip-Bauer nicht auch was am Kasten haben? ich persönlich kann mir nicht vostellen, dass du genug Zeit mit einer Beschleunigung raus bekommst, um die Zeit der ganzen Überprüfungen wieder rein zu holen. Ausserdem haben die meisten Compiler schon selber Optimierungen dabei- am bekanntesten das Shiften wenn es um ganzzahlige(pos und neg!) Potenzen von 2 geht.
Bastler schrieb: > Bestimmte Algorithmen lassen sich so 3-4x schneller abarbeiten als mit > nem Top-Compiler. Hast du zufällig ein Beispiel zur Hand? Marcus B. schrieb: > Ausserdem haben die meisten Compiler schon selber Optimierungen dabei- > am bekanntesten das Shiften wenn es um ganzzahlige(pos und neg!) > Potenzen von 2 geht. Ach so, dann sind solche Rechenabkürzungswege mehr oder weniger ein alter Hut!?
olli schrieb: > Was meint Ihr? Diese Rechenregeln gelten erstmal nur für das 10er-System. Der Grund, warum gerade dieses nicht bei ALUs erwendet wird, ist die Einfachheit des 2er-Systems. Eine Addition einer Stelle bricht sich auf 4 Fälle herunter (00,01,10,11) und ist somit platzgünstig und ohne Spezialfälle realisierbar und außerdem beliebig skalierbar (mit Übertrag) auf z.B. 128bit und mehr. Auch dauert eine Addition im 2er-System immer gleichlang, was der ganzen Ablaufsteuerung in Prozessoren zu gute kommt. :-)
Intel macht genau so was http://board.gulli.com/thread/1651047-intel-patentiert-algorithmus-zur-schnelleren-multiplikation-grosser-zahlen/ aber halt mit besser passenden Algorithmen als gerade dem unsäglichen 10er System.
Das Bruchrechnen wie auf der Wikiseite beschrieben, ist ja nichts besonderes. Mach ich immer so.
Les lieber die Wiki-Artikel über den Karatsuba und den
Toom-Cook-Algorithmus. Das sind Algorithmen die IRL auch was bringen.
Sachen wie Vedische Mathe oder das Trachtenberg System sind Algorithmen,
von denen man nur profitiert, wenn man die Rechnung im Kopf macht.
>es gibt auch Bücher über binäre Mathematik!
Irgendwelche (E)Book Links?
Leider habe ich selbst keine Bücher oder Titel zu den Büchern. Ich habe auf einem Sminar mite einem anderen Entwickler geredet. Dieser meinte dass sich diese Firma kleine Funktionen in Assembler eben mit dieser (teils vergessenen) Mathematik zurechtgelegt haben und nun 3-4x schneller sind als aktuelle Comnpiler.
Bastler schrieb: > Leider habe ich selbst keine Bücher oder Titel zu den Büchern. > Ich habe auf einem Sminar mite einem anderen Entwickler geredet. > Dieser meinte dass sich diese Firma kleine Funktionen in Assembler eben > mit dieser (teils vergessenen) Mathematik zurechtgelegt haben und nun > 3-4x schneller sind als aktuelle Comnpiler. Er lügt. 3-4 ist nicht drinnen.
Marcus B. schrieb: > ich persönlich kann mir nicht vostellen, dass du genug Zeit mit einer > Beschleunigung raus bekommst, um die Zeit der ganzen Überprüfungen > wieder rein zu holen. Sewh ich auch so. Diese ganzen Regeln funktionieren nur deshalb, weil wir Menschen wesentlich schneller Entscheidungen treffen können, als wir rechnen können. Wir sehen eine Zahl an und 'wissen' ohne lange nachzudenken, dass die letze Ziffer 5 ist und daher Sonderregeln greifen. Einem Computer ist das aber egal. Wenn der feststellen soll, ob die letzte Ziffer 5 ist, muss er erst mal eine Modulo-Division machen. Super. Erst mal Modulo-Dividieren um rauszufinden ob er für eine Multiplikation mit 5 den schnellen Weg gehen kann, oder ob die Multiplikation konventionell durchgeführt werden muss. Das wirds dann wohl nicht bringen. > Ausserdem haben die meisten Compiler schon selber Optimierungen dabei- > am bekanntesten das Shiften wenn es um ganzzahlige(pos und neg!) > Potenzen von 2 geht. Jup. Compiler haben für viele Dinge in denen Konstante involviert sind, spezielle Vorschriften mit, die bei Bedarf zum Einsatz kommen. zb Multiplikation mit 10 Einfach. 2 mal links shiften, die Originalzahl nochmal dazugezählt und noch einmal links geshiftet. Die generischen Algorithmen, die Compiler mithaben sind schwer zu toppen. Einfacher wird es, wenn man Annahmen und Vereinfachungen treffen kann, die speziell auf die Aufgabenstellung zugeschnitten sind. Diese Dinge greifen dann aber erst bei komplizierteren Berechnungen. Eine Addition oder Multiplikation kriegst du selber auch nicht schneller hin, als das was der Compiler mit hat. Bei Wurzeln oder trigonometrischen Funktionen sieht die Sache anders aus. Da müssen die mitgelieferten Funktionen universell sein und damit auch mit Fällen zurecht kommen, die in meiner App nicht vorkommen. Und das kann man ausnutzen.
Hi >Dieser meinte dass sich diese Firma kleine Funktionen in Assembler eben >mit dieser (teils vergessenen) Mathematik zurechtgelegt haben und nun >3-4x schneller sind als aktuelle Comnpiler. Als notorischer Assemblerprogrammierer kann ich mir das gut vorstellen. MfG Spess
zu Karl Heinz Buchegger schrieb: > Er lügt. > 3-4 ist nicht drinnen. und spess53 schrieb: >>3-4x schneller sind als aktuelle Comnpiler. > > Als notorischer Assemblerprogrammierer kann ich mir das gut vorstellen. Meine Ansicht liegt zwischen diesen Aussagen. Wenn man allgemein Berechnungs-Methoden vergleicht, ist der Faktor 3-4 gegenüber einem Compiler nicht drin. Wenn Berechnungen weit im Kontext anderer Arbeitsschritte untergebracht werden, sieht die Welt schon anders aus. Da kommen Dinge zum Tragen, die ein Compiler nicht berücksichtigen kann. Von "strukturierter" Programmierung wie sie allgemein gelehrt wird, ist das allerdings sehr weit weg. Bastler schrieb: > Ich habe auf einem Sminar mite einem anderen Entwickler geredet. > Dieser meinte dass Oft beziehen sich solche Aussagen auf eine zuvor vorhandene Implementierung, die bereits ersetzt ist. Es ist keine Aussage über deren Qualität. Wahrscheinlich hätte der Compiler, anders gefüttert, auch bessere Ergebnisse erzielen können.
Naja, ich hatte auch schon Code angepasst in dem mehrere Funktionen aufgerufen wurden um einen Pin zu setzten. Da geht pro Aufruf Zeit verloren. Ein guter C-Code bringt auch oft viel. Beispielsweise bei einer Mittelwertbildung 16 32 64 Werte verwenden anstelle von 50. Um Zeit zu sparen gibt es mittlerweile auch schon in den 8-Bittern DMA oder ähnliche Hardwareteile.
Vor allem gelten diese Regeln zum Kopfrechnen. Ein uC hat kein Problem damit 113 mit 207 zu multiplizieren. Ein ATmega macht das z.B. in 2 Taktzyklen. Ich glaube kaum, daß man das schneller damit hinbekommt. Wenn man einen uC als einen Rechner mit einem 256er Zahlensystem darstellt, könnte man die Regeln anwenden. Dazu muß man die Regeln anpassen und vor allem muß man jedes Mal prüfen, welche Regel greift, um im Zweifelsfall doch wieder auf die herkömmliche Art zu rechnen. Und die Berechnung dauert dann länger. Ausserdem frisst es Speicherplatz. Gruß Jobst
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.