Dela med 10 utan matte-bibliotek

[Icecap]

Att multiplicera med 10 utan att använda färdiga matte-bibliotek är ju enkelt:
A har värdet som ska multipliceras med 10.
Lägga en kopia av värdet i B.
Shifta A 2 gg till vänster.
A = A + B
Shifta A 1 gg till vänster.

Klart. Fungerar (om man gör shiftningen rätt) på alla heltalsvärden från byte och uppåt.

Denna rutin kan spara tid ibland och om man genomför den konsekvent kan man spara en del minne och vinna hastighet.

Men jag har klurat på om det går att göra detta åt andra hållet, alltså dela med 10 vid att bara använda shift osv. Ja, jag känner till att subtrahera med 10 och räkna antal gångar det fungerar men jag kunde önska mig att det finns en deterministisk sätt att göra det på.

Tänker vi ett 32-bit värde i en 8-bit µC är det ganska tveksamt om subtrahera-10 metoden är någon tidvinst alls. Och då jag ju vet att det finns mycket expertis här frågar jag: någon som har lösningen?

[adent]

Hittade lite här: http://www.avrfreaks.net/index.php?name ... ew&t=37150

Känns dock som det borde finnas en del trick om man vet hur stora tal det gäller eller om det inte är
supernoga med exakt resultat...

Leker lite nu och: y = ((x/8)+(x/16)+x/128)/2 verkar ganska nära division med 10 Ska leka lite till.

[Icecap]

Har själv letat mer och jag hitta detta.

Avrfreak-grejen är ingen hjälp, den förutsätter att det finns en hardware multiplikator inbyggd, utan den är man i lika illa ställd.

[bearing]

Piclist's kodgenerator:
http://www.piclist.com/techref/piclist/ ... divmul.htm

Ger denna algoritm:

Kod: Markera allt

; Clear accumulator
; Add input / 16 to accumulator
; Add input / 32 to accumulator
; Add input / 256 to accumulator
; Add input / 512 to accumulator
; Move accumulator to result
;
; Approximated constant: 0.0996094, Error: 0.390625 %

...

; Code size: 92 instructions

[Andax]

Behöver du få ut både heltalsdelen och resten?

[bearing]

Piclist's kodgenerator

Såg att man kan öka precisionen:

Kod: Markera allt

; ACC = ACC * 0.1
; Temp = TEMP
; ACC size = 32 bits
; Error = 0.0001 %
; Bytes order = little endian
; Round = no

; ALGORITHM:
; Clear accumulator
; Add input / 16 to accumulator
; Add input / 32 to accumulator
; Add input / 256 to accumulator
; Add input / 512 to accumulator
; Add input / 4096 to accumulator
; Add input / 8192 to accumulator
; Add input / 65536 to accumulator
; Add input / 131072 to accumulator
; Add input / 1048576 to accumulator
; Add input / 2097152 to accumulator
; Move accumulator to result
;
; Approximated constant: 0.0999999, Error: 9.53674e-005 %

;     Input: ACC0 .. ACC3, 32 bits
;    Output: ACC0 .. ACC3, 29 bits
; Code size: 230 instructions

...

[JimmyAndersson]

Bara för att få det ur systemet:
När jag räknat "binärt" i huvudet så får jag detta att stämma:

A har värdet som ska delas med 10.
Lägga en kopia av värdet i B.

Shifta A 1 steg åt höger.
A = A - B
Shifta A 2 steg åt höger.
Invertera A.


Det förutsätter förstås att man bara är intresserad av heltalsdelen.

[Icecap]

JimmyAndersson: resultatet av en heltalsfunktion som du beskriver den blir vid A = 1000: 125. Inte riktigt en division med 10 alltså.

[bearing]

Jimmys förslag borde ge y = x / 8 - 1
Resultatet blir rätt ifall x = 40 =)

[pbgp]

I AVRfreaks länken fanns en länk hit:
http://homepage.cs.uiowa.edu/~jones/bcd/divide.html
(Låt inte URL:en lura dig, det har inte med BCD att göra).

Ganska lång läsning men jag tycker Douglas Jones är en ganska bra pedagog. Här beskriver han hur man gör både med och utan hardware multiply.

[JimmyAndersson]

Bearing:

Jag använde din förenkling (tack!) nu och testade att plotta ett diagram över en serie tal och felen som kom ut.
Det visade sig att felet (procentenheten) blir inverterat logaritmisk.
0% fel vid indata = 40. Efter 23000 så planar kurvan ut och ger aldrig mer än 25% fel.
Min variant ger alltså en inbyggd limiter på köpet.

Men jag trodde förstås inte att det skulle vara Metoden.

[adent]

... Avrfreak-grejen är ingen hjälp, den förutsätter att det finns en hardware multiplikator inbyggd, utan den är man i lika illa ställd.

Njae, multiplikation kan man ju åstakomma med shift och additioner. det blir väl en 4 shiftar och en addition plus additionerna av det hela, men inte SÅ farligt iaf.

Blev lite förtjust i metoden y = x*205 / 2048

Som kan bli:

y = (x << 7 + x << 6 + x << 3 + x << 2 + x) >> 11

MVH: Mikael

[bearing]

Det vore ju bra att veta vilken processor det gäller. På en del går det t.ex. snabbt att shifta och addera i samma svep. Vissa kan fördelaktigt använda swap-instruktionen för att shifta 4-steg. Sådana saker kan påverka vilken algoritm som är snabbast. Om processorn inte har multiplikator har den sannolikt inte heller barrell-shifter, vilket påverkar vilka shift-operationer som går snabbt.

Sen vore det också bra om vi fick veta inom vilket intervall indatan är, och hur hög precision som önskas. Vissa algoritmer kastar bort någon värdesiffra här och där, vilket inte gör något ifall indatan är stor. Men om indatan är t.ex. numret 10 kommer 1:an (resultatet) försvinna någonstans på vägen.

[Icecap]

adent: inte fel - förutom att det finns ett fel på 1 vid negativa värden.

[adent]

Negativa tal är konstiga saker som inte finns, så sånt ska man ändå inte hålla på med