As a relief from all the "please do my homework" messages, let's see who really knows their axe from their eblow around here.

Consider a cylindrical tank, 1 meter in diameter and 4 meters long, laid horizontally on its side. The area of the circular end is pi/4 square meters, so the capacity is pi cubic meters or about 3140 liters.

There is a sensor in the tank to measure the depth of the liquid. It has a 12-bit digital output, giving a range from 0 (0 meters deep) to 4095 (1 meter deep).

Using this depth number as input, devise an equation to calculate the volume of liquid in the tank to an accuracy of +/- 1 liter. Hint: this requires knowledge of integration, and the equation is hideous.

Now write a program to do it, on the micro of your choice, in assembly language. Do this from first principles in 4096 bytes or less, WITHOUT using a floating point library, or any pre-written trig functions, or a lookup table.

If there's any interest in this problem, I'll explain my solution a bit later on, but take a shot at it first.

: As a relief from all the "please do my homework" messages, let's see who really knows their axe from their eblow around here.
:
: Consider a cylindrical tank, 1 meter in diameter and 4 meters long, laid horizontally on its side. The area of the circular end is pi/4 square meters, so the capacity is pi cubic meters or about 3140 liters.
:
: There is a sensor in the tank to measure the depth of the liquid. It has a 12-bit digital output, giving a range from 0 (0 meters deep) to 4095 (1 meter deep).
:
: Using this depth number as input, devise an equation to calculate the volume of liquid in the tank to an accuracy of +/- 1 liter. Hint: this requires knowledge of integration, and the equation is hideous.
:
: Now write a program to do it, on the micro of your choice, in assembly language. Do this from first principles in 4096 bytes or less, WITHOUT using a floating point library, or any pre-written trig functions, or a lookup table.
:
: If there's any interest in this problem, I'll explain my solution a bit later on, but take a shot at it first.
:
Ok... 68hc11's my controller of choice, as I know the language. Do I assume the input's already in memory, or do I have to fetch it too?

You can assume it's in memory. The interesting part of the exercise is evaluating the depth-to-volume function, which I'll post later today.

: Ok... 68hc11's my controller of choice, as I know the language. Do I assume the input's already in memory, or do I have to fetch it too?
:

As promised, here's the formula.

Taking pi=3.142, the volume of fluid in the tank when the depth reading is d is:

V = (1000*(arcsin(d)+d.sqrt(1-d^2))+1570) liters
where
d = ((depth sensor reading)-2048)/2048

Now you have to calculate an arcsin and a square root without a math package or a lookup table, and do it without rounding errors to 12 bits of resolution. Solution later.

For those wishing to follow the math, the full derivation is given below.

---

When the tank is partly filled, a certain D-shaped area of the end wall is covered by liquid. If we know this area, the area multiplied by the length of the tank gives us the volume of liquid.

To simplify the math a little, the D-shaped area could be considered a fraction of the total end area, pi.R^2.
So,

(area fraction) = (area D)/(pi.R^2)
and 
(liquid volume) = (tank volume) * (area fraction)
or
(liquid volume) = (tank volume) * (area of D)/(pi.R^2)

But (tank volume) is a constant, and so is (pi.R^2), so

(liquid volume) = (constant K) * (area of D)

This makes things easier, because we can take considerable liberties to simplify the expression for the area, and take care of it at the end by selecting the constant.

To find area, we have to integrate the equation for a circle between the edge and the liquid surface. The standard equation for a circle is:

(X/R)^2 + (Y/R)^2 = 1

If you plot this on graph paper you get a circle of radius R, centered on the origin. So it covers X values from -R to +R. The first simplification I'm going to make is to set R=1.
Now

X^2 + Y^2 = 1
or
Y = sqrt(1-X^2)

and the area to the liquid surface, say depth d, is

A = integral{sqrt(1-X^2) dX}
between the limits {X=-1,X=d}

