Searching \ for '[PIC]: Divide by 15 was [PIC]: Challenge! (Everyon' in subject line. ()
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.
'[PIC]: Divide by 15 was [PIC]: Challenge! (Everyon'
2000\12\22@120413 by

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

---
jamesnewtonpiclist.com 1-619-652-0593
PIC/PICList FAQ: http://www.piclist.com or .org

{Original Message removed}
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
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-requestmitvma.mit.edu

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

skpnc
incf    high,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-requestmitvma.mit.edu

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-requestmitvma.mit.edu

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.

--