Post by thread:[PIC]: Algorithm for 10^x

On Wed, 16 Aug 2000, Andrzej W.Baranski wrote: > Andrzey Baranski@ESA > 08/16/2000 02:02 PM > > Hello, > Does anybody know about an algorithm to calculate an exponential > function 10^x, where x is an 12-bits quantity. > > Thanks in advance for your help. I'd suggest Feynman's algorithm as described in Knuth's Volume 1 "The Art of Computer Programming: Fundamental Algorithms" (see chapter 1's homework exercises). I've implemented it in BASIC a long time ago (I believe I posted it at one time even) but I haven't implemented it with a pic. As an alternative to an iterative algorithm, you may wish to consider a lookup table and first order linear interpolation. This is what I use for calculating logarithms. See these for examples: www.dattalo.com/technical/software/pic/piclog.html http://www.dattalo.com/technical/theory/logs.html BTW, what are you trying to do? Scott -- http://www.piclist.com hint: The PICList is archived three different ways. See http://www.piclist.com/#archives for details.

Ok, but how is that scaled. What I mean by this: The binary value 000000000000 represents: x.xxx The binary value 111111111111 represents: y.yyy What are x.xxx and y.yyy? Or do you mean that 000000000000 represents -80 dB and 111111111111 represents +10 dB? Bob Ammerman RAm Systems (contract development of high performance, high function, low-level sofftware) From: Andrzej W.Baranski <spam_OUTabaranskTakeThisOuTESTEC.ESA.NL> To: <.....PICLISTKILLspam@spam@MITVMA.MIT.EDU> Sent: Wednesday, August 16, 2000 9:33 AM Subject: Re: [PIC]: Algorithm for 10^x > Andrzey Baranski@ESA > 08/16/2000 02:33 PM > > Hello Bob, > Thanks for your reply. > The x is an output from a log amplifier which has a range from -80 dB to 10 > dB > > Andrzej (Andy) W.Baranski > > -- > http://www.piclist.com hint: The PICList is archived three different > ways. See http://www.piclist.com/#archives for details. -- http://www.piclist.com hint: The PICList is archived three different ways. See http://www.piclist.com/#archives for details.

Andrzey Baranski@ESA 08/16/2000 02:53 PM The -80 dB is 000000000000 and +10 dB is 111111111111 Bob Ammerman <RAMMERMANKILLspamPRODIGY.NET> on 16/08/2000 12:41:05 Please respond to pic microcontroller discussion list <.....PICLISTKILLspam.....MITVMA.MIT.EDU> To: EraseMEPICLISTspam_OUTTakeThisOuTMITVMA.MIT.EDU cc: (bcc: Andrzey Baranski/estec/ESA) Subject: Re: [PIC]: Algorithm for 10^x Ok, but how is that scaled. What I mean by this: The binary value 000000000000 represents: x.xxx The binary value 111111111111 represents: y.yyy What are x.xxx and y.yyy? Or do you mean that c represents -80 dB and 111111111111 represents +10 dB? Bob Ammerman RAm Systems (contract development of high performance, high function, low-level sofftware) From: Andrzej W.Baranski <abaranskspam_OUTESTEC.ESA.NL> To: <@spam@PICLISTKILLspamMITVMA.MIT.EDU> Sent: Wednesday, August 16, 2000 9:33 AM Subject: Re: [PIC]: Algorithm for 10^x > Andrzey Baranski@ESA > 08/16/2000 02:33 PM > > Hello Bob, > Thanks for your reply. > The x is an output from a log amplifier which has a range from -80 dB to 10 > dB > > Andrzej (Andy) W.Baranski > > -- > http://www.piclist.com hint: The PICList is archived three different > ways. See http://www.piclist.com/#archives for details. -- http://www.piclist.com hint: The PICList is archived three different ways. See http://www.piclist.com/#archives for details. -- http://www.piclist.com hint: The PICList is archived three different ways. See http://www.piclist.com/#archives for details.

At 02:02 PM 8/16/00 +0100, Andrzej W.Baranski wrote: >Hello, >Does anybody know about an algorithm to calculate an exponential >function 10^x, where x is an 12-bits quantity. You can use a CORDIC algorithm. Best regards, =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= Spehro Pefhany --"it's the network..." "The Journey is the reward" KILLspamspeffKILLspaminterlog.com Info for manufacturers: http://www.trexon.com Embedded software/hardware/analog Info for designers: http://www.speff.com Contributions invited->The AVR-gcc FAQ is at: http://www.bluecollarlinux.com =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= -- http://www.piclist.com hint: The PICList is archived three different ways. See http://www.piclist.com/#archives for details.

