Potenzieren ohne <math.h>

Hero_123

Mitglied
17. Sep. 2010
183
3
18
Sprachen
  1. ANSI C
Hallo!

Ich möchte in einer for-Schleife Potenzen zur Basis 10 erstellen (10^i mit i = 0 ....n) ohne die math.h inkludieren zu müssen.
Leider interpretiert der Compiler das "^" Zeichen als EXCLUSIVE OR und macht somit aus 10^2 => 8 und nicht wie gewollt 100.

Wie kann ich diese Potenzierung ohne math.h machen? Ich habe schon im Netz gesucht, aber nichts gefunden :(

Für eine Lösung / zielführende Lösungshinweise (ohne math.h) wäre ich dankbar

mfg

Hero_123
 
im Prinzip willst Du Zehnen multiplizieren, und das n-oft. Quick'n'dirty geht das mit einer Schleife, und wenn der verwendete Controller multiplizieren kann (Megas, XTinies) ist das gar nicht mal so ineffizient.
10 entspricht 1010binär. Mit 10 zu multiplizieren erfordert also eigentlich nur viermal schieben und zwei Additionen...

Wie groß kann n höchstens werden?
 
Hallo LotadaC

Vielen Dank für Deine Hilfe!

Das mit dem Schieben habe ich schon mal (irgendwo) gelesen ...

Also:
i = 0 => 10^0 = 1 => 0000 0000 0000 0001
i = 1 => 10^1= 10 => 0000 0000 0000 1010
i = 2 => 10^2 = 100 => 0000 0000 0110 0100
i = 3 => 10^3 = 1000 => 0000 0011 1110 1000
i = 4 => 10^4 = 10.000 => 0010 0111 0001 0000

Hierbei erschließt sich mir (noch) nicht, wie/was ich viermal schieben und zweimal addieren muss...

Ich will nur:
......
/* aufspalten des ADC-Wertes in Zahlen zwecks Darstellung auf 7-Seg-Anzeige */
for(i = 0; i < laenge; i++) {wert = (adc/10^i)%10} /* wobei das 10^i nicht fkt */
.......

habe das bislang so gelöst:
wert[0] = (adc/1)%10; /* acd = uint16_t */
wert[1] = (adc/10)%10;
wert[2] = (adc/100)%10;
wert[3] = (adc/1000)%10;

mfg

Hero_123
 
Von der Zerlegung einer Zahl in Dezimalstellen hattest Du in #1 ja auch nichts geschrieben. Da gings nur am das berechnen von Potenzen bzw genauer von Zehnerpotenzen.

Das würde bedeuten, daß Zehnen multipliziert werden müssen. Einige AVR können multiplizieren, aber nicht alle - dann muß geschoben und addiert werden.
Wie geht das mit der binären Multiplikation genau?
Beispiel:
Faktor 1Faktor 2Produkt
000011000001101000000000Produkt erstmal null setzen
00000110 -> C=00001101000000000F1 einmal rechtsschieben, dabei fällt 'ne 0 ins Carry also wird F2 nicht zum Produkt addiert
000001100011010000000000F2 einmal linksschieben
00000011 -> C=00011010000000000F1 rechtsschieben, C=0 alsoF2 nicht addieren
000000110110100000000000F2 linksschieben
00000001 -> C=10110100001101000F1 rechtsschieben, wegen Carry=1 F2 auf Produkt addieren
000000011101000001101000F2 linksschieben
00000000 -> C=1110100001 00111000F1 rechtsschieben, wegen C=1 F2 auf Produkt addieren
F1=0, fertig

Also quasi F1 schieben, auf Carry prüfen, davon abhängig F2 auf Ergebnis addieren und dann F2 schieben. Solange bis F1 null ist.

Jetzt wissen wir aber, daß F1 = 10 ist , also &B1010 - damit vereinfacht sich der Rechenweg auf drei(!) shifts und zwei Additionen (bzw eine Kopie und eine Addition): Bsp 23*10
FaktorErgebnis
00010111xxxxxxxxFaktor einmal linksschieben
00101110xxxxxxxxFaktor nach Ergebnis kopieren
0010111000101110Faktor zweimal nach links schieben
1011100000101110Faktor auf Ergebnis addieren
1011100011100110fertig
Du willst aber eigentlich gar nicht (Zehner)Potenzieren, sondern höchstens kaskadiert durch Zehn teilen...
 
Hallo LotadaC

Vielen Dank für Deine Hilfe!

Von der Zerlegung einer Zahl in Dezimalstellen hattest Du in #1 ja auch nichts geschrieben. Da gings nur am das berechnen von Potenzen bzw genauer von Zehnerpotenzen.

Du willst aber eigentlich gar nicht (Zehner)Potenzieren, sondern höchstens kaskadiert durch Zehn teilen...

Ja, im Endeffekt ist es eine kaskadierte Teilung durch Zehn, wollte es aber "intelligent" mittels for-Schleife und Potenzieren machen ;)

