Post by thread:[PIC] 64 bit math fixed or floating point divide 4

I need to improve on the speed of some arbitrary-precision division and multiplication routines written for the CCS (CCSinfo.com) compiler in C code for the PIC18F8722. I would like to find a 64/64 bit or 64/48 bit fixed or floating point division routine in assembly for the PIC. I also require 48 bit multiplication. So far I have not had much luck in my search. Does anybody know if such a routine has been written? I require a great deal of precision in my application. I am a hardware engineer, assembly language is not my specialty, so I would prefer not to reinvent the wheel if possible. The Matlab equations I must perform on the PIC are attached. Thanks, Clay format long; Fout = 12.1*10^9 % desired output freq FGHz = Fout/2; % fundamental frequency before doubler Fref = 684.26*10^6; % nominal reference freq if FGHz < 6*10^9 % # of zeroed accumulator LSB's = nz = 8; % 8 for F < 6 GHz else % 7 for F >= 6 GHz nz = 7; end a = floor(2^20*(Fref/FGHz) + 0.5) % accumulator value seed1 = floor(a/2^nz)*2^nz; % accumulator with LSB's forced to zero dr1 = 2^20/seed1; % effective accumulator divide ratio Fref_act1 = FGHz/dr1; % exact reference frequency Fdds1 = (Fref_act1 - 600*10^6)*8 - 600*10^6; % exact DDS frequency if abs(Fdds1 - 66.66666*10^6) < 0.4 % reduce accumulator by 1 if DDS is close to 66.66666 MHz seed = floor(a/2^nz - 1)*2^nz dr = 2^20/seed Fref_act = FGHz/dr Fdds = (Fref_act1 - 600*10^6)*8 - 600*10^6 else seed = seed1 Fref_act = Fref_act1 dr = dr1 Fdds = Fdds1 end DDS_bits = floor(2^48*(Fdds/(300*10^6)) + 0.5) % DDS command bits __________________________________ Yahoo! FareChase: Search multiple travel sites in one click. http://farechase.yahoo.com

life speed wrote: > I need to improve on the speed of some > arbitrary-precision division and multiplication > routines written for the CCS (CCSinfo.com) compiler in > C code for the PIC18F8722. > > I would like to find a 64/64 bit or 64/48 bit fixed or > floating point division routine in assembly for the > PIC. I also require 48 bit multiplication. So far I > have not had much luck in my search. Does anybody > know if such a routine has been written? I require a > great deal of precision in my application. I am a > hardware engineer, assembly language is not my > specialty, so I would prefer not to reinvent the wheel > if possible. The Matlab equations I must perform on > the PIC are attached. Which don't contain any description or comments so are pointless to try and follow. What part of your calculations must be done at run time versus computed up front at assembly time? Do you really need 64 bits of precision (hard to imagine why) or just the dynamic range? If so, floating point may be easier than very wide integer or fixed point arithmetic. Step back and explain what you are trying to accomplish at a higher level. ****************************************************************** Embed Inc, Littleton Massachusetts, (978) 742-9014. #1 PIC consultant in 2004 program year. http://www.embedinc.com/products

At 03:37 PM 11/2/2005 -0800, you wrote: >I need to improve on the speed of some >arbitrary-precision division and multiplication >routines written for the CCS (CCSinfo.com) compiler in >C code for the PIC18F8722. FWIW, last time I looked (<mumble> months ago), I was not able to find a C compiler for an 8-bit class micro with 64 bit floating point numbers. At the time I did have an application where 32 bits was pretty marginal (easily verified in simulations using C double variables) because of numerical issues. {Quote hidden}>I would like to find a 64/64 bit or 64/48 bit fixed or >floating point division routine in assembly for the >PIC. I also require 48 bit multiplication. So far I >have not had much luck in my search. Does anybody >know if such a routine has been written? I require a >great deal of precision in my application. I am a >hardware engineer, assembly language is not my >specialty, so I would prefer not to reinvent the wheel >if possible. The Matlab equations I must perform on >the PIC are attached. I have not tried to analyze what you are doing.. but if you want to sit down and write such routines, it will probably be fairly easy. Try to avoid division as much as possible (entirely if you can), as it's invariably quite a bit slower than multiplication, especially if the 8x8 multiplier in the 18F is used to speed the multiplication routines. Best regards, Spehro Pefhany --"it's the network..." "The Journey is the reward" spam_OUTspeffTakeThisOuTinterlog.com Info for manufacturers: http://www.trexon.com Embedded software/hardware/analog Info for designers: http://www.speff.com ->> Inexpensive test equipment & parts http://search.ebay.com/_W0QQsassZspeff

