It looks like you're new here. If you want to get involved, click one of these buttons!

- 140.7K All Categories
- 103.5K Programming Languages
- 6.5K Assembler Developer
- 1.9K Basic
- 39.9K C and C++
- 2.9K C#
- 7.9K Delphi and Kylix
- 4 Haskell
- 9.7K Java
- 4.1K Pascal
- 1.3K Perl
- 2K PHP
- 538 Python
- 37 Ruby
- 4.4K VB.NET
- 1.6K VBA
- 20.8K Visual Basic
- 2.6K Game programming
- 315 Console programming
- 90 DirectX Game dev
- 1 Minecraft
- 110 Newbie Game Programmers
- 2 Oculus Rift
- 9K Applications
- 1.8K Computer Graphics
- 738 Computer Hardware
- 3.4K Database & SQL
- 535 Electronics development
- 1.6K Matlab
- 628 Sound & Music
- 257 XML Development
- 3.3K Classifieds
- 198 Co-operative Projects
- 196 For sale
- 190 FreeLance Software City
- 1.9K Jobs Available
- 602 Jobs Wanted
- 207 Wanted
- 2.9K Microsoft .NET
- 1.8K ASP.NET
- 1.1K .NET General
- 3.4K Miscellaneous
- 8 Join the Team
- 354 Comments on this site
- 69 Computer Emulators
- 2.1K General programming
- 187 New programming languages
- 621 Off topic board
- 186 Mobile & Wireless
- 60 Android
- 124 Palm Pilot
- 338 Multimedia
- 154 Demo programming
- 184 MP3 programming
- 0 Bash scripts
- 23 Cloud Computing
- 53 FreeBSD
- 1.7K LINUX programming
- 370 MS-DOS
- 0 Shell scripting
- 321 Windows CE & Pocket PC
- 4.1K Windows programming
- 930 Software Development
- 416 Algorithms
- 68 Object Orientation
- 90 Project Management
- 93 Quality & Testing
- 262 Security
- 7.6K WEB-Development
- 1.8K Active Server Pages
- 61 AJAX
- 2 Bootstrap Themes
- 55 CGI Development
- 28 ColdFusion
- 224 Flash development
- 1.4K HTML & WEB-Design
- 1.4K Internet Development
- 2.2K JavaScript
- 35 JQuery
- 298 WEB Servers
- 145 WEB-Services / SOAP

peret
Member Posts: **69**

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.

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.

Terms of use / Privacy statement / Publisher: Lars Hagelin

Programmers Heaven articles / Programmers Heaven files / Programmers Heaven uploaded content / Programmers Heaven C Sharp ebook / Operated by CommunityHeaven

© 1997-2015 Programmersheaven.com - All rights reserved.

## Comments

198:

: 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?

69: 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?

:

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

[code]V = (1000*(arcsin(d)+d.sqrt(1-d^2))+1570) liters

where

d = ((depth sensor reading)-2048)/2048[/code]

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.

[hr]

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,

[code](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)[/code]

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

[code](liquid volume) = (constant K) * (area of D)[/code]

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:

[code](X/R)^2 + (Y/R)^2 = 1[/code]

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

[code]X^2 + Y^2 = 1

or

Y = sqrt(1-X^2)[/code]

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

[code]A = integral{sqrt(1-X^2) dX}

between the limits {X=-1,X=d}[/code]

