Linear interpolation

How can I do this with PIC 18F and ASM? I'm drawing a complete blank.
All values will be integers:

Y = Y1 + ((Y2 - Y1)/(X2 - X1)) * (X - X1)

Eclipsed said:

How can I do this with PIC 18F and ASM? I'm drawing a complete blank.
All values will be integers:

Y = Y1 + ((Y2 - Y1)/(X2 - X1)) * (X - X1)

Click to expand...

There might be some 'clever' way to do it, but the obvious way is to use maths routines and calculate it.

What sort of precision do you require?, there are various maths routines available on the PICList - or there are 32 bit maths routines available on the EPE website, look for the source code for the LCF Meter, which includes the 32 bit maths routines.

Actually I was hoping one of you had a clever way, thanks for the help.

BTW X is 16 bit and Y is 8 bit

Your question is too general to produce a specific answer. There are some special cases which allow you to solve the equation with easier algorithms.
For example, if the value of ((Y2 - Y1)/(X2 - X1)) does not change at runtime then it can be precalculated during compile/assembly to reduce the amount of calculation.

Also, it is much easier for the PIC18 to multiply two numbers rather than to divide. You can precalculate the reciprocal of that number at compile time and use it a multiplier. If it is less than 1, you can multiply the constant by 256 or even 65536 to get a multiplier that is greater than 1 and just divide the product by 256 or 65536 by dropping a bye or two from the product.

I think this is more like a data analysis and mathematics question.
Mathematicians have developed some algorithm to implement interpolation with less calculation iteration.
These methods reduce the computing time a lot, even on PC

Are you trying to render a line? If so, take a look at the Bresenham Line Algorithm.

Dan East

Its actually a 64 point map lookup.(Y2 - Y1) and (X2 - X1) are not constants, and will change throughout the program.

The way your equation is written it will require floating point math. If you change your equation to this:

Y = Y1 + ((Y2 - Y1)*(X - X1))/(X2 - X1)

You will get the same results, but you can implement it with integer math thus avoiding floating point arithmetic.

If the difference between X2 and X1 can always be 2^n (2 to the n power), then you can simply shift right to perform the division. Same with Y2-Y1, just shift left to multiply.

Does X1, X2, Y1, Y2 represent a viewport into the map to which the Y and X values are relative? For example if you have zoomed in on the map.

Dan East

Exactly, first a search is performed to find approximate position on the map, then interpolation is used to find exact value between known points.