---

Hvordan regner jeg en logaritme ud på en microcontroller? Det skal bare være
heltal. Jeg tænker på en metode i stil med division, hvor man shifter til
venstre, og sammenligner med en remainder.

Man kan groft sige at log(tal) = den første bit der er sat i tallet, fra
venstre. F.eks. log(0b00100000)=5, da bit 5 er den første der er sat. Og
log(0b00001000)=3 osv. Men hvad gør jeg med resten af bitsene når de er sat,
hvordan bruger jeg dem til at forøge præcissionen? Resultatet må gerne
ganges op med en konstant, så det stadig bliver et heltal.

Kan huske jeg lavede det på en Motorola 68000 i Amiga-tiden, og har faktisk
disketten endnu, men kan ikke læse den, argh... :-/ (nogen i Århus der har
en gammel Amiga 500 jeg må arve?

--
Ulrik Smed
Denmark, Aarhus

---

"Ulrik Smed" <ulsm@post1.tele.dk> skrev i en meddelelse news:40f55a3e$0$140$edfadb0f@dread11.news.tele.dk...
> Hvordan regner jeg en logaritme ud på en microcontroller? Det skal bare være
> heltal. Jeg tænker på en metode i stil med division, hvor man shifter til
> venstre, og sammenligner med en remainder.
>
Man kunne måske bygge en algoritme på temaet a^m - 2^n ~ 0
hvor a er tallet du skal finde 2-talslogaritmen til.
Når differensen er passende lille stopper du søgningen efter
m og n.

Mvh
Martin

---

"Ulrik Smed" <ulsm@post1.tele.dk> skrev i en meddelelse news:40f55a3e$0$140$edfadb0f@dread11.news.tele.dk...
> Hvordan regner jeg en logaritme ud på en microcontroller? Det skal bare være
> heltal. Jeg tænker på en metode i stil med division, hvor man shifter til
> venstre, og sammenligner med en remainder.
>
Her er så noget kode som skulle være nem at oversætte
til den ønskede præcision

'eksempel for log2(a)
a = 1.25
FOR i = 1 TO 10
n = 0
WHILE a < 2
a = a * a: n = n + 1
WEND
PRINT n 'her skal være n-1 0'er efterfulgt af 1
a = a / 2
NEXT

Mvh
Martin

---

Martin Larsen wrote:

> Her er så noget kode som skulle være nem at oversætte
> til den ønskede præcision
>
> 'eksempel for log2(a)
> a = 1.25
> FOR i = 1 TO 10
> n = 0
> WHILE a < 2
> a = a * a: n = n + 1
> WEND
> PRINT n 'her skal være n-1 0'er efterfulgt af 1
> a = a / 2
> NEXT
>
> Mvh
> Martin

Hm, det giver sekvensen:
2
2
3
3
1
2
3
1
1
1

Jeg forstår ikke lige hvordan det skal virke, hvor får jeg resultatet ud
henne?

Jeg har lavet det her forsøg, som giver en dårlig, hakket tilnærmelse til en
logaritme. :-/

FUNCTION logaritme (n)
nl = n
res = 0
add = 16
appr = 1
div = 1
logloop:
IF appr > n THEN
div = div * 2
appr = appr - appr / div
add = add / 2
ELSE
res = res + add
appr = appr + appr / div
END IF
IF add > .5 THEN GOTO logloop
logaritme = res
END FUNCTION

--
Ulrik Smed
Denmark, Aarhus

---

"Ulrik Smed" <ulsm@post1.tele.dk> skrev i en meddelelse news:40f59d73$0$188$edfadb0f@dread11.news.tele.dk...
> Martin Larsen wrote:

> > PRINT n 'her skal være n-1 0'er efterfulgt af 1

> Hm, det giver sekvensen:
> 2
> 2
> 3
> 3
> 1
> 2
> 3
> 1
> 1
> 1
>
> Jeg forstår ikke lige hvordan det skal virke, hvor får jeg resultatet ud
> henne?

Du skal prøve at læse hvad der står!
Jeg går ud fra at du selv kan supplere med den kode der afleverer
det binære tal.

2,2,3,3,1 etc bliver til
01010010011

Foran skal du forestille dig et decimalpunktum. Og det fremgår så også
at du skal fjerne den principale del af tallets logaritme først. Eg: log2(5)
bliver til 2 + log2(5/2²) eller 2 + log2(1.25) og den sidste logaritme får
du med den vidunderlige kode fra mig.

Mvh
Martin

---

Hej Ulrik,

Jeg er lidt forvirret over dit spørgsmål - du skriver "bare heltal" og
efterfølgende "hvad gør jeg med resten af bitsne når de er sat" hvilket må
betyde at du godt vil ha' decimaldelen med!

Her en måde af beregne logaritmen til et tal på hvis din ordlængde ikke er
for lang:

-Heltalsdelen til din logaritmefunktion skulle være ligetil at finde -
undersøg hvor mange skift til højre du kan lave til din værdi bliver "nul"!

-Dernæst kan du generere en tabel til din "fraktionelle bits"(dem til højre
for dit punktum)! Det er hurtigt, men koster lidt memory!

Cheers
Thomas Stoltz

"Martin Larsen" <mlarsen@post7.tele.dk> wrote in message
news:40f5a52c$0$23870$14726298@news.sunsite.dk...
> "Ulrik Smed" <ulsm@post1.tele.dk> skrev i en meddelelse
news:40f59d73$0$188$edfadb0f@dread11.news.tele.dk...
> > Martin Larsen wrote:
>
> > > PRINT n 'her skal være n-1 0'er efterfulgt af 1
>
> > Hm, det giver sekvensen:
> > 2
> > 2
> > 3
> > 3
> > 1
> > 2
> > 3
> > 1
> > 1
> > 1
> >
> > Jeg forstår ikke lige hvordan det skal virke, hvor får jeg resultatet ud
> > henne?
>
> Du skal prøve at læse hvad der står!
> Jeg går ud fra at du selv kan supplere med den kode der afleverer
> det binære tal.
>
> 2,2,3,3,1 etc bliver til
> 01010010011
>
> Foran skal du forestille dig et decimalpunktum. Og det fremgår så også
> at du skal fjerne den principale del af tallets logaritme først. Eg:
log2(5)
> bliver til 2 + log2(5/2²) eller 2 + log2(1.25) og den sidste logaritme får
> du med den vidunderlige kode fra mig.
>
> Mvh
> Martin
>
>

---

bemærkning!

min version bygger på log2!

men du kan skifte basen til 10 ved at gange med faktoren log10(x)/log2(x)
(hvor x er et tal større end 1) - hvis jeg husker rigtig....

Thomas

"JohnDoe" <stoltzo@hotmail.com> wrote in message
news:cd68oj$1ihh$1@news.cybercity.dk...
> Hej Ulrik,
>
> Jeg er lidt forvirret over dit spørgsmål - du skriver "bare heltal" og
> efterfølgende "hvad gør jeg med resten af bitsne når de er sat" hvilket må
> betyde at du godt vil ha' decimaldelen med!
>
> Her en måde af beregne logaritmen til et tal på hvis din ordlængde ikke er
> for lang:
>
> -Heltalsdelen til din logaritmefunktion skulle være ligetil at finde -
> undersøg hvor mange skift til højre du kan lave til din værdi bliver
"nul"!
>
> -Dernæst kan du generere en tabel til din "fraktionelle bits"(dem til
højre
> for dit punktum)! Det er hurtigt, men koster lidt memory!
>
> Cheers
> Thomas Stoltz
>
> "Martin Larsen" <mlarsen@post7.tele.dk> wrote in message
> news:40f5a52c$0$23870$14726298@news.sunsite.dk...
> > "Ulrik Smed" <ulsm@post1.tele.dk> skrev i en meddelelse
> news:40f59d73$0$188$edfadb0f@dread11.news.tele.dk...
> > > Martin Larsen wrote:
> >
> > > > PRINT n 'her skal være n-1 0'er efterfulgt af 1
> >
> > > Hm, det giver sekvensen:
> > > 2
> > > 2
> > > 3
> > > 3
> > > 1
> > > 2
> > > 3
> > > 1
> > > 1
> > > 1
> > >
> > > Jeg forstår ikke lige hvordan det skal virke, hvor får jeg resultatet
ud
> > > henne?
> >
> > Du skal prøve at læse hvad der står!
> > Jeg går ud fra at du selv kan supplere med den kode der afleverer
> > det binære tal.
> >
> > 2,2,3,3,1 etc bliver til
> > 01010010011
> >
> > Foran skal du forestille dig et decimalpunktum. Og det fremgår så også
> > at du skal fjerne den principale del af tallets logaritme først. Eg:
> log2(5)
> > bliver til 2 + log2(5/2²) eller 2 + log2(1.25) og den sidste logaritme
får
> > du med den vidunderlige kode fra mig.
> >
> > Mvh
> > Martin
> >
> >
>
>

---

JohnDoe wrote:
>
> min version bygger på log2!
>
> men du kan skifte basen til 10 ved at gange med faktoren log10(x)/log2(x)
> (hvor x er et tal større end 1) - hvis jeg husker rigtig....

Det der gælder, er

log10(x) = log2(x)/log2(10)

Derfor er faktoren 1/log2(10) som også er det samme som log10(2) .

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

JohnDoe wrote:
> Hej Ulrik,
>
> Jeg er lidt forvirret over dit spørgsmål - du skriver "bare
> heltal" og efterfølgende "hvad gør jeg med resten af bitsne
> når de er sat" hvilket må betyde at du godt vil ha'
> decimaldelen med!

Ja, det vil jeg også, men det var derfor jeg skrev at resultatet gerne måtte
ganges op med en konstant, så det forblev et heltal. Mit input er 1 til
1024, og jeg vil godt ha' lidt bedre præcission end 0-9 som resultat. Så
hvis man nu lavede en byte med decimalerne og satte bagefter, og betragtede
det hele som et 12-bits heltal, så bliver det brugbart.

> Her en måde af beregne logaritmen til et tal på hvis din
> ordlængde ikke er for lang:
>
> -Heltalsdelen til din logaritmefunktion skulle være ligetil at
> finde - undersøg hvor mange skift til højre du kan lave til
> din værdi bliver "nul"!

Jeps, det samme som at finde den første bit fra venstre der er sat.

> -Dernæst kan du generere en tabel til din "fraktionelle
> bits"(dem til højre for dit punktum)! Det er hurtigt, men
> koster lidt memory!

Jahh, det er jo lidt 'ufint'. Jeg tror Martins metode er rigelig
hurtig, så den vil jeg lige arbejde lidt videre med.

--
Ulrik Smed
Denmark, Aarhus

---

Ulrik Smed skrev

> Mit input er 1 til
> 1024, og jeg vil godt ha' lidt bedre præcission end 0-9 som resultat.

Jeg har ikke helt fulgt med i jeres diskussion, men ovenstående lyder
umiddelbart som noget der kan klares med en opslagstabel.


Mvh,
--
Filip Larsen

---

Martin Larsen wrote:

> Foran skal du forestille dig et decimalpunktum. Og det fremgår
> så også
> at du skal fjerne den principale del af tallets logaritme
> først. Eg: log2(5)
> bliver til 2 + log2(5/2²) eller 2 + log2(1.25) og den sidste
> logaritme får
> du med den vidunderlige kode fra mig.

OK, nu fes den vist ind på den lettere defokuserede lystavle! Det
virker jo fremragende, præcis hvad jeg skulle bruge til finde decimalerne.
Det må jeg lige ha' skrevet om til Atmel assembler. Takker mange
gange!

--
Ulrik Smed
Denmark, Aarhus

---

"Ulrik Smed" <ulsm@post1.tele.dk> skrev i en meddelelse news:40f6b2d2$0$311$edfadb0f@dread11.news.tele.dk...

> Det må jeg lige ha' skrevet om til Atmel assembler. Takker mange
> gange!
>
Det kan vil nok kræve lidt omtanke at lave float multiplikation
om til integer, men skulle nok kunne lade sig gøre.

Mvh
Martin

---

Martin Larsen wrote:

> Det kan vil nok kræve lidt omtanke at lave float multiplikation
> om til integer, men skulle nok kunne lade sig gøre.

Jeps, jeg har netop lavet denne her, som kører med fast looplængde på 8, og
bruger integers:

a = input
res = 0
FOR i = 1 TO 8
a = a * a / 128
res = res * 2
IF a > 256 THEN
res = res + 1
a = a / 2
END IF
NEXT i

Den er noget simplere, man skal ikke til at lave bitmønsteret ud fra
1,3,2,2,3... sekvensen bagefter. Præcissionen er ikke helt perfekt, men
absolut brugbar. Inputtet er fra 128 til 255, svarende til fra 1 til
"næsten-2". Den crasher heller ikke hvis man giver den 1 (128) eller 2 (256)
som input.

--
Ulrik Smed
Denmark, Aarhus

---

"Ulrik Smed" <ulsm@post1.tele.dk> skrev i en meddelelse news:40f70081$0$311$edfadb0f@dread16.news.tele.dk...

> "næsten-2". Den crasher heller ikke hvis man giver den 1 (128) eller 2 (256)
> som input.

Disse input burde vel være sorteret fra på forhånd i en
optimal implementation

Mvh
Martin

---

Martin Larsen wrote:

> Disse input burde vel være sorteret fra på forhånd i en
> optimal implementation

Tjah, 2 forekommer jo ikke, men det er da meget rart man kan smide 1 efter
den, og den så returnere 0.

Her er så lige en 8 bit assembler version til Atmel:

log2:
ldi r17,0 ; counter, integer result
log2loop1:
cpi r16,0
breq log2l1 ; exit loop if 0
lsr r16
ror r1
inc r17 ; inc result
rjmp log2loop1
log2l1:
ldi r18,8 ; loop
log2loop2:
mul r1,r1
lsl r0
rol r1
rol r16
sec
sbrc r16,0
ror r1
dec r18
brne log2loop2
; r16=fractional result
ret

Første loop finder heltalsdelen, samtidig med den forbereder r1 til andet
loop.
Andet loop finder decimalerne med "i anden"-metoden.
Input er r16
Output er r17:r16
--
Ulrik Smed
Denmark, Aarhus

---

Ulrik Smed wrote:
> log2loop1:
> cpi r16,0
> breq log2l1 ; exit loop if 0
> lsr r16
> ror r1
> inc r17 ; inc result
> rjmp log2loop1

Woops, bummer! Det første loop her skal lige have flyttet "lsr r16" og "ror
r1" op ovenover compare'en i starten. Sådan her:

log2loop1:
lsr r16
ror r1
cpi r16,0
breq log2l1 ; exit loop if 0
inc r17 ; inc result
rjmp log2loop1

Ellers bliver heltallet 1 for stort, det kan vi jo ikke ha'!

--
Ulrik Smed
Denmark, Aarhus