Woher weißt Du das alles - schieben, test des Carry-Flag, addieren? Wenn das Grundlagen sind, habe ich ein Problem; ich kenne zwar links-schieben & rechts-schieben, aber wie man mittels dieser "Bitschubsereien" Multiplizieren & Addieren kann, war mir nicht klar.

mfg

Hero_123
 
Hat zwar eigentlich nichts mehr mit Deinem Thema zu tun, aber Du bist ja wissbegierig...
Wir erinnern uns an die schriftliche Multiplikation aus der Grundschule - als Beispiel mal 123*117

Code:
123 * 117
---------
    123         1*123
     123        1*123
      861       7*123
---------       zusammenaddieren
    14391
Die einzelnen Summanden sind um 'ne Zehnerstelle verschoben, was hast Du eigentlich gerechnet?
Genau genommen hast Du die 117 in seine Dezimalstellen zerlegt - 117 = 1*102 +1*101 + 7*100 - und die dann jeweils mit 123 Multipliziert, und die Teilergebnisse zusammenaddiert.
Binär ist das genau dasselbe, nur viel einfacher...
Dezimal hast Du den einen Faktor dreimal mit irgend'ner dezimalen Ziffer multipliziert - im binären gibt's aber nur zwei Ziffern - die Eins oder die Null
Unsere 123 entspricht &B01111011, mit &B0 multipliziert ergibt das &B00000000, mit &B1 multipliziert ändert sich nichts (&B01111011). Die Multiplikation mit den Zehnerpotenzen (dezimal linksschieben) sind hier Multiplikationen mit Zweierpotenzen (binär linksschieben).
Also nochmal in Binär:
Code:
01111011 * 01110101
-------------------
    00000000          0*'123'
     01111011         1*'123'
      01111011        1*'123'
       01111011       1*'123'
        00000000      0*'123'
         01111011     1*'123'
          00000000    0*'123'
           01111011   1*'123'
-------------------   addieren
   ‭ 011100000110111‬

Jetzt schaust Du Dir das mal von unten nach oben an.
weil das letzte Bit der '117' 'ne '1' war haben wir die '123' hingeschrieben
weil das vorletzte Bit der '117' keine 1 war, haben wir statt einer linksgeschobenen '123' (also 123*2) nur 'ne 0 hingeschrieben
für das gesetzte drittletzte Bit kommt 'ne zweimal linksgeschobene '123' (also 123*2*2) dazu.
Soweit klar?

Ok, die ganzen Nullen brauchen wir natürlich nicht zu addieren bleibt:
Code:
       01111011  für Bit 0
     01111011    für Bit 2
   01111011      für Bit 4
  01111011       für Bit 5
 01111011        für Bit 6
 --------------
 ‭11100000110111‬
Wie prüfen wir, ob die Bits in '117' eins oder null sind?
Indem wir es einfach einmal nach rechts schieben - das rausgeschobene Bit landet dabei im Carry-Bit des Statusregisters.
Als nächstes prüfen wir das Carry, wenn es gesetzt ist, addieren wir unsere '123' zum Ergebnis hinzu, sonst überspringen wir diese Addition (also das Überprüfen ist einfach ein bedingter Sprung über die Addition hinweg - Branch if Carry Clear (BRCC)).
Danach wird die '123' einmal nach links geschoben.
Das ganze wird wiederholt, bis '117' leer (=0) ist.

Verständlicher?
 
  • Like