(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

[code]X=sin(Q)[/code]

where Q is in Radians.

Now

[code]sin^2(Q) + cos^2(Q) = 1[/code]

so

[code]sqrt(1-sin^2(Q)) = cos(Q)[/code]

And the formula becomes

[code]A = integral{cos(Q) dX}[/code]

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

Since

[code]X = sin(Q)[/code]

then

[code]dQ/dX = cos(Q)[/code]

So

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

Therefore the final formula is

[code]A = integral{cos^2(Q) dQ}[/code]

Now

[code]cos^2(Q) = (1+cos(2Q))/2 = 1/2 + 1/2.(cos(2Q))[/code]

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

[code]integral{1/2 dQ} = Q/2[/code]

and

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

= 1/2.sin(Q).cos(Q)[/code]

So

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

and reversing the substitution to get back into X,

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

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:

[code] 1/2.(-pi + -1.(1-1))

= -pi/2[/code]

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,

[code]X = (d-radius)/radius

= (d-1)[/code]

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:

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

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

[code]d = ((sensor output) - 2048)/2048[/code]

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

So

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

= K*pi/2[/code]

so [b]K = 1000[/b]

Checking,

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

So

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

= K*(pi/2 + pi/2)[/code]

Confirmed, [b]K = 1000[/b]

Hence our full formula is this:

[code]Volume = 1000*(arcsin(d) + d.sqrt(1-d^2)) + 1570

where

d = ((sensor reading)-2048)/2048[/code]

198I'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:

: [code]V = (1000*(arcsin(d)+d.sqrt(1-d^2))+1570) liters

: where

: d = ((depth sensor reading)-2048)/2048[/code]

:

: 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.

: [hr]

: 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,

: [code](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)[/code]

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

: [code](liquid volume) = (constant K) * (area of D)[/code]

: 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:

: [code](X/R)^2 + (Y/R)^2 = 1[/code]

: 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

: [code]X^2 + Y^2 = 1

: or

: Y = sqrt(1-X^2)[/code]

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

: [code]A = integral{sqrt(1-X^2) dX}

: between the limits {X=-1,X=d}[/code]

: (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

: [code]X=sin(Q)[/code]

: where Q is in Radians.

: Now

: [code]sin^2(Q) + cos^2(Q) = 1[/code]

: so

: [code]sqrt(1-sin^2(Q)) = cos(Q)[/code]

: And the formula becomes

: [code]A = integral{cos(Q) dX}[/code]

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

: Since

: [code]X = sin(Q)[/code]

: then

: [code]dQ/dX = cos(Q)[/code]

: So

: [code]A = integral{cos(Q) dQ/dX.dX}[/code]

: Therefore the final formula is

: [code]A = integral{cos^2(Q) dQ}[/code]

: Now

: [code]cos^2(Q) = (1+cos(2Q))/2 = 1/2 + 1/2.(cos(2Q))[/code]

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

: [code]integral{1/2 dQ} = Q/2[/code]

: and

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

: = 1/2.sin(Q).cos(Q)[/code]

: So

: [code]A = 1/2.(Q + sin(Q).cos(Q))[/code]

: and reversing the substitution to get back into X,

: [code]A = 1/2.(arcsin(X) + X.sqrt(1-X^2))[/code]

: 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:

: [code] 1/2.(-pi + -1.(1-1))

: = -pi/2[/code]

: 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,

: [code]X = (d-radius)/radius

: = (d-1)[/code]

: 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:

: [code]A = 1/2.(arcsin(d-1)+(d-1).sqrt(1-(d-1)^2))-(pi/2)[/code]

: 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

: [code]d = ((sensor output) - 2048)/2048[/code]

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

: So

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

: = K*pi/2[/code]

: so [b]K = 1000[/b]

:

: Checking,

: Liquid volume when full (sensor reads 4096) is (pi)*1000 liters.

: So

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

: = K*(pi/2 + pi/2)[/code]

: Confirmed, [b]K = 1000[/b]

:

: Hence our full formula is this:

: [code]Volume = 1000*(arcsin(d) + d.sqrt(1-d^2)) + 1570

: where

: d = ((sensor reading)-2048)/2048[/code]

:

:

69Using 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

[code]R^2(Q - sin(Q).cos(Q))[/code]

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

[code]cos(Q) = (R-d)/R[/code]

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:

[code]R^2(arccos(X) - X.sqrt(1-X^2))[/code]

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.

198I 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

: [code]R^2(Q - sin(Q).cos(Q))[/code]

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

: [code]cos(Q) = (R-d)/R[/code]

: 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:

: [code]R^2(arccos(X) - X.sqrt(1-X^2))[/code]

: 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.

:

:

69: 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.

198: : 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.

1case < 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.

:

69Working 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!