Exponents using only addition and subtraction

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Porkrind
Posts: 5
Joined: Fri Mar 28, 2008 12:30 am UTC

Exponents using only addition and subtraction

Postby Porkrind » Fri Mar 28, 2008 1:12 am UTC

Basically, I need to implement a function on an embedded system that only has ADD and SUBTRACT opcodes. The function is: f=440*2^((x-69)/12) (A simple Pitch Space function). I can do multiplication and division using repeated addition and bit shifting, but my power rules are pretty rusty and I cannot get my head around this problem.

Note: I know this is possible because I am using the same Zilog z80 processor as the Ti-83, but stripped down a bit. If anyone knows where to get assembly source code for Ti-83 that has power function in it, that would save me a lot of work. I have searched far and wide with no luck.

boss_mc
Posts: 47
Joined: Thu Oct 04, 2007 12:03 am UTC

Re: Exponents using only addition and subtraction

Postby boss_mc » Fri Mar 28, 2008 2:21 am UTC

Do you know that (x-26)/12 is an integer? If so, you can implement exponents using repeated multiplication or division (just increment/decrement the index, performing a multiplication/division each time until the exponent is 0).

If the exponent is a decimal, you'll have a tricker time, the best I can think of this late at night is to take the exponent p/q and use the above method to find 2p and then find the qth-root of this number using an approximating technique. Simple (but slow) method is a basic binary search (pick a number, raise to the qth power and test if it is too big or too small, adjust accordingly and test again). You will never get an exact answer unfortunately (if x is 75 then the answer required is 440*sqrt(2), an irrational number) so you'll have to be approximating somewhere.
while ((*(iterator++) != (LExpression*)next) && (iterator != m_vector.end()){}

Porkrind
Posts: 5
Joined: Fri Mar 28, 2008 12:30 am UTC

Re: Exponents using only addition and subtraction

Postby Porkrind » Fri Mar 28, 2008 2:58 am UTC

If somebody could refresh me, can I not just pull the 21/12 out and go ahead and solve that leaving me ~1.12246x-69*440? That would simplify things a lot.

Hmm, just realized that still leaves me with a loop of ~1.12246*~1.12246 x times which, with repeating addition, is still REALLY drawn out (Plus another 440 additions after that).... Come to think of it, a frequency table doesn't sound so bad after all...

Ril
Posts: 2
Joined: Fri Mar 28, 2008 3:11 am UTC

Re: Exponents using only addition and subtraction

Postby Ril » Fri Mar 28, 2008 3:27 am UTC

The TI source code is held pretty closely, so it's unlikely you'll be able to locate it anywhere.

That said, the method that TI calculators use to calculate everything that's not addition or subtraction is the CORDIC algorithm. Do you have methods available to store and retrieve data from a table? Addition, subtraction, digit shifts and table lookup is all it uses. With enough cycles, you can get arbitrary precision out the algorithm, if need a real accurate answer.

In any case, I direct you to my professor's webpage, he's got a paper or two on calculator methods. http://www.math.ufl.edu/~be/papers.html
The first paper, How Calculators Calculate ought to cover it.

Hope that's helpful.

User avatar
evilbeanfiend
Posts: 2650
Joined: Tue Mar 13, 2007 7:05 am UTC
Location: the old world

Re: Exponents using only addition and subtraction

Postby evilbeanfiend » Fri Mar 28, 2008 11:53 am UTC

how much ram you got free? you can always implement it as a look up table (perhaps with some interpolation between table entries if space is a problem and time isn't)
in ur beanz makin u eveel

User avatar
parallax
Posts: 157
Joined: Wed Jan 31, 2007 5:06 pm UTC
Location: The Emergency Intelligence Incinerator

Re: Exponents using only addition and subtraction

Postby parallax » Fri Mar 28, 2008 12:43 pm UTC

There's always Taylor polynomials. I think most calculators use Taylor polynomials or some variant to calculate trigonometric functions. The Taylor polynomial for that function is 1 + [ln2(x-69)/12]1/2! + [ln2(x-69)/12]2/3! +[ln2(x-69)/12]3/4! + . . .

It should converge rather quickly.
Cake and grief counseling will be available at the conclusion of the test.

Seraph
Posts: 343
Joined: Mon Jul 16, 2007 4:51 pm UTC

Re: Exponents using only addition and subtraction

Postby Seraph » Fri Mar 28, 2008 2:04 pm UTC

A few questions:

How big/small is "x" and what sort of accuracy (how many significant figures) do you need for your result? Can "x-69" be negative?

Why can't use use the other instructions in the Z80?
As your always multiplying by powers of two the bitwise shift command, and the ability to grab one bit from a register, would be extreamly useful in this problem. I know the Z80 has the former, does it have the latter?

Porkrind
Posts: 5
Joined: Fri Mar 28, 2008 12:30 am UTC

Re: Exponents using only addition and subtraction

Postby Porkrind » Fri Mar 28, 2008 8:21 pm UTC

Seraph wrote:A few questions:

How big/small is "x" and what sort of accuracy (how many significant figures) do you need for your result? Can "x-69" be negative?

Why can't use use the other instructions in the Z80?
As your always multiplying by powers of two the bitwise shift command, and the ability to grab one bit from a register, would be extreamly useful in this problem. I know the Z80 has the former, does it have the latter?



Sorry, I wasn't making myself clear earlier. 0<=x<=127 so it will be negative at times. As for sig figs, what is the human hearing threshold? Like .1? .01 at most.And I can use almost any other function the z80 has. I was just trying to say, "I need to do this w/o multiplication and division." After a lot of thought and writing out some of the code needed for this, I realized it would be a lot simpler to calculate the values at assembly time (Where I have */^) and store them in a table. Time really is the problem. This is going to end up being a Gameboy MIDI player and the timing must be (near) perfect.

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: Exponents using only addition and subtraction

Postby Nitrodon » Fri Mar 28, 2008 9:19 pm UTC

The most efficient method would probably use a table which gives f(x) for 12 different values of x, then use bit shifts to calculate f(x) for any other value of x.

User avatar
hobo386
Posts: 26
Joined: Thu Oct 18, 2007 12:03 am UTC

Re: Exponents using only addition and subtraction

Postby hobo386 » Mon Apr 07, 2008 2:13 am UTC

For integers...
x^2
1 4 9 16 25 36
3 5 7 9 11
2 2 2 2

x^3
1 8 27 64
7 19 37
12 18
6
x^4
.....
....
...
..
24
etc

This is probably useless to you, but fun nonetheless.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 6 guests