> At 02:02 PM 8/16/00 +0100, Andrzej W.Baranski wrote: > > >Hello, > >Does anybody know about an algorithm to calculate an exponential > >function 10^x, where x is an 12-bits quantity. Here is a little analysis of a different sort of way to go about this. We are given by Andrzej that 0 counts maps to -80 dB and 4095 counts map to +10 dB. Now, assume that we are dealing with dB SPL, where we have 20 dB per decade. (A similar analysis can be performed for dB IL, with 10 dB per decade). We want to figure out how many of the 4096 counts corresponds to a doubling of the value (trust me, you'll see why): 4096 counts = 90 dB 1 dB corresponds to 4096/90 == 45.511111 counts A factor_of_10 (20 dB) corresponds to 20*4096/90 == 910.22222 counts A factor_of_2 corresponds to a factor_of_10 * the log10(2) (ie: the base 10 log of 2) (ie: 0.30103): Thus a factor_of_2 corresponds to 20*4096/90*0.30103 == 274.004 counts. Note how conveniently close to 274 that is! So, one way we could solve this problem would be to compute how many factors of two are in the result as follows: pow_of_2 = raw_counts / 274 // integer division value_left = raw_counts % 274 // integer remainder Now, we build a table of 274 precomputed values. These values are the number represented by the count values 0 through 273. They could be computed on a PC like this: for i = 0 to 273 precomputed_value[i] = 0.0001 * 2 ^ (i / 274.0) next i Note that the first element of value[i] = 0.0001 * 2 ^ 0 == 0.0001 = 10 ^ -4 which is -80 dB SPL. The last element of value[i] = 0.0001 * 2 ^ (273/274) which is nearly twice as much. If we had one more entry in the table it would be 0.001 * 2 ^ (274/274) which is 0.0002. This shows that the function will be 'smooth' as we wrap around the table with increasing raw counts. The precomputed values could be stored in any convenient format: binary, decimal, bcd, whatever. So, now to compute 10^x, where x is our log value: temp = precomputed_value[i] while (pow_of_2-- > 0) temp = temp + temp The only arithmetic operation we need to be able to perform on our value is doubling, which is trivial for binary and very easy to do in BCD or DECIMAL formats. Of course we do need a chunk of memory to store the "precomputed_value" table, but that could be quite a bit less than a full floating point package. For dB IL (where a doubling is 10 dB) we would only need half as many entries in the table. Bob Ammerman RAm Systems (contract development of high performance, high function, low-level sofftware) -- http://www.piclist.com hint: The PICList is archived three different ways. See http://www.piclist.com/#archives for details.

Dmitry, could you please explain how to apply CORDIC to exponential function? I just recently started to learn about that algorithm and how to use it for magnitude, phase, sine and cosine calculations. But I would like to learn how to use CORDIC for other elementary math. Not much pointers on the net :( BTW, it doesn't look so good for magnitude calculation. It takes around 1500 cycles for PIC to find sqrt(x^2+y^2), where x, y are 16 bit signed numbers. Probably, using good square and square root routines would be faster in that case. Thanks in advance, Nikolai P.S. Good starting point to get into CORDIC: http://www.dspguru.com/info/faqs/cordic.htm ---- Original Message ---- From: Dmitry Kiryashov Sent: Wednesday, August 16, 2000 16:57:11 To: RemoveMEPICLISTTakeThisOuTMITVMA.MIT.EDU Subj: [PIC]: Algorithm for 10^x {Quote hidden}> Yeah, probably CORDIC is best what you can do with that. > For 12 bits you will need 12 cycles(or loops) to get > result. Try to search on the webs for CORDIC related > math for fast tracking into it. > WBR Dmitry. >> At 02:02 PM 8/16/00 +0100, Andrzej W.Baranski wrote: >> >> >Hello, >> >Does anybody know about an algorithm to calculate an exponential >> >function 10^x, where x is an 12-bits quantity. >> >> You can use a CORDIC algorithm. -- http://www.piclist.com hint: To leave the PICList spamBeGonepiclist-unsubscribe-requestspamBeGonemitvma.mit.edu>

Hi Nikolai. ;) > Dmitry, could you please explain how to apply CORDIC to exponential > function? I'm not promising alot but as only will have 20 free minutes to go other office location I will search for those docs in backed up database of file server. I remember that there were many articles in the past how to apply CORDIC for non standart math functions and hopefully for exponential too. (There was a discussion somewhere that CORDIC can be applied for that but doubled iterations are required for some cases) > I just recently started to learn about that algorithm and how to use > it for magnitude, phase, sine and cosine calculations. But I would > like to learn how to use CORDIC for other elementary math. Not much > pointers on the net :( Try altavista with: +CORDIC +"math*" +"exponent*" I guess it should works. I played with CORDIC together with vertical math to significantly reduce code size and execution time for some correlation based signal detection. Because it is very easy to do number shifting in vertical math. Special thanks to Scott Dattalo and John Payson. You guys opened a door for me into such a upside down beautiful world ;) > BTW, it doesn't look so good for magnitude calculation. It takes > around 1500 cycles for PIC to find sqrt(x^2+y^2), where x, y are 16 > bit signed numbers. Probably, using good square and square root > routines would be faster in that case. 1500 is sounding too long.. Probably you are doing correction on every iteration not finally ? I'll be curious to look your code if that is possible. Looks like a good candidate for optimization ;) WBR Dmitry. -- http://www.piclist.com hint: To leave the PICList TakeThisOuTpiclist-unsubscribe-requestEraseMEspam_OUTmitvma.mit.edu>

part 1 2797 bytes content-type:text/plain; charset=us-ascii (decoded 7bit) What I found on the net was something about 'linear' and 'hyperbolic' rotations. Using this kind of rotations, functions like ln/exp/sqrt/... can be calculated. But hyperbolic stuff is above my understanding, especially rotations :) So I would be very glad if you find a simple explanation... Take a look at the magnitude routine in attachment. Correction is made outside the loop, so it's not the main problem. Most of the time in the loop is spent on register shifts. So vertical math may probably help. However, if a 16 bit register used vertically, it looks like it would take 16 8-bit registers. Can that be avoided? Enjoy :) Nikolai ---- Original Message ---- From: Dmitry Kiryashov <RemoveMEzewsTakeThisOuTAHA.RU> Sent: Thursday, August 17, 2000 23:05:23 To: PICLISTEraseME.....MITVMA.MIT.EDU Subj: [PIC]: Algorithm for 10^x {Quote hidden}> Hi Nikolai. ;) >> Dmitry, could you please explain how to apply CORDIC to exponential >> function? > I'm not promising alot but as only will have 20 free minutes to go other > office location I will search for those docs in backed up database of > file > server. I remember that there were many articles in the past how to > apply > CORDIC for non standart math functions and hopefully for exponential > too. > (There was a discussion somewhere that CORDIC can be applied for that > but > doubled iterations are required for some cases) >> I just recently started to learn about that algorithm and how to use >> it for magnitude, phase, sine and cosine calculations. But I would >> like to learn how to use CORDIC for other elementary math. Not much >> pointers on the net :( > Try altavista with: +CORDIC +"math*" +"exponent*" I guess it should > works. > I played with CORDIC together with vertical math to significantly reduce > code size and execution time for some correlation based signal > detection. > Because it is very easy to do number shifting in vertical math. Special > thanks to Scott Dattalo and John Payson. You guys opened a door for me > into such a upside down beautiful world ;) >> BTW, it doesn't look so good for magnitude calculation. It takes >> around 1500 cycles for PIC to find sqrt(x^2+y^2), where x, y are 16 >> bit signed numbers. Probably, using good square and square root >> routines would be faster in that case. > 1500 is sounding too long.. Probably you are doing correction on > every iteration not finally ? I'll be curious to look your code if > that is possible. Looks like a good candidate for optimization ;) > WBR Dmitry. > -- > http://www.piclist.com hint: To leave the PICList > EraseMEpiclist-unsubscribe-requestmitvma.mit.edu> part 2 4450 bytes content-type:application/octet-stream; name="magnitude16.asm" (decode) part 3 142 bytes -- http://www.piclist.com hint: The list server can filter out subtopics (like ads or off topics) for you. See http://www.piclist.com/#topics