Reaktionen: TommyB
Hallo LotadaC

Vielen Dank für diese ausführliche Erklärung :good2:

Als "Hochsprachler" kann ich mit dem Carry-Bit und Statusregister nichts anfangen (ich weiß nicht, wie ich darauf Zugriff habe bzw welches Register ich abfragen müsste), ich würde halt testen, ob Bit 0 = "0" und dementsprechend addieren bzw nicht addieren (nicht addieren, wenn Bit 0 = "0") - soweit alles klar ;).

Wie funktioniert es denn, wenn ich dividieren will?

mfg

Hero_123
 
Das SREG (Statusregister) ist eines der wichtigsten Register. Bei vielen Rechenoperationen können bestimmte besondere Zustände auftreten. Die AVR sind 8Bit-Prozessoren, fast alle Operationen basieren also auf Bytes.
Addierst oder subtrahierst Du zwei Bytes, kann das Ergebnisbyte überlaufen - dann wird automatisch das Überlaufbit (Carry) gesetzt. Tritt dabei kein Überlauf ein, wird das Carry gelöscht. Ist das Ergebnis einer Operation Null, wird das Zero-Bit gesetzt (und sonst gelöscht). Außerdem gibt es noch ein Halb-Carry-Bit (Überlauf von Bit 3 auf Bit 4), ein Negative-Bit wenn das Ergebnis im Sinne des Zweierkomplements (quasi 8-Bit-Integer) negativ ist, usw.

Beim Schieben wird der Inhalt eines Rechenregisters um eine Stelle nach links/rechts verschoben - die leere Position wird mit einer 0 aufgefüllt, das was rausgeschoben wird, landet im Carry. Für alle Bits im SREG gibt es bedingte Sprunganweisungen, die nur dann springen, wenn das Bit gesetzt bzw gelöscht ist.

Nehmen wir mal an, Du hast in Deiner Hochsprache sowas wie "If A=7 then tue was else tue was anderes"
Übersetzt wird das in:
Lade A in ein Rechenregister (LDS Rd, 'A')
Prüfe, ob Rechenregister=7 (CPE Rd, 7 - Compare with immediate, intern wird quasi Rd-7 gerechnet - ist das Ergebnis =0, wird das Zero gesetzt)
Wenn Z nicht gesetzt, springe nach "tue was anderes" (BRNE tue was anderes - Branch if not equal, springe wenn Z nicht gesetzt)
"Tue was"
springe zur nächsten Instruktion (RJMP - relative jump)
"Tue was anderes"

Hier wurde explizit mit Compare verglichen - man kann aber manchmal auch ausnutzen, das Instruktionen selbst Bits im SREG manipulieren. Wenn Du zB eine Schleife hast, die n-Mal durchlaufen werden soll, könnte man das auch so machen
Schleifenanfang
mach irgendwas
inkrementiere Zähler
prüfe ob Zähler=n (Compare)
Springe in Abhängigkeit von Z zum Schleifenanfang. (BRNE)
Aber das Inkrementieren (bzw auch das dekrementieren) manipuliert selbst das Z, also geht's auch einfacher andersrum
Schleifenanfang
mach irgendwas
dekrementiere Zähler (manipuliert außerdem Z)
springe in Abhängigkeit von Z zum Schleifenanfang