--- Olin Lathrop <.....olin_piclistKILLspam@spam@embedinc.com> wrote: > Which don't contain any description or comments so > are pointless to try and > follow. > > What part of your calculations must be done at run > time versus computed up > front at assembly time? Do you really need 64 bits > of precision (hard to > imagine why) or just the dynamic range? If so, > floating point may be easier > than very wide integer or fixed point arithmetic. > Step back and explain > what you are trying to accomplish at a higher level. The calculations must all be done at run time, as the input variable "Fout" will always change. Fout can be 24e9, more than 32 bits, and requires precision in the tenths place. Both dynamic range and precision are required, that is why I am looking for 64 bit math routines. I cannot simply scale an imprecise result. I understand the impulse to ask "Do you really need what you're asking for?". Or, "Is there another way that doesn't require the precision?" The answer is: I need the precision. The application is a microwave synthesizer operating at frequencies up to 24 X 10^9 Hz, with sub-Herz resolution, a 40-bit number. To perform the math without rounding errors requires more than 40 bits. Variable "DDS_bits" requires a 48-bit precision result. All the inputs to that last equation must be exact. I hope that is enough explanation, it probably does not make sense for me to try and describe the entire block diagram of the synthesizer in this post. You may be sure if there were a mathematically more simple approach I would have used it. It may be true that 48 bits are sufficient. Now that I have taken the time to explain that I need precision math, will you, if you can, answer my question? Regards, Clay Fout = 1.212456391800000e+010 a = 118355 seed = 118272 Fref_act = 6.837827795551758e+008 dr = 8.86580086580087 Fdds = 7.026223644140625e+007 DDS_bits = 6.592353788661100e+013 __________________________________ Yahoo! FareChase: Search multiple travel sites in one click. http://farechase.yahoo.com

Clay, I looked at your MatLab code and I assume this is similar to what you wish to implement in PIC assembly. If so, then it appears that all divisions can be replaced with multiplications. For example, you write: dr = 2^20/seed Fref_act = FGHz/dr Which can obviously be written as: Fref_act = (FGHz * seed) / 2^20 And division by 2^20 is the same thing as shifting right 20 bit positions. In another place you show a division by a constant. This one can be replaced with a multiplication of 1/constant. Having said this, I don't have any routines to perform 64bit multiplication. However, if I were to write one I'd either start from first principles and implement a shift/add routine, or I'd use pre-existing 32-bit routines. E.g. you may've already noticed that if N and M are 64-bit numbers, they can be written as: N = a*2^32 + b M = c*2^32 + d and N*M can be written as N*M = ac*2^64 + (ad+bc)*2^32 + bd A 64-bit multiplication has been replaced with 4 32-bit multiplications. This can actually be replaced with 3 32-bit multiplications: N*M = ac*2^64 + (ac + bd - (a - b)(c - d)) *2^32 + bd However, the middle term is now signed. Scott