Andy, thanks for the pointer. The article makes things a bit more clear. I found the modified code (original from Dr Dobbs October 1990) referred to in this article at: http://devil.ece.utexas.edu/code.html The code can calculate all functions that are possible using CORDIC algorithm. Nikolai ---- Original Message ---- From: Andrzej W.Baranski <RemoveMEabaranskEraseMEEraseMEESTEC.ESA.NL> Sent: Wednesday, August 23, 2000 18:04:25 To: RemoveMEPICLISTspam_OUTKILLspamMITVMA.MIT.EDU Subj: [PIC]: Algorithm for 10^x {Quote hidden}> Andrzey Baranski@ESA > 08/23/2000 04:04 PM > First let me thank you, to all who took their time to replay to my question, > but particularly to Bob for his, as usual, in depth explanation. > I've just got hold of September issue of Dr.Dobb's Journal, and there's > an article by Michael Pashea " Microcontrollers & CORDIC Methods", > The source code ( cordic.txt and cordic.zip ) is at > http://www.ddj.com/ftp/2000/2000_09/ > Regards > Andrzej (Andy) W.Baranski > -- > http://www.piclist.com hint: The list server can filter out subtopics > (like ads or off topics) for you. See http://www.piclist.com/#topics -- http://www.piclist.com hint: The PICList is archived three different ways. See http://www.piclist.com/#archives for details.