Searching \ for 'Division by Constants' in subject line. ()
Help us get a faster server
FAQ page: piclist.com/techref/method/math.htm?key=division
Search entire site for: 'Division by Constants'.

Truncated match.
'Division by Constants'
1999\07\24@093643 by

Hi Folks,

Quick question for the Math Wizzes out there.

Is there a series method of doing a divide by a constant?  I'm thinking of
the divide by three operation:

n/3 = x/2 - x/4 + x/8 - x/16 + x/32 - x/64...

which is very easy to code and is very fast.  Of course, powers of two work
the same way.

Is there a general case for non-powers of two?

I got asked for a routine which needs a divide by seven and wondered if
there was a better way of doing it instead of the methods which use a
variable.

Thanx,

myke

Myke Predko wrote:

> Quick question for the Math Wizzes out there.

Sorry, pass!

> Is there a series method of doing a divide by a constant?  I'm
> thinking of the divide by three operation:
> n/3 = x/2 - x/4 + x/8 - x/16 + x/32 - x/64...

From the last thread on this subject, you mean?

> which is very easy to code and is very fast.

OK, so what's the problem then?  This approach is better described as
the "multiply by 1/3" operation, and it absolutely general.  IOW, for
each division, you determine the recurring binary expansion of the
fraction, and code that.

>  Of course, powers of two work the same way.

You mean, they only have one term.

> Is there a general case for non-powers of two?

Yep.  But it eludes me right at the moment.  I have to go on a 400 km
and return trip today.

> I got asked for a routine which needs a divide by seven and wondered
> if there was a better way of doing it instead of the methods which use
> a variable.

What methods are they?  Do you mean better than the above method?  I
don't think so, it is pretty accurate.

What was determined on the last round is that you have to be *very*
careful not to lose precision during the summing operation.
--
Cheers,
Paul B.

I was fooling around with this today (avoiding fixing
the oven, I'm sure I'll have to pay for that soon),
and I found an interesting twist on this series.

I wasn't (not having noticed or been around for the
previous round that Paul mentioned) quite sure
how the series for 1/3 might have been derived,
so I was trying to come up with a demonstration
of it, hoping I could find a general formula.

popped out of an Euler transformation somehow, and I was
fooling around with that. What I noticed, however, was that
if the Euler transformation was applied backward of what
I had first thought (and I'm not this smart, this is an
immediate consequence of a derivaton in R.W. Hamming's
book on Numerical Methods, section 12.6, on page 203 of
the Dover edition), that you can improve the convergence
of such a series while still working exclusively with
powers of two. In particular, the series

1/2 * ( 1/4 + 1/16 + 1/64 + 1/256 + ... + 1/(4^n) + ... )

Also converges to 1/3, but at a much quicker rate.
I calculated the two series in Excel to demonstrate:

Index   Myke's Series   Powers of 1/4
1       0.5             0.25
2       0.25            0.3125
3       0.375           0.328125
4       0.3125          0.33203125
5       0.34375         0.333007813
6       0.328125        0.333251953
7       0.3359375       0.333312988
8       0.33203125      0.333328247
9       0.333984375     0.333332062
10      0.333007813     0.333333015
11      0.333496094     0.333333254
12      0.333251953     0.333333313
13      0.333374023     0.333333328
14      0.333312988     0.333333332
15      0.333343506     0.333333333
16      0.333328247     0.333333333
17      0.333335876     0.333333333
18      0.333332062     0.333333333
19      0.333333969     0.333333333
20      0.333333015     0.333333333
21      0.333333492     0.333333333
22      0.333333254     0.333333333
23      0.333333373     0.333333333
24      0.333333313     0.333333333
25      0.333333343     0.333333333
26      0.333333328     0.333333333
27      0.333333336     0.333333333
28      0.333333332     0.333333333
29      0.333333334     0.333333333
30      0.333333333     0.333333333
31      0.333333333     0.333333333

Thus, the replacement series requires almost exactly half
as many terms to achieve the same degree of accuracy.

Not that this answers Myke's question, but I
thought it was kind of useful.

I suppose I really should try to fix the oven
before my wife starts getting cranky.

--Bob

On Sat, Jul 24, 1999 at 09:36:03AM -0400, Myke Predko wrote:
{Quote hidden}

--
============================================================
Bob Drzyzgula                             It's not a problem
============================================================

Bob Drzyzgula <picDRZYZGULA.ORG> wrote:

{Quote hidden}

...  all of which amounts to multiplying the Numerator (N) by the binary
expansion of 1/the Denominator (1/D). Note that the binary digits of 1/3
are a repeating fraction, 0.01010101......, and that the positions with
1's correspond to the terms that are present in Bob's series. Take the
same expansion of any fraction, and do likewise. In Myle's original case,
1/7 = 0.0010010010......

