Searching \ for '[PIC]: yet another challenge' in subject line. ()
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.
'[PIC]: yet another challenge'
2000\11\13@060652 by

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

--

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.

Andrzey.BaranskiESA.INT wrote:
{Quote hidden}

--

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}

--

> > 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, olincognivis.com, http://www.cognivis.com

--

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.

--

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_piclistCOGNIVIS.COM> on 11/13/2000 12:55:04 PM

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

To:      PICLISTMITVMA.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, olincognivis.com, http://www.cognivis.com

--

--

Ah, now THAT is easier to follow..

Andy

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

To:      PICLISTMITVMA.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.

--

--

> > 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, olincognivis.com, http://www.cognivis.com

--

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

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

Nikolai

---- Original Message ----
From: Andrzey.BaranskiESA.INT <Andrzey.BaranskiESA.INT>
Sent: Monday, November 13, 2000 13:07:38
To: PICLISTMITVMA.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

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. :)

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

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

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

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

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

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...