Searching \ for '[PIC]: Divide by 15 was [PIC]: Challenge! (Everyon' 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/math/index.htm?key=divide
Search entire site for: 'Divide by 15 was [PIC]: Challenge! (Everyon'.

Exact match. Not showing close matches.
PICList Thread
'[PIC]: Divide by 15 was [PIC]: Challenge! (Everyon'
2000\12\22@120413 by jamesnewton

face picon face
Thanks Scott (and Andy). I thought that looked like the old xor swap trick,
but somehow I just couldn't wrap my mind around WHY it was being used. With
your comments it begins to make sense. Now if I could just figure out how
you guys dream up these things... <GRIN> Wow. Divide 16 bits by a constant
(15) in *11* cycles.

Nik, here is a perfect example of a need for a database for the multiply (or
divide) by a constant code generator. You can look at the incoming
parameters, search a table and say "The following machine generated code
will produce the correct result in x cycles, but there is hand optimized
code (also listed below) that appears to meet your needs which is only y
cycles.

Scott, this is a good example of the need for an open source C compiler that
also checks a library of routines to find the best possible code for the
parameters (if they are known). Over time, an awesome library of optimized
code will pile up.

I would work with any author of an open source compiler to integrate the
code library at
www.piclist.com/techref/microchip/routines
with the language in such a way that as routines are added to the site, they
automatically become available to the language.

This one is at
http://www.piclist.com/techref/microchip/math/div/16byconst15-dk.htm

---
James Newton (PICList Admin #3)
spam_OUTjamesnewtonTakeThisOuTspampiclist.com 1-619-652-0593
PIC/PICList FAQ: http://www.piclist.com or .org

{Original Message removed}

2000\12\22@125634 by Scott Dattalo

face
flavicon
face
On Fri, 22 Dec 2000, James Newton wrote:

> Thanks Scott (and Andy). I thought that looked like the old xor swap trick,
> but somehow I just couldn't wrap my mind around WHY it was being used. With
> your comments it begins to make sense. Now if I could just figure out how
> you guys dream up these things... <GRIN> Wow. Divide 16 bits by a constant
> (15) in *11* cycles.
>
> Nik, here is a perfect example of a need for a database for the multiply (or
> divide) by a constant code generator. You can look at the incoming
> parameters, search a table and say "The following machine generated code
> will produce the correct result in x cycles, but there is hand optimized
> code (also listed below) that appears to meet your needs which is only y
> cycles.

BTW, you should be aware that Nik's generator is more accurate than what Dmitry
and I generated. The algorithm is based on this formula:

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

Dmitry and I computed the first two terms, Nik does all three in the generator.

The error is on the order of 1/16/16/16 = 2E-4

For example:

suppose you wanted to divide 65535 by 15. The exact answer is 4369. However,
using Dmitry's code you'd get: 4350. Nik's produces: 4365 (I think).

But a slight mod will improve Dmitry's

{Quote hidden}

       movf  high,w
       addwf low,f
       skpnc
        incf high,f

This modification will yield the result: 4366

>
> Scott, this is a good example of the need for an open source C compiler that
> also checks a library of routines to find the best possible code for the
> parameters (if they are known). Over time, an awesome library of optimized
> code will pile up.

True. At some point Nik will integrate his code generator into SDCC.

Scott

--
http://www.piclist.com hint: To leave the PICList
.....piclist-unsubscribe-requestKILLspamspam@spam@mitvma.mit.edu


2000\12\22@203628 by Dmitry Kiryashov

flavicon
face
Hi Scott, James and other guys.

> > >         swapf   low,F   ;0.c
> > >         swapf   high,F  ;0.a

since W is holding a.b it can be shrieked down

       addwf   high,W  ;0.a+a.b
       skpnc
       incf    high,F
       addwf   low,F
       skpnc
       incf    high,F

It is just 6 commands instead of 7.

14 clocks at all. Nikolai wasn't saying
anything yet, what about shrink it down
to 12 for this case ? ;)

WBR Dmitry.

{Quote hidden}

--
http://www.piclist.com hint: To leave the PICList
piclist-unsubscribe-requestspamKILLspammitvma.mit.edu


2000\12\22@231629 by Nikolai Golovchenko

flavicon
face
Privet Dmitry!

> 14 clocks at all. Nikolai wasn't saying
> anything yet, what about shrink it down
> to 12 for this case ? ;)

I stopped trying to understand your super small snippets
long ago :) Mainly for the sake of my health. After seeing
swaps and xors on every other line my eyes start to swap and
xor...


S Novym Godom!

Nikolai

--
http://www.piclist.com hint: To leave the PICList
.....piclist-unsubscribe-requestKILLspamspam.....mitvma.mit.edu


2000\12\23@071633 by Ray Gardiner

flavicon
face
       Let me see if i got this correct, if we use the expansion

       x/15 = x/16 + x/256 + x/4096

       (actual = 0.66667, 3rd order approximation = 0.66665 )

       factoring out 1/16 successively,

       x/15 = 1/16( x + x/16 + x/256)

       and further,

       x/15 = 1/16( x + 1/16(x + x/16))

       seems to be a simplification that would suggest a looped
       version that computes  x+x/16 each iteration might be a
       good solution, also more terms would improve accuracy.

       of course x/16 could make good use of swapf.



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


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