Hi, all! I'm using a limited system (atmega32) and trying to come up
with an approximation of y=2^(x/16). y is in the range 80 to 65535.
x is in 256 equal steps. Any suggestions?
I've looked into Taylor series, but the quantity of fractions are
hard to implement efficiently. I'm considering lookup tables and have
an elegant way to do generate 16 orders of magnitude (in base 2),
but can't figure out how to adapt it to 9.677 (log2(65535/80)) orders.
I'm *considering* performing a single divide: x/25, then using the modulus
as in index into a table and shifting by the quotient. That's still kind
of a big table, though.
// small, accurate exponential conversion
// input : 0-255.
// output: 1+2^(t1/16), nominal range: 1 <=> 65535
// actual range: 1 <=> 0xf501(62721)
// note: arpTime should be non-zero
void setArpTime(u08 t1)
{
u08 powref[16]={0x80,0x85,0x8b,0x91, 0x98,0x9e,0xa5,0xad,
0xb5,0xbd,0xc5,0xce, 0xe7,0xe0,0xea,0xf5};
arpTime = 1 + (powref[t1&0x0f]<<8)>>(15-(t1>>4));
// arpTime = (256-t1)*255; // (yuck, linear)
}
--
different MP3 every day! http://gweep.net/~shifty/snackmaster
. . . . . . . . ... . . . . . .
"Anything moving in the zone, even a three-year- | Niente
old, needs to be killed." -Captain R. | shifty@HEHHEHHEHgweep.net
small, quick 2^x
Started by ●March 22, 2005
Reply by ●March 22, 20052005-03-22
Tachyon <shifty@BWAHHAHHAHsidehack.sat.gweep.net> writes:> Hi, all! I'm using a limited system (atmega32) and trying to come up > with an approximation of y=2^(x/16). y is in the range 80 to 65535. > x is in 256 equal steps. Any suggestions? > > I've looked into Taylor series, but the quantity of fractions are > hard to implement efficiently. I'm considering lookup tables and have > an elegant way to do generate 16 orders of magnitude (in base 2), > but can't figure out how to adapt it to 9.677 (log2(65535/80)) orders. > I'm *considering* performing a single divide: x/25, then using the modulus > as in index into a table and shifting by the quotient. That's still kind > of a big table, though. > > // small, accurate exponential conversion > // input : 0-255. > // output: 1+2^(t1/16), nominal range: 1 <=> 65535 > // actual range: 1 <=> 0xf501(62721) > // note: arpTime should be non-zero > void setArpTime(u08 t1) > { > u08 powref[16]={0x80,0x85,0x8b,0x91, 0x98,0x9e,0xa5,0xad, > 0xb5,0xbd,0xc5,0xce, 0xe7,0xe0,0xea,0xf5}; > arpTime = 1 + (powref[t1&0x0f]<<8)>>(15-(t1>>4)); > // arpTime = (256-t1)*255; // (yuck, linear) > }I'm confused. If x is in 256 equal steps, then a simple 16-bit lookup table with 8 bit address will do the job, no? The only trick is converting x to an 8-bit number. -- Randy Yates Sony Ericsson Mobile Communications Research Triangle Park, NC, USA randy.yates@sonyericsson.com, 919-472-1124
Reply by ●March 22, 20052005-03-22
Tachyon wrote:> Hi, all! I'm using a limited system (atmega32) and trying to come up > with an approximation of y=2^(x/16). y is in the range 80 to 65535. > x is in 256 equal steps. Any suggestions? > > I've looked into Taylor series, but the quantity of fractions are > hard to implement efficiently. I'm considering lookup tables and have > an elegant way to do generate 16 orders of magnitude (in base 2), > but can't figure out how to adapt it to 9.677 (log2(65535/80)) orders. > I'm *considering* performing a single divide: x/25, then using the modulus > as in index into a table and shifting by the quotient. That's still kind > of a big table, though. > > // small, accurate exponential conversion > // input : 0-255. > // output: 1+2^(t1/16), nominal range: 1 <=> 65535 > // actual range: 1 <=> 0xf501(62721) > // note: arpTime should be non-zero > void setArpTime(u08 t1) > { > u08 powref[16]={0x80,0x85,0x8b,0x91, 0x98,0x9e,0xa5,0xad, > 0xb5,0xbd,0xc5,0xce, 0xe7,0xe0,0xea,0xf5}; > arpTime = 1 + (powref[t1&0x0f]<<8)>>(15-(t1>>4)); > // arpTime = (256-t1)*255; // (yuck, linear) > } >I'm with Randy on this one. Is x not an integer? If it is then you can either use his 256-element array of answers, or you can use a 16-element array of answers for the fractional part of x/16, and shift up by the integer part of x/16. But if x is an integer then your numbers don't fit. So what goes, and why can't you make x an integer? -- Tim Wescott Wescott Design Services http://www.wescottdesign.com
Reply by ●March 22, 20052005-03-22
in article slrnd40bn3.eg2.shifty@sidehack.sat.gweep.net, Tachyon at shifty@BWAHHAHHAHsidehack.sat.gweep.net wrote on 03/22/2005 09:42:> I'm using a limited system (atmega32) and trying to come up > with an approximation of y=2^(x/16). y is in the range 80 to 65535. > x is in 256 equal steps. Any suggestions? > > I've looked into Taylor series, but the quantity of fractions are > hard to implement efficiently.i don't get what fractions you are typing about. � � � � 2^x ~= � � � � � � � � �1.0 � � � � � � � � � � � � + � � � �0.6930321187 * x � � � � � � � � � � � � + � � � �0.2413797743 * x^2 � � � � � � � � � � � � + � � � �0.0520323499 * x^3 � � � � � � � � � � � � + � � � �0.0135557571 * x^4 0 <= x <= 1 � � |error|/(2^x) < 3.340e-6 �(exact when x=0 and x=1) ain't no fractions there (but it covers one octave instead 16, which is what you want). perhaps, table lookup (for only 256 entries) is the best thing to do. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●March 22, 20052005-03-22
On 2005-03-22, robert bristow-johnson <rbj@audioimagination.com> wrote:> ain't no fractions there (but it covers one octave instead 16, which is what > you want). perhaps, table lookup (for only 256 entries) is the best thing > to do.Sorry folks, I must have explained this horribly :( Let me try again: The input should be 0-255. The output should be 64-65535, doubling every 25.6 input values. In other words: y=64*2^(x/25.6). I don't want to have more than 16 bytes of table lookup. I don't want to use floats. I don't want to use word sizes greater than 16 bits. I don't want to use division. I'm looking for an integer-only method. -- different MP3 every day! http://gweep.net/~shifty/snackmaster . . . . . . . . ... . . . . . . "Anything moving in the zone, even a three-year- | Niente old, needs to be killed." -Captain R. | shifty@EGGSgweep.net
Reply by ●March 22, 20052005-03-22
Tachyon wrote:> On 2005-03-22, robert bristow-johnson <rbj@audioimagination.com> wrote: > >>ain't no fractions there (but it covers one octave instead 16, which is what >>you want). perhaps, table lookup (for only 256 entries) is the best thing >>to do. > > > Sorry folks, I must have explained this horribly :( Let me try again: > > The input should be 0-255. The output should be 64-65535, doubling every > 25.6 input values. In other words: y=64*2^(x/25.6). > > I don't want to have more than 16 bytes of table lookup. I don't > want to use floats. I don't want to use word sizes greater than 16 bits. > I don't want to use division. I'm looking for an integer-only method.So you have 256 possible inputs, each yielding an output no bigger than 65535. A LUT to do the job consists of 256 16-bit words. If your project has the board space, you could put it in PROM (512 by 8?). Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●March 22, 20052005-03-22
Tachyon wrote:> Sorry folks, I must have explained this horribly :( Let me try again:> The input should be 0-255. The output should be 64-65535, doubling every > 25.6 input values. In other words: y=64*2^(x/25.6).> I don't want to have more than 16 bytes of table lookup. I don't > want to use floats. I don't want to use word sizes greater than 16 bits. > I don't want to use division. I'm looking for an integer-only method.It is the 25.6 that makes it hard. If it is 64*2^(x/16) or 64*2^(x/32) then you take the high bits and use them to shift the output. That is, 64*2^(x/16)=64*2^int(x/16)*2^frac(x/16) For integer x there are 16 possible frac(x/16) and 32 possible frac(x/32), I would probably put 16 bit entries into the table, but it might be that eight bit is enough. Then shift it as needed. 2^.0625 = 1.044 2^.1250 = 1.091 2^.1875 = 1.139 ... 2^.9375 = 1.915 Before the binary point is always 1, eight bits may be fine. 2^.0625 = binary 1.00001011 2^.1250 = binary 1.00010111 2^.5000 = binary 1.01101010 2^.9375 = binary 1.11101010 OK, eight bits is probably fine, but I would make it 12 or 16. Then shift left 6+int(x/16) and take the bits to the left of the binary point. -- glen
Reply by ●March 22, 20052005-03-22
in article slrnd41bk3.15gl.shifty@sidehack.sat.gweep.net, Tachyon at shifty@ERASMUJSsidehack.sat.gweep.net wrote on 03/22/2005 18:47:> On 2005-03-22, robert bristow-johnson <rbj@audioimagination.com> wrote: >> ain't no fractions there (but it covers one octave instead 16, which is what >> you want). perhaps, table lookup (for only 256 entries) is the best thing >> to do. > > Sorry folks, I must have explained this horribly :( Let me try again: > > The input should be 0-255. The output should be 64-65535, doubling every > 25.6 input values. In other words: y=64*2^(x/25.6). > > I don't want to have more than 16 bytes of table lookup. I don't > want to use floats. I don't want to use word sizes greater than 16 bits. > I don't want to use division. I'm looking for an integer-only method.the remez optimized series quoted was designed for fixed-point use (56K). because it fits only one octave, you have to strip off the integer part of the input, x, use the series on the fractional part, and then shift the result by the stripped integer part. quite doable in fixed-point. shifty, what are you doing this 2^x on? -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●March 23, 20052005-03-23
In article <slrnd41bk3.15gl.shifty@sidehack.sat.gweep.net>, Tachyon <shifty@ERASMUJSsidehack.sat.gweep.net> wrote: | Sorry folks, I must have explained this horribly :( Let me try again: | | The input should be 0-255. The output should be 64-65535, doubling every | 25.6 input values. In other words: y=64*2^(x/25.6). | | I don't want to have more than 16 bytes of table lookup. I don't | want to use floats. I don't want to use word sizes greater than 16 bits. | I don't want to use division. I'm looking for an integer-only method. And from the original post:> I've looked into Taylor series, but the quantity of fractions are > hard to implement efficiently. I'm considering lookup tables and have > an elegant way to do generate 16 orders of magnitude (in base 2), > but can't figure out how to adapt it to 9.677 (log2(65535/80)) orders. > I'm *considering* performing a single divide: x/25, then using themodulus> as in index into a table and shifting by the quotient. That's stillkind> of a big table, though.Actually, I think your proposed solution here is on the right track: divide the input by 25.4, use the most-significant bits of the fractional value as a lookup into a pre-computed power-of-two table, and shift that value by the integral value. The effect of dividing by 25.4 can be accomplished by multiplying by its reciprocal, which when scaled by the appropriate power of 2 is equivalent to multiplying by 10 (which can be done with shifts and adds): n2 = n << 1; n10 = n2 << 1; n10 = n2 << 1; n10 += n2; At this point, bits 8..11 of n10 contain the integer shift amount, bits 4..7 are the index into the fractional power-of-2 table, and bits 0..3 are a linear offset from the lookup result. The fractional power table is built by taking the midpoints of 16 equal spaced values from 0 .. 1, raising 2 to that power, subtracting 1, then multiplying by 65536 to scale: fracPow2[] = {1435, 4400, 7496, 10730, 14106, 17633, 21315, 25160, 29175, 33369, 37747, 42320, 47095, 52082, 57289, 62727}; To create the final result: nLinear = n10 & 0x0f; nIndex = (n10 >> 4) & 0x0f; nShift = (n10 >> 8) & 0x0f) + 6; /* adding 6 gives us the final *64 */ result = (fracPow2[nIndex] + 65536) << nShift >> 16; The last computation assumes that you can do 32-bit arithmetic. If you can only do 16-bit, then you can code it in low-level assembly language using add/add-with-carry in a loop nShift times: regHi = 1; regLo = fracPow2[nIndex]; count = nShift; loop: add regLo, regLo, regLo; addc regHi, regHi, regHi; sub count, count, 1; bgez count, loop final result is in regHi This description doesn't get into the refinement of using the nLinear bits to linearly adjust the offset from the lookup table value, but even without that the average error is around 1 percent. -- Tim Olson
Reply by ●March 24, 20052005-03-24
On Tue, 22 Mar 2005 23:47:15 +0000 (UTC), Tachyon <shifty@ERASMUJSsidehack.sat.gweep.net> wrote:>On 2005-03-22, robert bristow-johnson <rbj@audioimagination.com> wrote: >> ain't no fractions there (but it covers one octave instead 16, which is what >> you want). perhaps, table lookup (for only 256 entries) is the best thing >> to do. > >Sorry folks, I must have explained this horribly :( Let me try again: > >The input should be 0-255. The output should be 64-65535, doubling every >25.6 input values. In other words: y=64*2^(x/25.6).I presume you mean the output should be 65536 if the input were allowed to be 256. With 255 for input, that formula gives 63785, not 65535. Yes, I'm being pedantic, but if you want an output of 65535 (max unsigned 16 bit integer) for an input of 255 you need to tweak your formula.>I don't want to have more than 16 bytes of table lookup. I don't >want to use floats. I don't want to use word sizes greater than 16 bits. >I don't want to use division. I'm looking for an integer-only method.Do you have plenty of code space, or does that defeat the 'small' criterion? Here are two solutions, the first rather crudely brute-force: if (x == 0) y = 64; else if (x == 1) y = 66; else if (x == 2) y = 68; else if (x == 3) y = 69; else if (x == 4) y = 71; else if (x == 5) y = 73; else if (x == 6) y = 75; ... else if (x == 253) y = 60423; else if (x == 254) y = 62081; else y = 63785; Okay, that's not quick except for x near zero. The second is better, it's a binary tree of nested if-else's for ranges of the value of x. This also has several hundred comparisons, but the processor would only execute eight comparisons to get any value of y for x in he range 0-255. Here's a start on it: if (x < 128) if (x < 64) if (x < 32) if (x < 16) if (x < 8) if (x < 4) if (x < 2) if (x < 1) y = 64; // x = 0 else y = 68; // x = 1 else // (x < 2) is false if x < 3) y = 69; // x = 2 else y = 71; // x = 3 ... Of course, both of these are effetively lookup tables with the table 'hidden' in the code, but you might actually have room for it in code space rather than in data space, especially on Harvard-architecture DSP's. ----- http://mindspring.com/~benbradley
