40 bit Wurzel AVR ASM

[Sebi (Gast)]

Der Betreff sagt es ja schon. Hat jemand eine fertige Routine?

[Markus W. (Firma: guloshop.de) (m-w)]

Sebi schrieb:
> Der Betreff sagt es ja schon.

Schön wärs. ;-)

Für welchen Mikrocontroller genau?

Was meinst du mit 40 Bit? Ist das die Genauigkeit der Zahl?

In welchem Format hast du den Radikand und in welchem Format brauchst du 
das Ergebnis?

[Sebi (Gast)]

Hallo Markus,
entschuldige, dass ich die Informationen vergessen habe.
Also:
-ATMEGA88PA
Format Radikand: 40bit Integer
Format Ergebniss: 20bit Integer, gerundet (ob auf oder ab ist ja egal)y

Ich hab mir schon die 32bit Wurzel Funktion hier im Wiki angeschaut. 
Allerdings weiß ich nicht, wie ich die "erweitern" kann.

[Johann L. (gjlayde)]

Sebi schrieb:

> Ich hab mir schon die 32bit Wurzel Funktion hier im Wiki angeschaut.
> Allerdings weiß ich nicht, wie ich die "erweitern" kann.

Anstatt 4-Byte Eingabe wird's eine 5-Byte Eingabe.
Anstatt 2-Byte Ausgabe wird's eine 3-Byte Ausgabe.

In einem ersten Schritt kannst du die hartcodierten Register zum 
bwesseren Überblick ersezten:
 

ldi   R19, 0xc0
clr   R18          ; rotation mask in R19:R18
ldi   R27, 0x40
sub   R26, R26     ; developing sqrt in R27:R26, C=0

wird dann zu
 

#define RES 26
#define MASK 18
#define BITS 40

; rotation mask in MASK
ldi   MASK+1, 3 << ((BITS-2) % 8)
clr   MASK

; expand sqrt in RES, C=0
ldi   RES+1, 1 << ((BITS/2-2) % 8)
sub   RES,   RES

...

#undef BITS
#undef MASK
#undef RES

In einem 2. Schritt erweiterst du dann die Arbeitsregister zur jeweils 
benötigten Bitbreite:

; rotation mask in MASK
ldi   MASK+2, 3 << ((BITS-2) % 8)
clr   MASK+1
clr   MASK

Die Shifts oben musst noch nachrechnen (Hausaufgabe).

hmmm. oder erweitern auf 6 Byte Radikant, die Routine setzt wohl voraus, 
daß der Radikant eine gerade Anzahl Bytes groß ist, d.h. das Erhebnis 
nicht 2.5 Bytes groß ist.

[Sebi (Gast)]

Ich werde mich mal an der 48bit Variante versuchen und die dann hier 
posten.

[Wolfgang (Gast)]

Zur Erweiterung auf 40 bit sollte auch die Näherung

 sqrt(1+x) = 1 + x/2 + eps

gut sein.

[Sebi (Gast)]

Verlfucht, ich krieg es nicht hin.
Andere Baustelle: Heron Verfahren.
Wie krieg ich das ohne die Division Xn/a hin? Division durch zwei ist ja 
kein Ding (shift) aber die andere Division bereit mir Kopfzerbrechen.

[Johann L. (gjlayde)]

Wolfgang schrieb:
> Zur Erweiterung auf 40 bit sollte auch die Näherung
>

 sqrt(1+x) = 1 + x/2 + eps

> gut sein.

Aber nur für |x| << 1

[Sebi (Gast)]

;  R18:R17:R16=SQRT(R6:R5:R4:R3:R2:R1)
SQRT48:
    ldi r21,0xc0 
    clr r20
    clr r19
    ldi   R18,0x40
        clr r17
    sub r16,r16
_sq48_1:    brcs  _sq48_2
    cp r4,r16
    cpc r5,r17
    cpc r6,r28
    brcs  _sq48_3
_sq48_2:    sub   R4,R16
    sbc r5,r17
    sbc r6,r18
    or r16,r19
    or r17,r20
    or r18,r21
_sq48_3:    lsr   R21
    ror r20
    ror r19
    eor r18,r21
    eor r17,r20
    eor r16,r19
    rol r1
    rol r2
    rol r3
    rol r4
    rol r5
    rol r6
    sbrs r1,0
    rjmp  _sq48_1 

    brcs  _sq48_4
    lsl   R3
    cpc   R16,R4
    cpc   r17,r5
    cpc    r18,r6
_sq48_4:    adc   R16,r21
ret

das ist der klägliche Versuch.

[Horst H. (horha)]

Hallo,

als ich
 sqrt(1+x) = 1 + x/2 + eps  heute gesehen habe, fiel mir spotan soetwas 
ein:
Falls die Zahl kleiner 32 -Bit ist einfach 32 Bit Rechnung.-> trivial.
Falls die Zahl >=2^32 ist dann die Zahl aufspalten
N = K*256 + C mit K = oberen 32 Bits und C = N mod 255 also die unter 8 
Bit

Wurzel(N)=Wurzel(K*256 + C)
erweitert mit 1=Wurzel(K*256)/Wurzel(K*256)
=Wurzel(K*256)*Wurzel( (K*256)/(K*256) + C/(K*256))

= Wurzel(K*256)*Wurzel( 1+ C/(K*256))
x = c/(256*K) | irgenwas kleiner 2^-24 < 1e-7
= 16*Wurzel(K) + (16*Wurzel(K)* C/(256*K)/2
= 16*Wurzel(K) // + C/(16*Wurzel(K))/2 < 1/512 )
Dummerweise ist Wurzel(K) nur eine 16 Bit Integerzahl. :-(
Wenn man eine Wurzelfunktion hätte, die 32 Bit integer ins 16.8 Format 
umrechnen würde, hätte man ein Chance.