Dessa trix är i första hand avsedda för att tillämpas på en mikrokontroller som ofta saknar beräkningsmöjligheter i någon större utsträckning.
Division är ofta en kostsam process för en mikrokontroller, och därför finns normalt inga divisionsinstruktioner eftersom det skulle kosta extra i form av speciell hårdvara, eller inbyggda algoritmer. Det är ofta upp till programmeraren att skriva egna divisionsrutiner. Om möjligt ska man undvika divisioner eller åtminstone försöka använda så få som möjligt. Ibland kan det vara möjligt att formulera om en division till att använda division med tvåpotenser, och det är ju enkelt eftersom det bara handlar om att skifta talet till höger ett visst antal steg. Det ska vi titta närmare på.
Division med 10 är ju ganska vanligt eftersom vi människor använder ett decimalt talsystem. Antag att vi vill dela talet x med 10, det skulle man ju kunna göra på följande sätt:
x*25.6/256
25.6 är ju ett decimaltal, vilket inte passar så bra i en mikrokontroller så vi avrundar till 26 och får då:
x*26/256
Att dela med 256 är ju väldigt enkelt genom att bara bortse från dom 8 minst signifikanta bitarna av resultatet, så en ungefärlig division med 10 skulle alltså kunna åstadkommas genom multiplikation med 26. Om man använder den metoden för x i intervallet [0,255] så blir aldrig avvikelsen någon gång större än 1 jämfört med en korrekt division med trunkering av decimaldelen. Dessutom så ger t ex 169/10 resultatet 16 vid en korrekt heltalsdivision, men med “multiplikation med 26” så blir resultatet 17, vilket ju faktiskt är närmare 16.9 som är det exakta resultatet.
Ovan approximerade vi 25.6 med 26 och fick på så sätt ett ungefärligt resultat vid divison med 10. Det är ju själva approximationen som orsakar avvikelsen från ett korrekt heltalsresultat. Det visar sig dock att om man provar med andra multiplikations/divisionstermer så kan man få ett bättre resultat, t o m ett helt korrekt resultat.
Antag alltså att vi gör vår division på följande sätt:
x*204.8/2048
Åter igen gör vi en approximation där nu 204.8 blir 205 och har på så sätt gjort en bättre approximation än då 25.6 blev 26 eftersom det procentuella förhållandet mellan 204.8 och 205 är bara 0.1% men mellan 25.6 och 26 är det 1.6%. Vår funktion för att dela med 10 blir alltså:
x*205/2048 = x*205/2/2/2/256
På samma sätt som tidigare bortser vi från dom 8 minst signifikanta bitarna av resultatet (dvs dela med 256). Sedan återstår bara att dela återstående bitarna av högre ordning med 2 tre gånger. Det kan ju enkelt åstadkommas genom att skifta dessa bitar åt höger tre gånger. Med den här metoden visar det sig att man får ett helt korrekt resultat för heltalsdivision med 10 för ett x i intervallet [0,255].
På samma sätt som ovan går det även att hitta en lämplig faktor för division med 100 för att få ett helt korrekt resultat. Det visar sig att följande funktion är lämplig:
x*40.96/4096
vilket är ungefär:
x*41/4096 = x*41/2/2/2/2/256
vilket endast avviker med en knapp promille från en korrekt division med 100.
Bortse från dom 8 minst signifikanta bitarna (dela med 256) och skifta dom återstående 4 steg åt höger. Resultatet blir då helt korrekt för x i intervallet [0,255].
Ett sätt att göra en generell division A/B är ju att räkna hur många gånger man kan subtrahera B från A. Det ska vi göra här också men med en twist så att det hela blir betydligt effektivare.
Om X=A/B så ger det att A=B*X. Betrakta resultatet X som ett binärt tal och skriv om på följande sätt:
A = B * ( X15*2^15 + X14*2^14 + ... + X1*2^1 + X0*2^0 )
A = B*X15*2^15 + B*X14*2^14 + ... + B*X1*2^1 + B*X0*2^0
Nu skulle man kunna subtrahera term för term av högerledet från A med början av den mest signifikanta termen B*X15*2^15 på så sätt att om A >= B*2^15 så genomförs subtraktionen och X15 1-ställs annars genomförs inte subtraktionen och X15 0-ställs. Sedan fortsätter man med termen för X14, X13 o s v till X0. På så sätt bygger man upp resultatet av X bit för bit och kvar i A finns den s k resten efter divisionen.
Det kan ju dock vara lite bökigt att behöva räkna ut termerna B*2^15, B*2^14 o s v innan dom subtraheras från A, så istället subtraherar vi B från A/2^15 (om A/2^15 >= B) och B från A/2^14 (om A/2^14 >= B) o s v vilket leder till samma resultat. Att räkna ut A/2^15 är ju väldigt enkelt då det bara handlar om att bortse från dom 15 sista bitarna. Samma sak för A/2^14 o s v.
Låt oss titta på ett exempel. Antag att vi vill utföra divisionen 12345/67:
Nedan markerar vi gränsen mellan ett hållregister HR och A (=12345). Initialt betraktar vi A
som om det vore delat med 2^16 och sedan skiftar man bit för bit åt vänster in i HR.
Vid första skiftet blir då HR det samma som A delat med 2^15, vid andra A delat med 2^14 o s v.
HR jämförs i varje steg med B (=67) för att avgöra om aktuell bit i X ska 1- eller 0-ställas.
---HR---|--------A--------
00000000 00110000 00111001
00000000 01100000 01110010 HR = 0 >= 67 ? Nej => X15=0
00000000 11000000 11100100 HR = 0 >= 67 ? Nej => X14=0
00000001 10000001 11001000 HR = 1 >= 67 ? Nej => X13=0
00000011 00000011 10010000 HR = 3 >= 67 ? Nej => X12=0
00000110 00000111 00100000 HR = 6 >= 67 ? Nej => X11=0
00001100 00001110 01000000 HR = 12 >= 67 ? Nej => X10=0
00011000 00011100 10000000 HR = 24 >= 67 ? Nej => X9 =0
00110000 00111001 00000000 HR = 48 >= 67 ? Nej => X8 =0
01100000 01110010 00000000 HR = 96 >= 67 ? Ja => X7 =1 => HR=96-67=29 = 00011101 =>
00011101 01110010 00000000
00111010 11100100 00000000 HR = 58 >= 67 ? Nej => X6 =0
01110101 11001000 00000000 HR =117 >= 67 ? Ja => X5 =1 => HR=117-67=50 = 00110010 =>
00110010 11001000 00000000
01100101 10010000 00000000 HR =101 >= 67 ? Ja => X4 =1 => HR=101-67=34 = 00100010 =>
00100010 10010000 00000000
01000101 00100000 00000000 HR = 69 >= 67 ? Ja => X3 =1 => HR=69-67= 2 = 00000010 =>
00000010 00100000 00000000
00000100 01000000 00000000 HR = 4 >= 67 ? Nej => X2 =0
00001000 10000000 00000000 HR = 8 >= 67 ? Nej => X1 =0
00010001 00000000 00000000 HR = 17 >= 67 ? Nej => X0 =0
Resultatet X = [X15 ... X0] = [00000000 10111000] = 184
Hållregistret HR = [00010001] = 17
Kontroll 184 * 67 + 17 = 12345 !
Låt oss utarbeta en metod för att snabbt och enkelt multiplicera med PI, dock med vissa begränsningar men ändå.
PI är ungefär 3.14159265359 Det ger att PI*256 blir ungefär 804. Det är ett stort tal som inte ryms inom 8 bitar så vi dividerar det med 2 två gånger och får då 201. Metoden för att räkna ut x*PI blir då att multiplicera x med 201, skifta resultatet två gånger åt vänster (multiplikation med 2 två gånger) och sedan bortse från dom 8 minst signifikanta bitarna (division med 256).
T ex, om vi vill multiplicera 169 med PI så börjar vi med att multiplicera med 201:
Decimalt 169 * 201 = 33969
Binärt 10101001 * 11001001 = 10000100 10110001
Resultatet skiftas sedan två steg åt vänster:
Resultat 00000000 10000100 10010001
Vänsterskift 00000001 00001001 00100010
Vänsterskift 00000010 00010010 01000100
Bortse från dom 8 minst signifikanta bitarna:
169 * PI = 00000010 00010010 -------- = 530 (decimalt)
Det korrekta decimala resultatet för 169*PI är ungefär 530.9 så vi kom ju ganska nära, eller hur. En begränsning vi har infört är dock att x ska rymmas inom 8 bitar.
En dator lagrar som bekant sina tal i binärt format. Som människa vill man gärna se talet decimalt, siffra för siffra, även kallat BCD-format. Omvandlingen där emellan är inte trivial så vi ska titta på en metod som är effektiv och förbluffande enkel. Det är dock inte lika enkelt att förstå varför det fungerar.
Metoden kan beskrivas som följer. Man vänsterskiftar binärtalet och BCD-resultatet bit för bit så att binärtalets mest signifikanta bit går in i BCD-resultatets minst signifikanta bit. Efter varje sådant skift sker en justering av BCD-talet på så sätt att 3 adderas till respektive BCD-siffra, i tur och ordning, med början på mest signifikant BCD-siffra. Om adderingen innebär att mest signifikant bit inom siffran (dvs bit 3) 1-ställs så behålls siffran som den är, annars återställs den som den var innan adderingen. Hela förloppet upprepas tills alla bitar skiftats, dock sker ingen justering av BCD-talet efter sista skiftningen.
Vi illustrerar det hela med ett exempel. Antag att vi vill omvandla det binära talet 10101100 (=172) till BCD-format:
BCD2 BCD1 BCD0 Binärt
0000 0000 0000 10101100 Initialt tillstånd
0000 0000 0001 01011000 Vänsterskift 1
0000 0000 0001 01011000 Efter addering med 3 och kontroll av bit 3
0000 0000 0010 10110000 Vänsterskift 2
0000 0000 0010 10110000 Efter addering med 3 och kontroll av bit 3
0000 0000 0101 01100000 Vänsterskift 3
0000 0000 1000 01100000 Efter addering med 3 och kontroll av bit 3, siffran behålls
0000 0001 0000 11000000 Vänsterskift 4
0000 0001 0000 11000000 Efter addering med 3 och kontroll av bit 3
0000 0010 0001 10000000 Vänsterskift 5
0000 0010 0001 10000000 Efter addering med 3 och kontroll av bit 3
0000 0100 0011 00000000 Vänsterskift 6
0000 0100 0011 00000000 Efter addering med 3 och kontroll av bit 3
0000 1000 0110 00000000 Vänsterskift 7
0000 1011 1001 00000000 Efter addering med 3 och kontroll av bit 3, siffran behålls
0001 0111 0010 00000000 Vänsterskift 8
Resultat: BCD2=1, BCD1=7, BCD0=2, dvs 172!
Metoden fungerar för godtyckligt antal bitar i det binära talet.