(Actually that's only half the area, because sqrt(1-X^2) has two roots, one positive and one negative, and the circle is half above and half below the X axis. But we take care of the constant 2 later.)

This is an impossible integral as it stands, so make a substitution

X=sin(Q)

where Q is in Radians.
Now

sin^2(Q) + cos^2(Q) = 1

so

sqrt(1-sin^2(Q)) = cos(Q)

And the formula becomes

A = integral{cos(Q) dX}

But we can't integrate Q by dX, so we have to multiply by dQ/dX
Since

X = sin(Q)

then

dQ/dX = cos(Q)

So

A = integral{cos(Q) dQ/dX.dX}

Therefore the final formula is

A = integral{cos^2(Q) dQ}

Now

cos^2(Q) = (1+cos(2Q))/2 = 1/2 + 1/2.(cos(2Q))

You can integrate this one term at a time, thus:

integral{1/2 dQ} = Q/2

and

integral{1/2(cos(2Q)) dQ} = 1/2.1/2.sin(2Q)
                          = 1/2.sin(Q).cos(Q)

So

A = 1/2.(Q + sin(Q).cos(Q))

and reversing the substitution to get back into X,

A = 1/2.(arcsin(X) + X.sqrt(1-X^2))

To get a definite integral, or the area between two points, we evaluate the function at each point and subtract one from the other. In this case we evaluate at some variable point X, and subtract the (constant) value when the tank is empty at X=-1.

The value when X=-1 is:

    1/2.(-pi + -1.(1-1))
  = -pi/2

Next thing is to express X in terms of d, the depth of fluid.

Because at the start we decided to find A as a fraction (0..1) of the total area, we want X as a fraction of the total diameter. Further, because our original circle formula is centered on the origin, we want X to vary between -1 and +1. Further, we arbitrarily declared that the radius of the tank is 1, so the diameter is 2 * radius, or 2.

So if our depth reading is d,

X = (d-radius)/radius
  = (d-1)

and as d varies from 0..1 diameters, or 0..2 radii,
when d=0, X=-1
when d=2, X=+1

Therefore the D-shaped area covered at depth d is:

A = 1/2.(arcsin(d-1)+(d-1).sqrt(1-(d-1)^2))-(pi/2)

What we actually want is the total volume, so let's work out that
constant K I mentioned at the beginning and put in some real numbers.

Total tank volume is pi cubic meters, or pi*1000 liters.
Output from sensor is in range (0..4095)
So

d = ((sensor output) - 2048)/2048

Liquid volume when half full (sensor reads 2048) is (pi/2)*1000 liters.
So

(pi/2)*1000 = K*(arcsin(0)+(0).sqrt(1)-(-pi/2))
            = K*pi/2

so K = 1000

Checking,
Liquid volume when full (sensor reads 4096) is (pi)*1000 liters.
So

(pi)*1000 = K*(arcsin(1)+(1).sqrt(0)-(-pi/2))
          = K*(pi/2 + pi/2)

Confirmed, K = 1000

Hence our full formula is this:

Volume = 1000*(arcsin(d) + d.sqrt(1-d^2)) + 1570
where
d = ((sensor reading)-2048)/2048

There is no need for integrals, if you think about it a little, although it may be faster with them.

I'll write out a breif explination of how I'd do this, as I haven't had time to work it out completely yet:

Modify an equation for a circle such that the bottom of the circle is tangent to x=0. The x values are equal to height of the liquid, which is the same as depth. Knowing depth allows one to find the Y values that the circle crosses at the given depth. Once this is accomplished, it is possible to find the angle of the arc from the center point of the cylinder. Finding this area is now quite simple, as it's simply a fraction of a circle. If the Y values are greater than half the depth, simply subtract half the depth and add half the volume of the cylinder to the end result. Once you have the area of the arc of the circle, subtract the area of the triangle to the top of the water. This also isn't hard to find, as you know the width and height of the triangle. Now, multiply by the length of the cylinder to find the volume.

Code and equations will come later if there is a desire to see them.

: As promised, here's the formula.
:
: Taking pi=3.142, the volume of fluid in the tank when the depth reading is d is:
:

V = (1000*(arcsin(d)+d.sqrt(1-d^2))+1570) liters
: where
: d = ((depth sensor reading)-2048)/2048

:
: Now you have to calculate an arcsin and a square root without a math package or a lookup table, and do it without rounding errors to 12 bits of resolution. Solution later.
:
: For those wishing to follow the math, the full derivation is given below.
:

---

: When the tank is partly filled, a certain D-shaped area of the end wall is covered by liquid. If we know this area, the area multiplied by the length of the tank gives us the volume of liquid.
:
: To simplify the math a little, the D-shaped area could be considered a fraction of the total end area, pi.R^2.
: So,
:

(area fraction) = (area D)/(pi.R^2)
: and 
: (liquid volume) = (tank volume) * (area fraction)
: or
: (liquid volume) = (tank volume) * (area of D)/(pi.R^2)

: But (tank volume) is a constant, and so is (pi.R^2), so
:

(liquid volume) = (constant K) * (area of D)

: This makes things easier, because we can take considerable liberties to simplify the expression for the area, and take care of it at the end by selecting the constant.
:
: To find area, we have to integrate the equation for a circle between the edge and the liquid surface. The standard equation for a circle is:
:

(X/R)^2 + (Y/R)^2 = 1

: If you plot this on graph paper you get a circle of radius R, centered on the origin. So it covers X values from -R to +R. The first simplification I'm going to make is to set R=1.
: Now
:

X^2 + Y^2 = 1
: or
: Y = sqrt(1-X^2)

: and the area to the liquid surface, say depth d, is
:

A = integral{sqrt(1-X^2) dX}
: between the limits {X=-1,X=d}

: (Actually that's only half the area, because sqrt(1-X^2) has two roots, one positive and one negative, and the circle is half above and half below the X axis. But we take care of the constant 2 later.)
:
: This is an impossible integral as it stands, so make a substitution
:

X=sin(Q)

: where Q is in Radians.
: Now
:

sin^2(Q) + cos^2(Q) = 1

: so
:

sqrt(1-sin^2(Q)) = cos(Q)

: And the formula becomes
:

A = integral{cos(Q) dX}

: But we can't integrate Q by dX, so we have to multiply by dQ/dX
: Since
:

X = sin(Q)

: then
:

dQ/dX = cos(Q)

: So
:

A = integral{cos(Q) dQ/dX.dX}

: Therefore the final formula is
:

A = integral{cos^2(Q) dQ}

: Now
:

cos^2(Q) = (1+cos(2Q))/2 = 1/2 + 1/2.(cos(2Q))

: You can integrate this one term at a time, thus:
:

integral{1/2 dQ} = Q/2

: and
:

integral{1/2(cos(2Q)) dQ} = 1/2.1/2.sin(2Q)
:                           = 1/2.sin(Q).cos(Q)

: So
:

A = 1/2.(Q + sin(Q).cos(Q))

: and reversing the substitution to get back into X,
:

A = 1/2.(arcsin(X) + X.sqrt(1-X^2))

: To get a definite integral, or the area between two points, we evaluate the function at each point and subtract one from the other. In this case we evaluate at some variable point X, and subtract the (constant) value when the tank is empty at X=-1.
:
: The value when X=-1 is:
:

    1/2.(-pi + -1.(1-1))
:   = -pi/2

: Next thing is to express X in terms of d, the depth of fluid.
:
: Because at the start we decided to find A as a fraction (0..1) of the total area, we want X as a fraction of the total diameter. Further, because our original circle formula is centered on the origin, we want X to vary between -1 and +1. Further, we arbitrarily declared that the radius of the tank is 1, so the diameter is 2 * radius, or 2.
:
: So if our depth reading is d,
:

X = (d-radius)/radius
:   = (d-1)

: and as d varies from 0..1 diameters, or 0..2 radii,
: when d=0, X=-1
: when d=2, X=+1
:
: Therefore the D-shaped area covered at depth d is:
:

A = 1/2.(arcsin(d-1)+(d-1).sqrt(1-(d-1)^2))-(pi/2)

: What we actually want is the total volume, so let's work out that
: constant K I mentioned at the beginning and put in some real numbers.
:
: Total tank volume is pi cubic meters, or pi*1000 liters.
: Output from sensor is in range (0..4095)
: So
:

d = ((sensor output) - 2048)/2048

: Liquid volume when half full (sensor reads 2048) is (pi/2)*1000 liters.
: So
:

(pi/2)*1000 = K*(arcsin(0)+(0).sqrt(1)-(-pi/2))
:             = K*pi/2

: so K = 1000
:
: Checking,
: Liquid volume when full (sensor reads 4096) is (pi)*1000 liters.
: So
:

(pi)*1000 = K*(arcsin(1)+(1).sqrt(0)-(-pi/2))
:           = K*(pi/2 + pi/2)

: Confirmed, K = 1000
:
: Hence our full formula is this:
:

Volume = 1000*(arcsin(d) + d.sqrt(1-d^2)) + 1570
: where
: d = ((sensor reading)-2048)/2048

:
:

That's a very interesting method - I wish I'd thought of it! The first time I did the integral it took me three days, and I got it wrong.

Using your method on a circle radius R (times 2 understood)

The area of the segment at angle Q rads is
pi.R^2.Q/pi (for Q=0..pi)

The area of the triangle is
R.sin(Q).R.cos(Q) (for Q=0..pi)

So the area of the chord is

R^2(Q - sin(Q).cos(Q))

If the depth (from X=0) is D, then

cos(Q) = (R-d)/R

and if you substitute X=cos(Q), and sin^2 = root(1-cos^2), you get something that looks awfully similar to the integration result:

R^2(arccos(X) - X.sqrt(1-X^2))

I plotted this (in Excel) and got the right curve, but mirrored and offset. Subtracting the expression from pi/2 made it fit. I guess that means if you did the math assuming Q=0 is straight up vertical and the range is Q=(-pi/2..+pi/2), you'd get the same result as the integration. Nice job.


: There is no need for integrals, if you think about it a little, although it may be faster with them.

Still, that leaves the problem of floating point with sine, cosine, and sqrt without a math library.
I took a quick glance at it when you posted your solution and replied the next day. Granted, I didn't work it all out, it just seemed like overkill, but that's not uncommon for me. I've found that most things can be done much simpler than most people assume, with just a little thought.
A prime example I've seen is, someone wanting to use a microcontroller to output a voltage based on an input from an rs232 cable, where a simple r2r ladder works wonders and is faster. I've also seen them used for outputting fixed frequncies, also quite a bit of overkill.

: That's a very interesting method - I wish I'd thought of it! The first time I did the integral it took me three days, and I got it wrong.
:
: Using your method on a circle radius R (times 2 understood)
:
: The area of the segment at angle Q rads is
: pi.R^2.Q/pi (for Q=0..pi)
:
: The area of the triangle is
: R.sin(Q).R.cos(Q) (for Q=0..pi)
:
: So the area of the chord is
:

R^2(Q - sin(Q).cos(Q))

: If the depth (from X=0) is D, then
:

cos(Q) = (R-d)/R

: and if you substitute X=cos(Q), and sin^2 = root(1-cos^2), you get something that looks awfully similar to the integration result:
:

R^2(arccos(X) - X.sqrt(1-X^2))

: I plotted this (in Excel) and got the right curve, but mirrored and offset. Subtracting the expression from pi/2 made it fit. I guess that means if you did the math assuming Q=0 is straight up vertical and the range is Q=(-pi/2..+pi/2), you'd get the same result as the integration. Nice job.
:
:
: : There is no need for integrals, if you think about it a little, although it may be faster with them.
:
:

: Still, that leaves the problem of floating point with sine, cosine, and sqrt without a math library.
: I took a quick glance at it when you posted your solution and replied the next day. Granted, I didn't work it all out, it just seemed like overkill, but that's not uncommon for me. I've found that most things can be done much simpler than most people assume, with just a little thought.

Absolutely - and that applies to the trig functions too. You don't need FP to solve this equation. All you need is two simple numerical routines, a square root finder and a Mclaurin series for Arcsin, both of which you can do with integer arithmetic. I'll post my solution later this week.

: : Still, that leaves the problem of floating point with sine, cosine, and sqrt without a math library.
: : I took a quick glance at it when you posted your solution and replied the next day. Granted, I didn't work it all out, it just seemed like overkill, but that's not uncommon for me. I've found that most things can be done much simpler than most people assume, with just a little thought.
:
: Absolutely - and that applies to the trig functions too. You don't need FP to solve this equation. All you need is two simple numerical routines, a square root finder and a Mclaurin series for Arcsin, both of which you can do with integer arithmetic. I'll post my solution later this week.
:
I've actually been trying to find an equation for sine, cosine, and tangent to make things nice and simple. Unfortunately, I had to stop, as I tended to do it during calculus.

In the program, you need three cases for d:
case < 0.5 then volume is calculated as mentioned,let v1
case = 0.5 then vl=V/2 (vl:liquid volume)
case >0.5 then vl=V-v1
It could be formed in a unique equation:
Vl=k*V+(-1)^s*v1 (v1 calculated in first case), with k=f(d),s=g(d), but I still can't find them!
Nice problem though, kept me thinking!

: : : Still, that leaves the problem of floating point with sine, cosine, and sqrt without a math library.
: : : I took a quick glance at it when you posted your solution and replied the next day. Granted, I didn't work it all out, it just seemed like overkill, but that's not uncommon for me. I've found that most things can be done much simpler than most people assume, with just a little thought.
: :
: : Absolutely - and that applies to the trig functions too. You don't need FP to solve this equation. All you need is two simple numerical routines, a square root finder and a Mclaurin series for Arcsin, both of which you can do with integer arithmetic. I'll post my solution later this week.
: :
: I've actually been trying to find an equation for sine, cosine, and tangent to make things nice and simple. Unfortunately, I had to stop, as I tended to do it during calculus.
:

Ah, nice to see someone still thinking about this. I never did post my final solution but as I mentioned, it used a McLaurin series for arcsin and a Newton's Method square root.

Working to 12 bit accuracy, I precalculated the first few McLaurin constants, and then it's just a matter of squaring the arcsin and multiplying/dividing by the next constants until the result is negligible, and adding the results. It needed some care in the multiply and divide to avoid overflowing and losing accuracy. I found the series converged after three terms, provided I kept the range to X <= root(1/2), the point where sin(pi/4)=cos(pi/4). I covered the range {root(1/2) < X <= 1.0} by calculating X1 = root(X^2 - 1/2) - this is of course sin(pi/4-X) - calculating arcsin(X1) and subtracting the result from pi/4, another precalculated constant. It all came out in about half a k of Z80 code.

: In the program, you need three cases for d:
: case < 0.5 then volume is calculated as mentioned,let v1
: case = 0.5 then vl=V/2 (vl:liquid volume)
: case >0.5 then vl=V-v1
: It could be formed in a unique equation:
: Vl=k*V+(-1)^s*v1 (v1 calculated in first case), with k=f(d),s=g(d), but I still can't find them!
: Nice problem though, kept me thinking!