Searching \ for '[PIC]: yet another challenge' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.piclist.com/techref/microchip/devices.htm?key=pic
Search entire site for: 'yet another challenge'.

Exact match. Not showing close matches.
PICList Thread
'[PIC]: yet another challenge'
2000\11\13@060652 by Andrzey.Baranski

flavicon
Andrzey Baranski@ESA
11/13/2000 12:07 PM

Here's an equation

         y = ( 1 + x ) / ( 1 - x )

where     0 < x < 1 i.e. Q0.16 format and y should be in Q6.10.

Does anybody know a trick to avoid a brute force 24 bits arithmetic ?

Looking forward to hearing from you.

Best Regards

Andrzej Baranski

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
"[PIC]:","[SX]:","[AVR]:" =uP ONLY! "[EE]:","[OT]:" =Other "[BUY]:","[AD]:" =Ads




2000\11\13@091511 by M. Adam Davis

flavicon
face
y = ( 1 + x ) / ( 1 - x )

simplifies to

y= 2 / (1-x) - 1
or
y= ( -2 / (x-1) ) - 1

Pick your poison.  In both cases you only have a variable on one side of
the division, rather than both sides.  You should be able to optimize a
simple 24 bit division routine based on that.

-Adam

spam_OUTAndrzey.BaranskiTakeThisOuTspamESA.INT wrote:
{Quote hidden}

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
"[PIC]:","[SX]:","[AVR]:" =uP ONLY! "[EE]:","[OT]:" =Other "[BUY]:","[AD]:" =Ads




2000\11\13@103251 by Scott Dattalo

face
flavicon
face
On Mon, 13 Nov 2000, M. Adam Davis wrote:

> y = ( 1 + x ) / ( 1 - x )
>
> simplifies to
>
> y= 2 / (1-x) - 1
> or
> y= ( -2 / (x-1) ) - 1

I think you meant:

 y  = 1 + 2x /(1-x)

Right?

If so, then the second term can be simplified by applying this formula:

 1 / (A + B) = 1/A * (1 - (B/A) + (B/A)^2 ...)

setting A = 1, and B = -x (recall 0 <x < 1)


y = 1 + 2x * ( 1 + x + x^2 + x^3 + ...)

If x is close to 1, then it'll take a while for this to converge. In fact, if
you look just at:

1/(1-x) = 1 + x + x^2 + ... + x^n + (x^(n+1))/(1-x))

