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: Jaap van Ganswijk 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/chipdir/ - USA -- http://www.xs4all.nl/~ganswijk/chipdir/ - 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: Jaap van Ganswijk 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: Jaap van Ganswijk 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: Jaap van Ganswijk 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/chipdir/ - USA California -- http://www.eskimo.com/~cadfael/chipdir/ - USA Seattle [New!] -- http://www.xs4all.nl/~ganswijk/chipdir/ - 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: Jaap van Ganswijk 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: Jaap van Ganswijk 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: Jaap van Ganswijk 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: Jaap van Ganswijk 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/chipdir/ - USA -- http://www.xs4all.nl/~ganswijk/chipdir/ - 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" 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: Jaap van Ganswijk 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/chipdir/ - USA -- http://www.xs4all.nl/~ganswijk/chipdir/ - 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: Jaap van Ganswijk 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