Dave

Maybe I'm just pointing out the obvious, but it seems to me that the
algorithm to generate that series (or any series not involving negative
coefficients for any of the terms) can easily be generated by the simple
algorithm:

CLS
b = 1 / 3       ' The required fraction
tol = .0001   ' As needed
a = 0
d = .5
d2 = 2
WHILE ABS(a - b) > tol
c = a + d
d = d / 2
d2 = d2 * 2
IF c <= b THEN a = c: PRINT "1/"; d2 ' This term is included, so print it out
WEND

Sean

At 10:59 PM 7/24/99 -0700, you wrote:
{Quote hidden}

| Sean Breheny
| Electrical Engineering Student
\--------------=----------------
Save lives, please look at http://www.all.org
Personal page: http://www.people.cornell.edu/pages/shb7
shb7cornell.edu ICQ #: 3329174
________________________________________________________
NetZero - We believe in a FREE Internet.  Shouldn't you?
Get your FREE Internet Access and Email at

OOPS, the results printed by that BASIC program are wrong:

>Maybe I'm just pointing out the obvious, but it seems to me that the
algorithm to generate that series (or any series not involving negative
coefficients for any of the terms) can easily be generated by the simple
algorithm:
{Quote hidden}

d2 = d2 * 2  ' **** RIGHT HERE
{Quote hidden}

| Sean Breheny
| Electrical Engineering Student
\--------------=----------------
Save lives, please look at http://www.all.org
Personal page: http://www.people.cornell.edu/pages/shb7
shb7cornell.edu ICQ #: 3329174
________________________________________________________
NetZero - We believe in a FREE Internet.  Shouldn't you?
Get your FREE Internet Access and Email at

On Sat, 24 Jul 1999, Dave Bell wrote:

{Quote hidden}

Bingo!

This is the way those routines I posted yesterday work. 1/7 is
particularly 'nice' because there are only two binary 1's in a run of 8
binary digits. Hence there are only two additons. The only caveat is that
these need to be 16 bits. Roundoff errors would kill you otherwise.

If I were to obtain a 16-bit result instead of 8, I'd certainly
investigate that repeating '001' pattern.

As a general rule-of-thumb, I'd say that series approximations on a pic
are not the way to go. If you're looking for upto 16-bit results then an
optimized algorithm and/or a look-up table with interpolation is a better
way to go.  If you need more than 16-bits then the trade off is less
clear. (Division by a constant would still be handled more efficiently
using these specialized algorithms. However, finding the arcsine of a
32-bit floating point number, well... Who'd want to do that on a pic? :)

On Sun, Jul 25, 1999 at 07:38:02AM -0700, Scott Dattalo wrote:
> On Sat, 24 Jul 1999, Dave Bell wrote:
>
> > Bob Drzyzgula <picDRZYZGULA.ORG> wrote:
> >
> > >I was fooling around with this today (avoiding fixing
> > >the oven, I'm sure I'll have to pay for that soon),
> > >and I found an interesting twist on this series.
> >
> > ...  all of which amounts to multiplying the Numerator (N) by the binary
> > expansion of 1/the Denominator (1/D). Note that the binary digits of 1/3
> > are a repeating fraction, 0.01010101......, and that the positions with
> > same expansion of any fraction, and do likewise. In Myle's original case,
> > 1/7 = 0.0010010010......
>
> Bingo!

<Sigh> Yet another forest/tree discrimination problem for
me, I think.  Seven years of college mathematics just seems
like a liability sometimes. :-)

On the plus side, I did finally figure out what was
wrong with the oven -- contacts melted in the thermal
switch when the bake unit failed and arced all over
the eggplant. I must say though, the hassle was worth
not having to eat the eggplant...

> .... (Division by a constant would still be handled more efficiently
> using these specialized algorithms. However, finding the arcsine of a
> 32-bit floating point number, well... Who'd want to do that on a pic? :)

Probably some Linux freak... :-)

--Bob

--
============================================================
Bob Drzyzgula                             It's not a problem
============================================================

Now i remember this. I came across this by wondering what it would be like
if there were decimal points in binary. thus to come up for a series to
devide by some number, say 9 for instance, just do long division in binary
of 9 into 1:
.0001100011...
1001) 1.0000000000
-1 001
1100
-1001
10000
-1001
110....

which coresponds to 1/9=1/16 + 1/32 + 1/512 + 1/1024...
neat stuff!

------------------------------------------------------------------------------
A member of the PI-100 Club:
3.1415926535897932384626433832795028841971693993751
058209749445923078164062862089986280348253421170679

On Sat, 24 Jul 1999, Dave Bell wrote:

{Quote hidden}

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