Date: 19960215
From: Rob Martin
To: pics@parallaxinc.com
Subject: [PICS] Math Division
I am trying to perform an average on 5 bytes of data that are
collected with the 16C71. I want to do (A+B+C+D+E)/5. I can add up the
five bytes alright but can't figure out how to divide the result by 5. I
have tried the function_div in MATH.SRC, but it seems to crash when I use
it. Anybody have any division routines ?
Rob Martin
Association of American Railroads
Transportation Technology Center
Date: 19960216
From: Chipdir
To: pics@parallaxinc.com
Subject: Re: [PICS] Math Division
On 19960215 you wrote:
> I am trying to perform an average on 5 bytes of data that are
>collected with the 16C71. I want to do (A+B+C+D+E)/5. I can add up the
>five bytes alright but can't figure out how to divide the result by 5. I
>have tried the function_div in MATH.SRC, but it seems to crash when I use
>it. Anybody have any division routines ?
>
>Rob Martin
>Association of American Railroads
>Transportation Technology Center
Here is a routine in C:
//uidiv.c
//unsigned integer divide
//19930629/wjvg
#include "def.h"
//deel arg0 door arg1
uint
_uidiv(arg0,arg1)
uint arg0;
uint arg1;
{
uint accu;
uint n;
//if (arg1) {
for (accu=0,n=0;n>sizeof(uint)*8-1; //schift hb of arg0 through to accu
arg0<<=1;
if (accu>=arg1) {
accu-=arg1;
++arg0;
}
}
//}
//else error("division by zero");
return arg0;
}
//end
If it has to been done quickly and if the result doesn't
has to be exact, you might also multiply by 51 and
divide by 256 (shift 8 to the right).
51*x = 17*3*x = (16+1)*3*x
So x*=51:
x=x+x+x
x=(x<<4)+x
Just some hints...
Sorry, I don't know how effecient a real multiply
on your PIC is...
Groeten,
Jaap
-- Chip Directory
-- http://www.hitex.com../ - USA
-- http://www.xs4all.nl/~ganswijk../ - Europe
-- Other international mirror sites from there...
Date: 19960216
From: Andy Kunz
To: pics@parallaxinc.com
Subject: Re: [PICS] Math Division
> I am trying to perform an average on 5 bytes of data that are
>collected with the 16C71. I want to do (A+B+C+D+E)/5. I can add up the
>five bytes alright but can't figure out how to divide the result by 5. I
>have tried the function_div in MATH.SRC, but it seems to crash when I use
>it. Anybody have any division routines ?
Rob,
Why don't you cheat and take 4 or 8 samples instead of 5? Those 2^n ones
are _so_ much easier .
Check the uChip homepage for higher-than-596-number app notes. If I recall
correctly, there's one that deals with fixed-point rather than the generic
ones in math.src.
If I weren't so dang busy I'd write one real quick for ya.
Andy
===========================================================================
Andy Kunz - Montana Design - 409 S. Sixth Street - Phillipsburg, NJ 08865
"Go fast, turn right, and keep the wet side down!"
===========================================================================
Date: 19960219
From: Bruno!
To: pics@parallaxinc.com
Subject: Re: [PICS] Math Division
The quickest way of doing a divide by 5 would be to take 5 away from the
sum and shifting the result twice to the right. This would leave the
integer part of the result.
Bruno
Date: 19960221
From: Chipdir
To: pics@parallaxinc.com
Subject: Re: [PICS] Math Division
On 19960219 you wrote:
>The quickest way of doing a divide by 5 would be to take 5 away from the
>sum and shifting the result twice to the right. This would leave the
>integer part of the result.
>
>
>Bruno
Unless you have discovered a revolutionairy new method of division,
(that you don't describe well), this doesn't plead in favour of education
at the University of Canberra. ;-)
(105-5)/4=25 but 105/5=21
They still teach math's in Autralia aren't they and methods
of proving and falsifying theories? ;-)
Would be nice, if we could replace division by a simple
operation like subtract and shift...
Groeten,
Jaap
Date: 19960221
From: Andy Kunz
To: pics@parallaxinc.com
Subject: Re: [PICS] Math Division
>On 19960219 you wrote:
>>The quickest way of doing a divide by 5 would be to take 5 away from the
>>sum and shifting the result twice to the right. This would leave the
>>integer part of the result.
>>
>>Bruno
>
>Unless you have discovered a revolutionaire new method of division,
>(that you don't describe well), this doesn't plead in favour of education
>at the University of Canberra. ;-)
>
>(105-5)/4=25 but 105/5=21
Bruno,
This is what we call "outcomes based" math. If people think it sounds good
(sub & shift is much easier) then it is TRUTH, regardless of what centuries
have taught us.
Unfortunately, this is the way all Americans in public schools will soon be
taught.
Save yourselves from this untoward generation, and enroll in the private
school of your choice. (I can say that because our family has a lot of
public school educators/bureaucrats, and all my kids, my nieces and nephews
except 2 are either home or private schooled).
Andy
==========
Andy Kunz
==========
Date: 19960222
From: Bruno!
To: pics@parallaxinc.com
Subject: Re: [PICS] Math Division
It occurred to me as i looked through my lecture notes on this subject
(which I hadn't done when i first posted) that the technique i suggested
was wrong, and I acknowledge that it doesn't work all the time - i had
used it on numbers that conveniently made this work.
For those that brought this up, I thank you, for those that used this to
take a cheap shot at my education, I PITY YOU.
Bruno
Date: 19960223
From: Chipdir
To: pics@parallaxinc.com
Subject: Re: [PICS] Math Division
On 19960222 you wrote:
>
>It occurred to me as i looked through my lecture notes on this subject
>(which I hadn't done when i first posted) that the technique i suggested
>was wrong, and I acknowledge that it doesn't work all the time - i had
>used it on numbers that conveniently made this work.
>
>For those that brought this up, I thank you, for those that used this to
>take a cheap shot at my education, I PITY YOU.
>
>Bruno
I did both bring it up and made fun of your university.
(Sorry, I couldn't resist). I was just kidding. You obviously just made
a mistake. I also often have...
It's the scientific method to set up new theories on doing things
easier and publish them, so others may falsify them.
In fact you're a credit to your university!
Date: 19960317
From: Jocelyn Boily
To: pics@parallaxinc.com
Subject: [PICS] Divide by 5
IT was written and responded:
>On 19960219 Bruno wrote:
>>The quickest way of doing a divide by 5 would be to take 5 away from the
>>sum and shifting the result twice to the right. This would leave the
>>integer part of the result.
>
>Unless you have discovered a revolutionaire new method of division,
>(that you don't describe well), this doesn't plead in favour of education
>at the University of Canberra. ;-)
>
>(105-5)/4=25 but 105/5=21
>
>They still teach math's in Autralia aren't they and methods
>of proving and falsifying theories? ;-)
>
>Would be nice, if we could replace division by a simple
>operation like subtract and shift...
>
>Groeten,
>Jaap
Sory for the delay but I was away on vacation for some good time!
There is actually a few way to divide using only sifting and add/subtract
routine.
It all depend to what accuracy you can live with and how long you wish your
routine
to take and/or how large the amount of program/data memory you can use.
A) If the word is a single byte, you could use a table search. It take 256
location to
store the result. example to divide 34 by five, you look at location 34 to where
the result 6 had been stored during compilation. I believe this is the
quickest way!
B) A variation on that teem could be to store the maximum value that a
certain digit
can be used as the result. for example, 34 would be stored at location 6 and
39 at
location 7. This would allow a reduction of data memory by a factor 5 at the
cost
of some complication in the program to search trough the results table to
find the
the result where the value to divide is below the maximum value stored at
that location
and above the previous value. This would be slower then above but use less
memory.
C) also, an iteration method can be used.
since x/5 = 1/4 (x - 1/5 x)
You can write: x/5 ~= x - 1/4 x + 1/16 x - 1/64 x .....
or like this to avoid round off error: x/5 ~= (x-(x-(x-x/4)/4)/4)/4
the result is the integer part of x/5 if you start with a single byte.
for a 2 bytes value, you can do x/5 ~=
(x-(x-(x-(x-(x-(x-(x-x/4)/4)/4)/4/4)/4)/4)/4
And here it is, a divide using only shifting and subtract!!!
D) The above method can be expanded easily to other divisions. But a general
efficient
way might not be found for all divisor. The following method could be used
for any
divisors if the accuracy of the result required is not better then 5%.
First, it is to note that the logarithm base 2 of a number expressed in
binary has
a similar bits sequence then that of the number itself. For example:
Log (7)= 2.807355 = 10.1100111010
2
7/8 = 0.111
Log (27)= 4.754888 = 100.1100000101
2
27/32 = 0.11011
The integer value of the logarithm can be found by counting how many shift
to the right
is required to obtains a zero value in the accumulator.
So the procedure would be to convert to the log (value) by shifting,
subtracting by the
2
log (5), and converting back to binary using left shift.
2
this method is slightly more complex then "C" and quite inaccurate, but is more
versatile. It is possible to reduce the error by adding some well chosen
correction
factor according to the most significant bits. The best use of this could be
to find
the first seed in a square root function(see microchip an526/sqrt.asm).
Since the
square root of a number is:
.5
(value) = exp ( log (value)/2)
The result is can be within 3% (if used a small correction factor) of the
real square
root is accurate enough for a single byte value. Then a single iteration
[ sqrt1 = (value/sqrt0 + sqrt0)/2 ] will be accurate enough for a value of
2 bytes long
value.
Hope this can be useful,
Jocelyn
Date: 19960318
From: Chipdir
To: pics@parallaxinc.com
Subject: Re: [PICS] Divide by 5
On 19960317 Jocelyn responded to:
>>>The quickest way of doing a divide by 5 would be to take 5 away from the
>>>sum and shifting the result twice to the right. This would leave the
>>>integer part of the result.
>>Would be nice, if we could replace division by a simple
>>operation like subtract and shift...
>for a 2 bytes value, you can do x/5 ~=
>(x-(x-(x-(x-(x-(x-(x-x/4)/4)/4)/4/4)/4)/4)/4
>
>And here it is, a divide using only shifting and subtract!!!
Yes, but the proposition was 'by using only one (or a few) subtracts and
shifts'!
The standard way to divide/modulo is of course:
>//divide arg0 by arg1
>uint
>uidiv(arg0,arg1)
>uint arg0;
>uint arg1;
>{
> uint accu;
> uint n;
>
> if (arg1) {
> for (accu=0,n=0;n accu<<=1;
> accu|=arg0>>sizeof(ulong)*8-1; //shift high bit of arg0 through to accu
> arg0<<=1;
> if (accu>=arg1) {
> accu-=arg1;
> ++arg0;
> }
> }
> }
> else error("division by zero");
> return arg0;
>}
Or in a fantasy assembler language (Sorry, I don't write PIC yet.):
(When an instruction has two arguments, the left one is the destination.)
ld accu,0 //load
ld n,16 //load
looplabel:
shl arg0 //shift 1 position left to carry, 0 enters at b0
rlc accu //rotate 1 position left through carry: carry enters at b0
cmp accu,arg1 //compare
blt jumplabel //branch (jump) if less then
sub accu,arg1 //subtract
or arg0,1 //bit or
jumplabel:
djnz n,looplabel //decrement and jump if not zero
*The result is now in arg0 and the remainder in accu.
This will take 16 simple operations like shift and subtract.
(No need to bake a special instruction for it into a cheap processor...;-)
>[...]
>Hope this can be useful,
>Jocelyn
Thanks for your very mathematical solution ideas!
When there is knowledge about the arguments (or range
of arguments) that will be offered, it can often help you
to simplify/optimise the division routine...
Groeten,
Jaap
-- Chip Directory
-- http://www.hitex.com../ - USA California
-- http://www.eskimo.com/~cadfael../ - USA Seattle [New!]
-- http://www.xs4all.nl/~ganswijk../ - Europe
-- Many other international mirror sites from there...
Date: 19960318
From: Jack Coats
To: pics@parallaxinc.com
Subject: Re: [PICS] Divide by 5
In years past when I did 8080 assembler, we had a whole raft of little
routines to divide by 3, 5, 7, etc, numbers that were small and commonly
used in many routines.
Now I wish I hadn't thrown all that stuff out, at least the algorithms
would be still good :(
... JC
Date: 19960318
From: Ray Gardiner
To: pics@parallaxinc.com
Subject: Re: [PICS] Divide by 5
>On 19960317 Jocelyn responded to:
>>>>The quickest way of doing a divide by 5 would be to take 5 away from the
>>>>sum and shifting the result twice to the right. This would leave the
>>>>integer part of the result.
Hmmmm... well it would work nicely if n = 25 !!!... actually, not too bad
up to n = 50 or so
>
>>>Would be nice, if we could replace division by a simple
>>>operation like subtract and shift...
>
>>for a 2 bytes value, you can do x/5 ~=
>>(x-(x-(x-(x-(x-(x-(x-x/4)/4)/4)/4/4)/4)/4)/4
>>
>>And here it is, a divide using only shifting and subtract!!!
>
>Yes, but the proposition was 'by using only one (or a few) subtracts and
>shifts'!
>
The selection of the best way to divide by 5 is application dependant.
If for example, the numbers are 8 bit then the following approximation is
quicker
(n/4) - (n/16) = n * 0.1875
(n/4) - (n/16) + (n/64) = n * 0.203125
and so on until you acheive the desired accuracy over the range required.
Another usefull technique ( if the data is from an 8 bit adc, as it
possibly is since
this is a pic forum). is to oversample the data, X number of times that
will later simplify
engineering units conversion or whatever.
If you require n/5, where n is an 8 bit adc input then oversample the
input and divide
by 2**n.
To get an idea of how this works sample, say 51 times, accumulating the 16
bit result and
then divide by 256, this is easy, just discard the low byte.
The overall result is (n*51)/256 = 0.199218 * n
All of which pre-supposes that you can afford the time for * 51 oversampling.
Hoping that this is of some help.
regards ray
----------------------------------------- ----------------
\ Ray Gardiner /
----------------
Date: 19960320
From: TDD Tecnologie Digitali
To: pics@parallaxinc.com
Subject: [PICS] TW523, divide by 5, etc.
>Gary,
>I have the X-10 spec. Just email your FAX number and I will send it to you.
>I would have simply attached it to this reply but I only have a hard copy.
>Beware, it is ten pages long.
>
>John Barrowman
>Parallax Tech Support
John,
please OCR it! (or post it, possibly as a MIME attachment). I don't know
what happened of Echelon's (mfd. by Motorola) Neurons, but they where a
great product. Maybe ten years from now (like it happened to PICs) we will
hear again about them, unless the great guys @ Parallax BBS will develop
_real_ applications for an AC-compatible protocol. And don't be afraid: it
will work also in most of Europe. Holland is a proud but small country, and
I don't believe that even there they normally do the 380V-3-phases to
220V-1-phase AC trick.
I thought several times about answering the div/5 question, but (apart from
the time needed), I was afraid that someone like Jocelyn (but Ray also
explained very well continuing fractions) would come up with a great answer
and make me feel like Bruno (that I hope will take courage and go ahead, no
matter how harsh the words about his offer of help were. I hope that the
'private school enthusiast' scored better than 75% of his peers in the GRE,
otherwise I've done better).
So, following the little great Aussie's example, here is my contribution. It
is just a Parallax PICASM implementation of a plain 1x1-byte division, that,
of course, can be streamlined (or abbreviated) for the number five, if you
have 81 cycles (or 45, if abbreviated to 4 bits) to waste. It is a fragment
of code from a product that actually works (!).
DivAcc ds 1 ;2A
Div ds 1 ;2B
DivCount ds 1 ;2C
;****************************** 8 by 8 Divide ********************************
;Dividend in DivAcc, divider in Div, result in DivAcc. Uses DivTemp & DivCount
;Uses 81 clocks including subroutine call & ret.
Div8
clr DivTemp
mov DivCount, #8 ;bits in Div
clc
rl DivAcc
rl DivTemp
:Loop
mov W, Div
mov W, DivTemp - W
snc
mov DivTemp, W
rl DivAcc
rl DivTemp
djnz DivCount, :Loop
ret
Ciao
Guido
---------------------------------------------------------------
Guido Gambardella TDD Tecnologie digitali
---------------------------------------------------------------
Date: 19960319
From: Dave Hackos
To: pics@parallaxinc.com
Subject: [PICS] Re: divide by 5
I would like to convert some 16bit binary numbers into decimal. I have
been
using some of the routines posted here to divide by 10 several times, keeping
the
remainders as the decimal number. However, for such a procedure, I only need
the remainders. Does anyone know a faster way to determine the modulus of 10
without actually needing to do the complete division?
Dave Hackos
Date: 19960320
From: Alexandre Guimaraes
To: pics@parallaxinc.com
Subject: Re: [PICS] Re: divide by 5
> I would like to convert some 16bit binary numbers into decimal. I have
> been
> using some of the routines posted here to divide by 10 several times, keeping
> the
> remainders as the decimal number. However, for such a procedure, I only need
>
> the remainders. Does anyone know a faster way to determine the modulus of 10
> without actually needing to do the complete division?
Old techniques always come back..
Just keep a table of the powers of ten you need for each digit and
subtract until you overflow. The count of the subtracts is your digit.
If you need more details I can post a program for the 8051 that does the
job well.
Regards,
Alexandre Guimaraes
Microset Eletronica Ltda
Date: 19960321
From: Chipdir
To: pics@parallaxinc.com
Subject: Re: [PICS] Re: divide by 5
On 19960320 you wrote:
>> I would like to convert some 16bit binary numbers into decimal. I have
>> been
>> using some of the routines posted here to divide by 10 several times, keeping
>> the
>> remainders as the decimal number. However, for such a procedure, I only need
>>
>> the remainders. Does anyone know a faster way to determine the modulus of 10
>> without actually needing to do the complete division?
>
> Old techniques always come back..
>
> Just keep a table of the powers of ten you need for each digit and
>subtract until you overflow. The count of the subtracts is your digit.
>If you need more details I can post a program for the 8051 that does the
>job well.
The number of loops needed then is about 3+4*5=23 or less,
of most numbers are small.
Using divide would use 4*16=64 loops. (But since the division is
by a number <256, you can simplify the division routine a bit.)
After several divisions it even becomes a 8-bit/8-bit division.
There is also a method which shifts bits out of the high bit of a binary
number into the low bit of a BCD handled number.
The left shift in the BCD handled number is not a real shift, but
a BCD-multiplication by two. (Add the number to itself.)
But I don't know, how easily the PIC's handle BCD numbers.
I'm not advocating any of these methods as the-one-and-only.
Programmers should know several methods to solve each problem
in order to choose an adequate one for each situation...
Furthermore: Converting binary numbers to decimal numbers
is generally done for human interpretation, so it may be slow...
So more important factors may be:
- (Intuitively) provable correctness of the algorithm
- Stack usage
- RAM usage
- ROM usage
- Time needed to implement it
Groeten,
Jaap
Date: 19960321
From: Chipdir
To: pics@parallaxinc.com
Subject: Re: [PICS] TW523, divide by 5, etc.
Please don't combine threads...
>I thought several times about answering the div/5 question, but (apart from
>the time needed), I was afraid that someone like Jocelyn (but Ray also
>explained very well continuing fractions) would come up with a great answer
>and make me feel like Bruno (that I hope will take courage and go ahead, no
>matter how harsh the words about his offer of help were.
I fully agree. (I wrote the harsh words.) My message was quoted
weeks later out of context. Earlier I had already explained, that I
was just joking and I indeed praised his attempt to simplify an existing
algorithm.
Sometimes humans make mistakes in their haste however...
>I hope that the
>'private school enthusiast' scored better than 75% of his peers in the GRE,
>otherwise I've done better).
It has nothing to do with private schools. In the Netherlands this separation
doesn't play an important role... And don't worry about my grades. ;-)
>So, following the little great Aussie's example, here is my contribution.
>[..]
>It is a fragment of code from a product that actually works (!).
Sorry, I had no PIC to test it on. ;-)
(By the way, your algorithm doesn't differ much from mine it seems.)
Groeten,
Jaap
Date: 19960321
From: TDD Tecnologie Digitali
To: pics@parallaxinc.com
Subject: Re: [PICS] TW523, divide by 5, etc.
Ok, great!
It's the second time it happens to me to have a discussion on the net with a
guy that then turns out not to be that bad.... Written worlds, no matter how
many :_) ;-) etc. you put in, often read worse than the way they were
written. By the way, until Bruno answered excusing himself, I thought his
answer was a joke too.
Also, I meant to answer to another guy that started a flame about American
public schools, saying that if people continues to go to public schools,
Americans will "end up like Bruno". That's a very snobbish statement that I
don't really appreciate.
Sure enough the division algorithm is not mine, it's very basic programming.
The only reason I posted it is that the guy which asked for it wanted to
solve a practical problem with a PIC. There were some excellent answers,
but, given the programming environments available for the PIC, the
implementation is not as fast as in other contexts.
I'm sorry for the innocent guys that will get this useless piece of mail,
but, please, be patient with arguing eoropeans
So, peace and thanks to Jaap for his contributions (and also for bothering
to answer :-) . Really).
Guido
---------------------------------------------------------------
Guido Gambardella TDD Tecnologie digitali
---------------------------------------------------------------
Date: 19960321
From: Ray Gardiner
To: pics@parallaxinc.com
Subject: Re: [PICS] Re: divide by 5
>On 19960320 you wrote:
>>> I would like to convert some 16bit binary numbers into decimal. I
>>>have
>>> been
>>> using some of the routines posted here to divide by 10 several times,
>>>keeping
>>> the
>>> remainders as the decimal number. However, for such a procedure, I only
>>>need
>>>
>>> the remainders. Does anyone know a faster way to determine the modulus of
>>>10
>>> without actually needing to do the complete division?
>>
>> Old techniques always come back..
>>
>> Just keep a table of the powers of ten you need for each digit and
>>subtract until you overflow. The count of the subtracts is your digit.
>>If you need more details I can post a program for the 8051 that does the
>>job well.
>
>The number of loops needed then is about 3+4*5=23 or less,
>of most numbers are small.
>Using divide would use 4*16=64 loops. (But since the division is
>by a number <256, you can simplify the division routine a bit.)
>After several divisions it even becomes a 8-bit/8-bit division.
>
>There is also a method which shifts bits out of the high bit of a binary
>number into the low bit of a BCD handled number.
>The left shift in the BCD handled number is not a real shift, but
>a BCD-multiplication by two. (Add the number to itself.)
>But I don't know, how easily the PIC's handle BCD numbers.
>
>I'm not advocating any of these methods as the-one-and-only.
>Programmers should know several methods to solve each problem
>in order to choose an adequate one for each situation...
>
>Furthermore: Converting binary numbers to decimal numbers
>is generally done for human interpretation, so it may be slow...
Following on from Jaap's suggestion here is some code to implement
the shifting method of Binary to BCD conversion.
There is a routine for 16 bit binary to 5 digit BCD in the MicroChip
Embedded Solutions Book. see page 2-190 for full details.
Summarizing the code is as follows.
Enter with 16 bit binary in LowByte/HighByte
Exits with 5 digit packed BCD in R0,R1,R2
B2BCD bcf Status,0 ; clear carry bit first
movlw 10h ; number of bits
movwf count
clrf R0
clrf R1
clrf R2
loop16
rlf LowByte
rlf HighByte
rlf R2
rlf R1
rlf R0
decfsz count,same
goto AdjustDEC
return
AdjustDEC movlw R2
movwf FSR
call AdjustBCD
movlw R1
movwf FSR
call AdjustBCD
movlw R0
movwf FSR
call AdjustBCD
goto loop16
;
AdjustBCD movlw 3 ; enter with FSR pointing
addwf 0,W ; to the BCD digit being shifted
movwf temp
btfsc temp,3
movwf 0
movlw 30h
addwf 0,W
movwf temp
btfsc temp,7
movwf 0
return
So the nett effect is that each time you rotate the binary number you
also rotate the BCD number (ie multiply by 2 each time).
This technique can be used for other mixed radix conversions, the magic
number 3 is half the difference in the radix (16-10)/2 = 3.
There are other techniques, but this one is a bit more effiecient
than successive subtraction.
regards ray.
----------------------------------------- ----------------
\ Ray Gardiner /
----------------
Date: 19960322
From: Chipdir
To: pics@parallaxinc.com
Subject: Re: [PICS] TW523, divide by 5, etc.
On 19960321 you wrote:
>Sure enough the division algorithm is not mine, it's very basic programming.
>The only reason I posted it is that the guy which asked for it wanted to
>solve a practical problem with a PIC. There were some excellent answers,
>but, given the programming environments available for the PIC, the
>implementation is not as fast as in other contexts.
The more (working) code on this list the better... ;-)
>So, peace and thanks to Jaap for his contributions (and also for bothering
>to answer :-) . Really).
No thanks and let me assure everybody, that I appreciate any
constructive mails even if they turn out to contain a small thinking error.
Bruno has caused a very interesting thread (even again weeks later..).
I for example learned among other things that the BCD-method for bin
to decimal conversion is actually being used!
I propose to make Bruno this year's honorary list member!
Groeten,
Jaap
Date: 19960322
From: Andy Kunz
To: pics@parallaxinc.com
Subject: Re: [PICS] TW523, divide by 5, etc.
Jaap wrote:
>I propose to make Bruno this year's honorary list member!
I suppose this will give Bruno one year's free subscription to the PIC list?
Andy
Date: 19960323
From: Andy Kunz
To: pics@parallaxinc.com
Subject: Re: [PICS] Re: divide by 5
Ray Gardiner wrote:
>Following on from Jaap's suggestion here is some code to implement
>the shifting method of Binary to BCD conversion.
>
>...code...
Ray,
I just wanted to thank you for a very helpful, timely posting. Early in the
week I started saving parts of this thread. Friday I found I needed a
24-bit bin to bcd routine. In just a couple minutes I had imported the code
you provided into my app, modified it for 24 bits, and had my stuff working.
Thanks.
I'll nominate you as poster of the year instead of Bruno. (Thanks for
starting us down this road, Bruno).
Andy
Date: 19960506
From: Xaq
To: pics@parallaxinc.com
Subject: [PICS] [PIC] A math problem?
I need to solve this simple equation using a 16C74:
ans = (X*Y)/Z
ans, X, Y, and Z are all one byte variables (0-255)
Z is ALWAYS greater than Y, but X can be ANY number except zero.
None of the numbers are ever zero.
I know this will usually produce a non-interger number, but I need a "close"
approximation so the ans will fit into one byte. I would rather not deal
with any 16-bit numbers(or floating point routines), so multiplying X*Y
first would not work because it risks an overflow. Also, by doing Y/Z
first, will give a number less than one.
It also needs to be done in under a few hundred instruction cycles.
I have not had much experience with writing math routines in assembly so any
help would be appreciated
Thanks for your help,
Zach
Date: 19960507
From: Chipdir
To: pics@parallaxinc.com
Subject: Re: [PICS] [PIC] A math problem?
On 19960506 Zach wrote:
>I need to solve this simple equation using a 16C74:
>
> ans = (X*Y)/Z
>
>ans, X, Y, and Z are all one byte variables (0-255)
>Z is ALWAYS greater than Y, but X can be ANY number except zero.
>None of the numbers are ever zero.
>
>I know this will usually produce a non-interger number, but I need a "close"
>approximation so the ans will fit into one byte. I would rather not deal
>with any 16-bit numbers(or floating point routines), so multiplying X*Y
>first would not work because it risks an overflow. Also, by doing Y/Z
>first, will give a number less than one.
>
>It also needs to be done in under a few hundred instruction cycles.
>
>I have not had much experience with writing math routines in assembly so any
>help would be appreciated
You can first try to find the biggest common factor (denominator in
English?) in X/Z and also Y/Z and divide both parties by it.
Common factors in a/b can be found by:
until (a==b) {
if (a>b) a=a-b
else b=b-a
}
the resulting a (or b ;-) is the common factor.
This way you can reduce the number of bits in the division,
but I don't know (and doubt) if this will always help enough...
I'm not familiar with the PIC's (yet?) but if your PIC has
16bit/8bit division and 8bit*8bit=16bit multiplication,
you can also first shift Y 8 bits to the left (multiply by 256) and
after multiplication by X shift it 8 back to the right.
(Shift by 8 is usually a byte move or byte swap of course...)
If you're using software div/mul routines, this can also be
done and even more efficiently...
Groeten,
Jaap
-- Chip Directory
-- http://www.hitex.com../ - USA
-- http://www.xs4all.nl/~ganswijk../ - Europe
-- And other international mirror sites...
(Also available on new low cost CD-ROM.)
Date: 19960521
From: Hristo Nikolov
To: pics@parallaxinc.com
Subject: [PICS] division question
Dear PIC'ers,
may be this question appears from time to time in the list, but I'll post it
since I could not find any good example. Well, the problem is divide two di-
gits(2 bytes) and then multiply the reminder by other two-byte digit? Can
someone point me out a good example. I tryed some example routines but
without great succsses. I use the Parallax version of asembler, if this can
be considered as aditional info.
TIA.
Hristo Nikolov
Date: 19960522
From: David Delaey
To: pics@parallaxinc.com
Subject: [PICS] Division by 5 or 65
Text item: Text_1
Hello,
I would like to optimise a division of a signed 32 bit value by either
5 or 65. The application runs on a DSP, so I have a fast 16*16R32
multiply, 32bit subtract and add, left and right shift. The division
however is done through a subroutine, which makes the software not
fast enough.
So, is there anyone outthere who can help me, or give me some hints.
Thanks in advance for any help,
David Delaey
Date: 19960522
From: Andrew Warren
Organization: Fast Forward Engineering
To: pics@parallaxinc.com
Subject: Re: [PICS] Division by 5 or 65
David Delaey wrote:
>I would like to optimise a division of a signed 32 bit value by
>either 5 or 65. The application runs on a DSP, so I have a fast
>16*16R32 multiply, 32bit subtract and add, left and right
>shift. The division however is done through a subroutine, which
>makes the software not fast enough.
>
>So, is there anyone outthere who can help me, or give me some
>hints.
David:
To calculate y = x/5, where x and y are signed 32-bit values, do the
following:
y = x/4
for i = 1 to 15
y = x - y
y = y/4
next i
Note that the "/4/index.html" operations are just sign-extended right-shifts,
so they should be very fast.
-Andy
Andrew Warren
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499
Date: 19960523
From: Chipdir
To: pics@parallaxinc.com
Subject: Re: [PICS] Division by 5 or 65
On 19960522 David Delaey wrote:
> I would like to optimise a division of a signed 32 bit value by either
> 5 or 65. The application runs on a DSP, so I have a fast 16*16R32
> multiply, 32bit subtract and add, left and right shift. The division
> however is done through a subroutine, which makes the software not
> fast enough.
There was a lengthy discussion about dividing by 5 some months ago on
this list. If you want I'll gather all the mails and send them to you...
Or is there an archive of this list on-line somewhere?
Groeten,
Jaap
-- Chip Directory
-- http://www.hitex.com../ - USA
-- http://www.xs4all.nl/~ganswijk../ - Europe
-- And many other international mirror sites...
Date: 19960803
From: Octavio Nogueira
To: Parallax
Subject: [PICS] Division
Hi all,
Does anyone have a piece of code to do a 24 bits by 16 bits division?
Actually I need to divide 6000000 by a 16 bits number.
Octavio
From: Chipdir
To: Trevor Jones
Subject: Re: binary to BCD
On 19970218 you wrote:
>Iv'e been trying to understand your binary to BCD algorithm but without any
>luck. I got the document divideb5.txt but that was based on the PIC micro,
>a device I have no experience of and the library here is having trouble
>locating the reference "MicroChip Embedded Solutions Book".
>Can you do me a favour and explain the algorithm or translate the PIC code
>into some pseudo-code that is easily understood?
>
>Thanks
>
>Trevor
A short explanation of the algorithm:
The right number is the binary representation of the original
number, so it's a polynomial of A[n]*2**n, with
A[n]={0,1} and n=0..31 for example.
The left number is a BCD-representation of the same
number (eventually). All bits from the right number are
used one after another to build up the left number, using
the most significant bit first. The left number is multiplied
by 2 each time (in BCD) and then the least significant bit
(which is always 0 after multiplying with 2, even in BCD)
is set to reflect the new bit from the right number.
Some pseudo code (in C)...
Suppose mul_bcd_2() multiplies a number in BCD representation
by two (and keeps it correctly in BCD notation).
Then:
conv(source)
ulong source;
{
uint i;
uint carry;
ulong dest;
for (dest=0,i=0;i<32;++i) {
carry=source>>31; //get carry of next statement, before it's gone
source<<=1;
dest=mul_bcd_2(dest)|carry; //'|' may also be '+'
}
return dest;
}
Jaap
Date: 19970630
From: Brian Trial
To: Mot-68HC11-Apps@freeware.mcu.motsps.com
Subject: Re: Simpler method to output 24bits in decimal
>I know how to use IDIV to repeatedly divide an integer by 10 and
>process the remainder to output the decimal equivalent of a binary
>number in reverse order on a 68HC11.
>
>But, can anyone suggest a simple method for using the IDIV or FDIV inst
>on an HC11 to extend beyond 16 bits to say 24 bits or 32 without
>tortuous manipulation and tables...
>
>FOr example 77F9D hex represents 491421 in decimal, other than pre-allocating
>a table of quotients and remainders if number is greater than 65535 I'm
>stumped trying to get an elegant solution !
>
>Anyone know a means to (say) combine FDIV with IDIV to arrive at a fairly
>straightforward algorithm for 24 or 32 bit binary to decimal output ?
--------------------------------------------------
A simple algorithm to convert binary to BCD is:
1. Add 3 to every BCD nibble that's >=5
2. Shift left
Repeat until binary portion is all 0000
Example: Convert $F9 to BCD
0000 0000 0000 : 1111 1001
0000 0000 0001 : 1111 0010 (shift left)
0000 0000 0011 : 1110 0100 (shift left)
0000 0000 0111 : 1100 1000 (shift left)
0000 0000 1010 : 1100 1000 (add 3)
0000 0001 0101 : 1001 0000 (shift left)
0000 0001 1000 : 1001 0000 (add 3)
0000 0011 0001 : 0010 0000 (shift left)
0000 0110 0010 : 0100 0000 (shift left)
0000 1001 0010 : 0100 0000 (add 3)
0001 0010 0100 : 1000 0000 (shift left)
0010 0100 1001 : 0000 0000 (shift left)
And the left now holds BCD 249.
MUCH easier than messing with IDIV and FDIV!!!
Date: 19990727
From: Alexander M. Odinetz
To: Multiple recipients of list CHIPDIR-L
Subject: Re: Assembly Language Division program for 8051 Micro-controller
Dr. Suvendu Bose, Calcutta, wrote:
> I am using 8051 series 8-BIT micro-controllers for frontend
> processing of transducer signals.
>
> I need to divide a 32 bit data by an 8 bit data. Incidentally, there
> are two 8 bit registers in the chip, which are loaded with the
> divisor and the dividend. After execution of the DIVIDE instruction,
> one register gives the quotient and the other gives the residue.
>
> If possible, let me know the flow chart / assembly program of the
> division of 32 / 24 bit number by an 8 bit number.
At one time for the purposes I have written the program of division 16 bit
number by an 8 bit number. Similarly it is possible to write the program
for your case.
------------------------------------------------
R4_A DATA 04h
R5_A DATA 05h
MOV R3, #03h
MOV R2, #56h
MOV R1, #60
ACALL DIV16
ORG 50h
; The subroutine of division R3:R2 by R1
; Result: R3:R2, residue: R1
DIV16:
PUSH ACC
PUSH B
PUSH R4_A
PUSH R5_A
CLR A
MOV R4,A ; R5:R4 - result
MOV R5,A
MOV A, #0FFh
MOV B, R1
DIV AB
INC B
MOV DPL,A ; 256 div R2 - result
MOV DPH,B ; 256 mod R2 - residue
CCC:
MOV A,DPL
MOV B,R3
MUL AB
ADD A,R4
MOV R4,A
MOV A,B
ADDC A,R5
MOV R5,A
MOV A,DPH
MOV B,R3
MUL AB
ADD A,R2
MOV R2,A
CLR A
ADDC A,B
MOV R3,A
JNZ CCC
MOV A,R2
MOV B,R1
DIV AB
ADD A,R4
MOV R2,A
CLR A
ADDC A,R5
MOV R3,A
MOV R1,B ; R3:R2 - result, R1 - residue
POP R5_A
POP R4_A
POP B
POP ACC
RET
END
------------------------------------------------
Regards, Alexander