and the error from taking just `n' terms is:

err = 2* (x^(n+2))/(1-x)

e.g. if x=0.1 and n=3

err = 2.2E-05  (y = 1.222)

if x=0.9 n=3

err = 11.8  (y = 19)

yuk!

if x=0.9 n=50

err = 0.0515



But there are some other tricks lurking...

Scott



{Quote hidden}

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
"[PIC]:","[SX]:","[AVR]:" =uP ONLY! "[EE]:","[OT]:" =Other "[BUY]:","[AD]:" =Ads




2000\11\13@125515 by Olin Lathrop

flavicon
face
> > y = ( 1 + x ) / ( 1 - x )
> >
> > simplifies to
> >
> > y= 2 / (1-x) - 1
> > or
> > y= ( -2 / (x-1) ) - 1
>
> I think you meant:
>
>   y  = 1 + 2x /(1-x)

A math teacher I once had would say you are both 80% right.  100% for being
correct, but -20% for not showing how you got it, thereby providing no
confidence to anyone else that the answer is in fact correct.

Consider rearranging the numerator:

1 + X  =  -(-1 - X)  =  -(-2 + 1 - X)  =  2 - (1 - X)

Dividing this by (1 - X) yields:

2 - (1 - X)       2
-----------  =  ----- - 1
  1 - X        1 - X

Now for the second form, rearrange the whole equation:

1 + X     (1 - X) + 2X          2X
-----  =  ------------  =  1 + -----
1 - X         1 - X            1 - X


*****************************************************************
Olin Lathrop, embedded systems consultant in Devens Massachusetts
(978) 772-3129, olinspamKILLspamcognivis.com, http://www.cognivis.com

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
"[PIC]:","[SX]:","[AVR]:" =uP ONLY! "[EE]:","[OT]:" =Other "[BUY]:","[AD]:" =Ads




2000\11\13@130345 by M. Adam Davis

flavicon
face
Scott Dattalo wrote:
>
> On Mon, 13 Nov 2000, M. Adam Davis wrote:
>
> > y = ( 1 + x ) / ( 1 - x )
> >
> > simplifies to
> >
> > y= 2 / (1-x) - 1
> > or
> > y= ( -2 / (x-1) ) - 1
>
> I think you meant:
>
>   y  = 1 + 2x /(1-x)
>
> Right?

Well, no:

y = ( 1 + x ) / ( 1 - x )
Seperate the numerator into two fractions:
y = 1/(1-x) + x/(1-x)
Expand using partial fractions:
y = 1/(1-x) + 1/(1-x) - 1
Simplified:
y = 2/(1-x) - 1

This can be simplifed further, knowing that 0 < x < 1, and shouldn't be
too difficult to calculate more quickly than a full 24-bit division
routine.

-Adam

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
"[PIC]:","[SX]:","[AVR]:" =uP ONLY! "[EE]:","[OT]:" =Other "[BUY]:","[AD]:" =Ads




2000\11\13@131847 by Andrew Kunz

flavicon
face
Olin,

What did you base your rearrangement of the numerator on?  I don't see a comment
explaining it.  Does this rearrangement follow some mathematical principle such
as commutation, or is it just something fanciful?  How come you did two steps at
once?

Andy








Olin Lathrop <.....olin_piclistKILLspamspam.....COGNIVIS.COM> on 11/13/2000 12:55:04 PM

Please respond to pic microcontroller discussion list <EraseMEPICLISTspam_OUTspamTakeThisOuTMITVMA.MIT.EDU>








To:      PICLISTspamspam_OUTMITVMA.MIT.EDU

cc:      (bcc: Andrew Kunz/TDI_NOTES)



Subject: Re: [PIC]: yet another challenge








{Quote hidden}

A math teacher I once had would say you are both 80% right.  100% for being
correct, but -20% for not showing how you got it, thereby providing no
confidence to anyone else that the answer is in fact correct.

Consider rearranging the numerator:

1 + X  =  -(-1 - X)  =  -(-2 + 1 - X)  =  2 - (1 - X)

Dividing this by (1 - X) yields:

2 - (1 - X)       2
-----------  =  ----- - 1
  1 - X        1 - X

Now for the second form, rearrange the whole equation:

1 + X     (1 - X) + 2X          2X
-----  =  ------------  =  1 + -----
1 - X         1 - X            1 - X


*****************************************************************
Olin Lathrop, embedded systems consultant in Devens Massachusetts
(978) 772-3129, @spam@olinKILLspamspamcognivis.com, http://www.cognivis.com

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
"[PIC]:","[SX]:","[AVR]:" =uP ONLY! "[EE]:","[OT]:" =Other "[BUY]:","[AD]:" =Ads

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
"[PIC]:","[SX]:","[AVR]:" =uP ONLY! "[EE]:","[OT]:" =Other "[BUY]:","[AD]:" =Ads




2000\11\13@131853 by Andrew Kunz

flavicon
face
Ah, now THAT is easier to follow..

Andy








"M. Adam Davis" <KILLspamadavisKILLspamspamUBASICS.COM> on 11/13/2000 01:03:14 PM

Please respond to pic microcontroller discussion list <RemoveMEPICLISTTakeThisOuTspamMITVMA.MIT.EDU>








To:      spamBeGonePICLISTspamBeGonespamMITVMA.MIT.EDU

cc:      (bcc: Andrew Kunz/TDI_NOTES)



Subject: Re: [PIC]: yet another challenge








Scott Dattalo wrote:
{Quote hidden}

Well, no:

y = ( 1 + x ) / ( 1 - x )
Seperate the numerator into two fractions:
y = 1/(1-x) + x/(1-x)
Expand using partial fractions:
y = 1/(1-x) + 1/(1-x) - 1
Simplified:
y = 2/(1-x) - 1

This can be simplifed further, knowing that 0 < x < 1, and shouldn't be
too difficult to calculate more quickly than a full 24-bit division
routine.

-Adam

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
"[PIC]:","[SX]:","[AVR]:" =uP ONLY! "[EE]:","[OT]:" =Other "[BUY]:","[AD]:" =Ads

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
"[PIC]:","[SX]:","[AVR]:" =uP ONLY! "[EE]:","[OT]:" =Other "[BUY]:","[AD]:" =Ads




2000\11\13@162105 by Olin Lathrop

flavicon
face
> > Consider rearranging the numerator:
> >
> > 1 + X  =  -(-1 - X)  =  -(-2 + 1 - X)  =  2 - (1 - X)
> >
> > Dividing this by (1 - X) yields:
> >
> > 2 - (1 - X)       2
> > -----------  =  ----- - 1
> >    1 - X        1 - X
> > Now for the second form, rearrange the whole equation:
> >
> > 1 + X     (1 - X) + 2X          2X
> > -----  =  ------------  =  1 + -----
> > 1 - X         1 - X            1 - X
>
> What did you base your rearrangement of the numerator on?  I don't see a
comment
> explaining it.  Does this rearrangement follow some mathematical principle
such
> as commutation, or is it just something fanciful?  How come you did two
steps at
> once?

I thought I had already taken sufficiently small steps to make it obvious,
in fact probably tedious to some.  The first step negates each of the terms,
then negates the whole thing for no net change.  The second step breaks
up -1 into -2 and +1.  The third step negates each the two terms
individually to get rid of the outer negative.  I prefer to leave "fanciful"
math to marketing types and politicians ;-)


*****************************************************************
Olin Lathrop, embedded systems consultant in Devens Massachusetts
(978) 772-3129, TakeThisOuTolinEraseMEspamspam_OUTcognivis.com, http://www.cognivis.com

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
"[PIC]:","[SX]:","[AVR]:" =uP ONLY! "[EE]:","[OT]:" =Other "[BUY]:","[AD]:" =Ads




2000\11\14@115347 by Nikolai Golovchenko

flavicon
face
The best way is to write a special division-like routine.
BTW, we had quite a few division routines lately on PicList! :)

Hint #1: since (1-x) < 1 when x!=0, than (1-x) will fit in
two bytes and the 24 bit subtraction/addition in the
division routine loop can be replaced by 16 bit
subtraction/addition. Well, divisor is 16 bit, but the
remainder is a bit longer...

Hint #2: you can use x directly in the division routine
instead of (1-x). For example, subtraction of (1-x) is equal
to addition of (x-1). Actually you add x and subtract 1...

That should take approximately 361 cycles/50 instructions/6
temporary bytes. :)

Nikolai

---- Original Message ----
From: RemoveMEAndrzey.BaranskispamTakeThisOuTESA.INT <Andrzey.BaranskiEraseMEspam.....ESA.INT>
Sent: Monday, November 13, 2000 13:07:38
 To: EraseMEPICLISTspamMITVMA.MIT.EDU
Subj: [PIC]: yet another challenge

{Quote hidden}

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics


2000\11\14@120440 by Scott Dattalo

face
flavicon
face
On Tue, 14 Nov 2000, Nikolai Golovchenko wrote:

> The best way is to write a special division-like routine.
> BTW, we had quite a few division routines lately on PicList! :)
>
> Hint #1: since (1-x) < 1 when x!=0, than (1-x) will fit in
> two bytes and the 24 bit subtraction/addition in the
> division routine loop can be replaced by 16 bit
> subtraction/addition. Well, divisor is 16 bit, but the
> remainder is a bit longer...
>
> Hint #2: you can use x directly in the division routine
> instead of (1-x). For example, subtraction of (1-x) is equal
> to addition of (x-1). Actually you add x and subtract 1...
>
> That should take approximately 361 cycles/50 instructions/6
> temporary bytes. :)

Good (constructive) suggestion Nikolai. Another observation about this function
is

f(x) = (1+x)/(1-x)

f(x) = 1/f(-x)

So the discontinuity as x->1 can be changed into a continuity by letting z=-x,
compute f(z) and finally take the reciprocal. Obviously, doing all steps with
24-bit arithmetic would be expensive. However, using your observations and
suggestions, you could compute the intermediate results using 16-bit arithmetic
and possibly get just as accurate of an answer. In fact, the function is very
smooth between 0 < x < 0.5, so a first order interpolation may be sufficient for
computing it.

But 24-bits, why?

Scott

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics


2000\11\15@140154 by Nikolai Golovchenko

flavicon
face
Well, no more ideas, so I'll just post the code. By the way,
Andrej, what that function might be used for?

Another observation about it:

Given y = (1+x)/(1-x)

we can find x,

x = (y-1)/(y+1)


Regards,
Nikolai


       cblock
       Counter
       x0, x1
       Temp0, Temp1
       Temp2, Temp3
       Temp4
       endc


mov     macro x, y
       movlw x
       movwf y
       endm

;0x0000 -> 0x0400
       mov 0x00, x0
       mov 0x00, x1
       call stuff
       nop
;0x8000 -> 0x0C00
       mov 0x00, x0
       mov 0x80, x1
       call stuff
       nop
;0x0001 -> 0x0400
       mov 0x01, x0
       mov 0x00, x1
       call stuff
       nop
;0x0002 -> 0x0400
       mov 0x02, x0
       mov 0x00, x1
       call stuff
       nop
;0x0020 -> 0x0401
       mov 0x20, x0
       mov 0x00, x1
       call stuff
       nop
;0xffff -> 0xffff
       mov 0xff, x0
       mov 0xff, x1
       call stuff
       nop
;0x5a5a -> 0x085d
       mov 0x5a, x0
       mov 0x5a, x1
       call stuff
       nop
;0xa987 -> 0x0d04
       mov 0xa9, x0
       mov 0x87, x1
       call stuff
       nop
;0xf820 -> 0xffff
       mov 0x20, x0
       mov 0xf8, x1
       call stuff
       nop
;0xf7ff -> 0xfbe0
       mov 0xff, x0
       mov 0xf7, x1
       call stuff
       nop

;      1+x
;  x = ---
;      1-x
;
; Input:
;   x1:0 - unsigned fixed point Q0.16
; Output:
;   x1:0 - unsigned fixed point Q6.10
; Temporary (6 bytes):
;   Temp4:0 - reminder and current result
;   Counter - loop counter
;
; Size: 50 instructions
; Timing: 2+8+10+16*21-1+4+2 = 361 cycles

stuff
       ;load Temp with (1+x) * 256 * 4
       movf x0, w
       movwf Temp1
       movf x1, w
       movwf Temp2
       movlw 1
       movwf Temp3     ;add 1 to get (1+x) as divisor
       movwf Temp0     ;initilize lower bit to 1
                       ;to perform subtraction at
                       ;first iteration
       clrf Temp4
                       ;shift left by 2 bits
       clrc
       rlf Temp1, f
       rlf Temp2, f
       rlf Temp3, f
       rlf Temp1, f
       rlf Temp2, f
       rlf Temp3, f

       movlw 16        ;initialize loop counter
       movwf Counter

       rlf Temp1, f    ;shift remainder
stuff_loop
       rlf Temp2, f
       rlf Temp3, f
       rlf Temp4, f

       movf x0, w      ;get LSB of x to w
       btfss Temp0, 0
        goto stuff_add

       ;subtraction of (1-x)
       ;-(1-x)=+(x-1)
       addwf Temp2, f
       movf x1, w
       skpnc
        incfsz x1, w
         addwf Temp3, f
       movlw 1
       skpc
        subwf Temp4, f
       goto stuff_next

stuff_add
       ;addition of (1-x)
       ;+(1-x)=-(x-1)
       subwf Temp2, f
       movf x1, w
       skpc
        incfsz x1, w
         subwf Temp3, f
       movlw 1
       skpnc
        addwf Temp4, f

stuff_next
       rlf Temp0, f    ;shift in next result bit
       rlf Temp1, f    ;and shift out next bit of dividend
       decfsz Counter, f
        goto stuff_loop

       ;move result to x1:0
       movf Temp0, w
       movwf x0
       movf Temp1, w
       movwf x1
       return

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.


More... (looser matching)
- Last day of these posts
- In 2000 , 2001 only
- Today
- New search...