life speed wrote: > The application is a microwave > synthesizer operating at frequencies up to 24 X 10^9 > Hz, with sub-Herz resolution, a 40-bit number. How are you going to measure or synthesize these frequencies to that accuracy unless you've got your own atomic clock? The latest cesmium clocks are good to about 47 bits, so I guess this is at least theoretically possible. > All the inputs to that last equation must be exact. Exact? Really? That will be tough as it requires an inifinte number bits to represent arbitrary values exactly. > You > may be sure if there were a mathematically more simple > approach I would have used it. But that's the point, I'm not sure. It may be that high precision is required for the solution approach you present, but I'm questioning whether there may not be other solution approaches at a higher level. > Now that I have taken the time to explain that I need > precision math, will you, if you can, answer my > question? You've hardly said anything about your application other than it's a "microwave synthesizer". I don't know what that is nor why you think it needs to synthesize frequencies to atomic clock accuracies. In any case, wide multiplies can be done by stringing together numerous 8 bit multiplies. This works just like doing long multiplication by hand with decimal digits. The basic multiplier in your head only works on two 0-9 digits at a time but you can use that basic operation multiple times to multiply large numbers. For example, suppose each upper case letter below is a digit in a decimal number: ABC * DE = E*C + E*B*10 + E*A*100 + D*C*10 + D*B*100 + D*A*1000 The same mechanism can be used to harness the 8x8 multiplier inside the 18F by using bytes instead of decimal digits. The equation above still works if the letters represented bytes and fixed multipliers were powers of 256 instead of 10. ****************************************************************** Embed Inc, Littleton Massachusetts, (978) 742-9014. #1 PIC consultant in 2004 program year. http://www.embedinc.com/products

--- Mike Singer <znatokKILLspamgmail.com> wrote: {Quote hidden}> life speed wrote: > > … need the precision. The application is a > microwave> synthesizer operating at frequencies up > to 24 X 10^9> Hz, with sub-Herz resolution, a 40-bit > number. > "24 X 10^9 Hz with sub-Herz resolution", - your > frequency meter is 11digits precision. > 100 000 000 000 / (60 * 60 * 24 * 365) : one second > per 3000 yearsprecision, cool device. > Congrats, > Mike. Thanks, but I am only one of three engineers working on this project. It does have fantastic phase noise performance and we hope it will bring our company some success. I'll post a link as soon as it is on our web page. Clay __________________________________ Yahoo! FareChase: Search multiple travel sites in one click. http://farechase.yahoo.co

--- Olin Lathrop <.....olin_piclistKILLspam.....embedinc.com> wrote: > How are you going to measure or synthesize these > frequencies to that > accuracy unless you've got your own atomic clock? > The latest cesmium clocks > are good to about 47 bits, so I guess this is at > least theoretically > possible. There is absolute accuracy and relative accuracy, both have value. Our reference is not an atomic clock, but it's absolute accuracy is 5e-7 Hz, which translates to 1.2e-4 Hz at the output. And the reference can be calibrated. > But that's the point, I'm not sure. It may be that > high precision is > required for the solution approach you present, but > I'm questioning whether > there may not be other solution approaches at a > higher level. The math is dictated by the hardware, the hardware is dictate by the performance requirements. I'm sorry it is not practical to explain it all in a post, but there is just no way around the need for precise math. Those 48 bit and 20 bit numbers are going directly into IC's that won't do their job correctly if they are off by even one bit. {Quote hidden}> In any case, wide multiplies can be done by > stringing together numerous 8 > bit multiplies. This works just like doing long > multiplication by hand with > decimal digits. The basic multiplier in your head > only works on two 0-9 > digits at a time but you can use that basic > operation multiple times to > multiply large numbers. For example, suppose each > upper case letter below > is a digit in a decimal number: > > ABC * DE = E*C + E*B*10 + E*A*100 + D*C*10 + > D*B*100 + D*A*1000 > > The same mechanism can be used to harness the 8x8 > multiplier inside the 18F > by using bytes instead of decimal digits. The > equation above still works if > the letters represented bytes and fixed multipliers > were powers of 256 > instead of 10. Thanks, I will have to use this technique. It has been awhile since I wrote any assembly. Clay __________________________________ Yahoo! Mail - PC Magazine Editors' Choice 2005 http://mail.yahoo.com