So, für Dich ist das nur Hintergrundwissen (zumindest wäre es ein Vorteil, wenn Du's weißt) - Du verwendest natürlich Deine Hochsprachenbefehle - aber manchmal sollte man trotzdem in etwa(!!) wissen, wie der Prozessor das in Maschinenprozessen umsetzt, um einschätzen zu können ob dieser oder jener Weg für die Lösung eines bestimmten Problems angemessen ist.

Ich bin eigentlich der Überzeugung, das C auch ohne Mathe-Bibliothek multiplizieren und dividieren kann - da wird's eher um Potenzen, Wurzeln, Trigonometrie und sowas gehen...

Was ist denn Dein konkretes Ziel? Das 10-Bit-Ergebnis als dezimale Zahl auf Siebensegmenten ausgeben? Dafür reicht die Division (mit Rest) durch 10. (In Bascom gibt's nur entweder Rest oder Division (obwohl der Rest ein Abfallprodukt der Division ist - nämlich genau das, was übrigbleibt (Rest eben), und ich weiß, in welchem Register Bascom diesen Rest nach der Division liegenläßt, und kann ihn da auslesen) - wie das In "Klammercode" ist, kann ich nicht sagen...)

Wie funktioniert es denn, wenn ich dividieren will?
Im Prinzip auch wieder genau so, wie Du in der Grundschule schriftlich dividieren gelernt hast - nur eben viel einfacher, da binär.
Wozu mußtest Du damals das kleine Einmaleins pauken? Damit Du 'ne Lookup-Table für die schriftliche Division im Kopf hast.
Für die Aufgabe 92527:13 mußtest erstmal bestimmen, wie oft die 13 in die 9 - gar nicht, also ... in die 92 paßt. Lookup-Table abrufen -> 7.
Als nächstes hast Du rückwärts wieder beides multipliziert, und von den 92 abgezogen - also nichts anderes als den Rest bestimmt.
Binär brauchst Du keine Lookup-Table auswendig lernen. Entweder es paßt einmal rein, oder eben nicht. Entweder der Divisor ist kleiner, oder nicht. Entsprechend hast Du 'ne eins oder 'ne null im Ergebnis.
Rückwärts muß auch nichts multipliziert werden - entweder es wird abgezogen, oder nicht...

Falls Du mal Zeit zum lesen hast, empfehle ich Dir mal die ersten Seiten DES ASM-Tutorials. Sehr amüsant...
 
Hallo LotadaC

Vielen Dank für Deine ausführliche Erklärung :good2:

So, für Dich ist das nur Hintergrundwissen (zumindest wäre es ein Vorteil, wenn Du's weißt) - Du verwendest natürlich Deine Hochsprachenbefehle - aber manchmal sollte man trotzdem in etwa(!!) wissen, wie der Prozessor das in Maschinenprozessen umsetzt, um einschätzen zu können ob dieser oder jener Weg für die Lösung eines bestimmten Problems angemessen ist.
Stimmt :good3:

Ich bin eigentlich der Überzeugung, das C auch ohne Mathe-Bibliothek multiplizieren und dividieren kann - da wird's eher um Potenzen, Wurzeln, Trigonometrie und sowas gehen...

Was ist denn Dein konkretes Ziel? Das 10-Bit-Ergebnis als dezimale Zahl auf Siebensegmenten ausgeben? Dafür reicht die Division (mit Rest) durch 10.
Stimmt - für meinen Zweck reicht dies vollkommen, ich wollte es nur etwas "eleganter" (mit 'ner Schleife) machen, aber das Elegante ist nicht immer das Sinnvolle ;).

Falls Du mal Zeit zum lesen hast, empfehle ich Dir mal die ersten Seiten DES ASM-Tutorials. Sehr amüsant...

Vielen Dank für diesen link, ich habe reingeschaut - ist für mich als "Klammercoder" sehr interessant

mfg

Hero_123
 

Über uns

  • Makerconnect ist ein Forum, welches wir ausschließlich für einen Gedankenaustausch und als Diskussionsplattform für Interessierte bereitstellen, welche sich privat, durch das Studium oder beruflich mit Mikrocontroller- und Kleinstrechnersystemen beschäftigen wollen oder müssen ;-)
  • Dirk
  • Du bist noch kein Mitglied in unserer freundlichen Community? Werde Teil von uns und registriere dich in unserem Forum.
  •  Registriere dich

User Menu

 Kaffeezeit

  • Wir arbeiten hart daran sicherzustellen, dass unser Forum permanent online und schnell erreichbar ist, unsere Forensoftware auf dem aktuellsten Stand ist und der Server regelmäßig gewartet wird. Auch die Themen Datensicherheit und Datenschutz sind uns wichtig und hier sind wir auch ständig aktiv. Alles in allem, sorgen wir uns darum, dass alles Drumherum stimmt :-)

    Dir gefällt das Forum und unsere Arbeit und du möchtest uns unterstützen? Unterstütze uns durch deine Premium-Mitgliedschaft!
    Wir freuen uns auch über eine Spende für unsere Kaffeekasse :-)
    Vielen Dank! :ciao:


     Spende uns! (Paypal)