--- Scott Dattalo <EraseMEscottspam_OUTTakeThisOuTdattalo.com> wrote: > Clay, > > I looked at your MatLab code and I assume this is > similar to what you > wish to implement in PIC assembly. If so, then it > appears that all > divisions can be replaced with multiplications. For > example, you write: > dr = 2^20/seed > Fref_act = FGHz/dr > Which can obviously be written as: > Fref_act = (FGHz * seed) / 2^20 > And division by 2^20 is the same thing as shifting > right 20 bit positions. > In another place you show a division by a constant. > This one can be > replaced with a multiplication of 1/constant. Yes, there is some mathematical simplification that has been done already in C. I posted the original equations to more clearly represent the goal. {Quote hidden}> Having said this, I don't have any routines to > perform 64bit > multiplication. However, if I were to write one I'd > either start from > first principles and implement a shift/add routine, > or I'd use > pre-existing 32-bit routines. E.g. you may've > already noticed that if N > and M are 64-bit numbers, they can be written as: > > N = a*2^32 + b > M = c*2^32 + d > > and N*M can be written as > > N*M = ac*2^64 + (ad+bc)*2^32 + bd > > A 64-bit multiplication has been replaced with 4 > 32-bit multiplications. > This can actually be replaced with 3 32-bit > multiplications: > > N*M = ac*2^64 + (ac + bd - (a - b)(c - d)) *2^32 + > bd > > However, the middle term is now signed. > > Scott Thanks for the tips on the fundamentals of binary math. I'll try and implement them. Clay __________________________________ Yahoo! FareChase: Search multiple travel sites in one click. http://farechase.yahoo.com

----- Original Message ----- From: "life speed" <life_speedspam_OUTyahoo.com> To: <@spam@piclistKILLspammit.edu> Sent: Wednesday, November 02, 2005 3:37 PM Subject: [PIC] 64 bit math fixed or floating point divide 48 bit multiply {Quote hidden}>I need to improve on the speed of some > arbitrary-precision division and multiplication > routines written for the CCS (CCSinfo.com) compiler in > C code for the PIC18F8722. > > I would like to find a 64/64 bit or 64/48 bit fixed or > floating point division routine in assembly for the > PIC. I also require 48 bit multiplication. So far I > have not had much luck in my search. Does anybody > know if such a routine has been written? I require a > great deal of precision in my application. I am a > hardware engineer, assembly language is not my > specialty, so I would prefer not to reinvent the wheel > if possible. The Matlab equations I must perform on > the PIC are attached. > > Thanks, > > Clay > > format long; > Fout = 12.1*10^9 % desired output freq > FGHz = Fout/2; % fundamental frequency > before doubler > Fref = 684.26*10^6; % nominal reference freq > if FGHz < 6*10^9 % # of zeroed accumulator LSB's = > nz = 8; % 8 for F < 6 GHz > else % 7 for F >= 6 GHz > nz = 7; > end > a = floor(2^20*(Fref/FGHz) + 0.5) % accumulator value > seed1 = floor(a/2^nz)*2^nz; % accumulator with LSB's > forced to zero > dr1 = 2^20/seed1; % effective accumulator divide > ratio > Fref_act1 = FGHz/dr1; % exact reference frequency > Fdds1 = (Fref_act1 - 600*10^6)*8 - 600*10^6; % exact > DDS frequency > if abs(Fdds1 - 66.66666*10^6) < 0.4 % reduce > accumulator by 1 if DDS is close to 66.66666 MHz > seed = floor(a/2^nz - 1)*2^nz > dr = 2^20/seed > Fref_act = FGHz/dr > Fdds = (Fref_act1 - 600*10^6)*8 - 600*10^6 > else > seed = seed1 > Fref_act = Fref_act1 > dr = dr1 > Fdds = Fdds1 > end > DDS_bits = floor(2^48*(Fdds/(300*10^6)) + 0.5) % DDS > command bits > > > > > __________________________________ > Yahoo! FareChase: Search multiple travel sites in one click. > http://farechase.yahoo.com > --