Floating point division alternatives?

Go To Last Post
11 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hi,

If I need to convert a value in centimeteres to kilometers, normaly I would divide by 100000. With the division mathamatics being so hard on the cpu, is there any benefit to multiplying by 0.00001 to convert the values? Or will this also be a huge function for the CPU to process?

Also, the end result will be converted to a string, would it be easier to just manipulate the string to pad out the value to the nearest whole unit (KM) and add a decimal point to the string?

Thanks

Richard

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Why not just do all internal calculations in centimeters (millimeters even?) and then just do the divide by 10^N when you finally need to display the result to the end user? In fact if you used BCD maths it'd just be a case of shifting the position of the decimal point for final display. Say you used "long long"s, that's 64 bits, with a decimal digit per nibble that'd be 16 digits allowing you to represent up to 1,000,000,000,000,000 mm which is 1,000,000,000,000 meters or 1,000,000,000 kilometers.

In fact you might not even need 64 bits and could do it in 32 with eight BCD digits allowing for 10,000,000 mm's or 10,000 meters or 10km.

It'd lkind of depend what the max km range is but maybe you don't need mm accuracy and could do it with cm accuracy in which case that would be 100km (and so on)

Course, if you used binary rather than BCD you could get a greater range int o32/64 bits but then you'd face a lot of /10 and *10

Cliff

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I have timed the fp mult and the fp divide... the mult uses the hw 8 bit mult instruction several times to mult the fp multiplicands.. fp mult is twice as fast as fp div... so mult by .1 is better than /10.0. All integer is more of a speed win, but more brain work on the programmer.

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

If one goes for the floating point route it should be noted that 0.1 cannot be accurately represented in binary in the same way that 1/3 cannot be accurately represented in decimal fractions. Both lead to a recurring fraction. This is why (17 * 0.1) * 10 will often not be equal to 17 but 16.9999995231 or 17.0000001271 or whatever.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I am trying to keep the number of floating point operations to an absoloute minimum, so as much of what I can do will be performed on integers.

Maximum KM will probably be 4 digits (9999.999KM) but I am still in the learning portion of all of this, so its not set in stone yet.

Is the FP multiply likely to be faster then me hacking away at converting to a string and adding 0's and the decimal point?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

But surely the only time when you need the values in a human readable form is just at the last minute before you display to an LCD or terminal or something? Presumably you don't intend updating that more than once every 100ms or something? So you have TONS of time to do output number conversions for the human. The key thing is to hold the values internally in some quick to calculate format wherever it's used in some timing critical part of the application.

Cliff

PS But if you are looking at 9999.999Km then that's only accurate to 1 meter and there's no centimeters involved - you could easily hold that kind of value in a 32bit BCD number. In fact you could go to 9999.9999Km and at least be decimeter accurate.

Last Edited: Wed. Aug 29, 2007 - 05:41 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Which is faster doesnt matter until you run out of cpu time. If you have enough cpu to run the program 5 times a sec, who cares if you can speed it up to 10 times a sec? The design criteria might be: get done as quick as possible (boss doesnt like to cut checks to programmers), super reliable, easy to maintain (he's planning to can you and hire someone cheaper to take over), or runs as fast as possible for this price point of hardware. All these goals interact in certain ways. I try to get things working fast and simple, then refine from there. fp is easy on the programmer, but after a while a 16k or 32k flash just fills up and you need to start pulling tricks out of your bag.

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Well, the internal accuracy will probably be in CM, but displayed to the user in M. One of the other functions the cpu will be doing is monitoring a sensor and counting pulses, then converting the pulse count to a distance. At a speed of 72KM/H which is common, aprox 30 pulses per second will be counted.

I know it probably wont be an issue, but I am trying to solve problems ahead of time so I dont have to alter my design too many times as the range of functionality expands. At the moment my goal is to build an accurate, easy to calibrate odometer and speedometer.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

If you count the vehicle speed sensor pulses with an edge triggered interrupt, lets say it takes 4usec to interrupt the avr, push 31 registers, increment the pulse count pull 31 registers and return. 4usec out of 30,000... .01% of the cpu used for this task. 30ms is plenty enough time to compute speed and distance, update the timer oneshots, and update the display about 10 times a sec (3 passes). I think cpu time is not the short pole in this tent. What about having a sensor on each rear wheel, and keep track of the mileage for each wheel separately? How many miles off you think they'd be after 20,000 miles average? 2 miles? 20 miles? 200 miles? (Have a lot of one way streets in your town? Lots of left turns?) Never mind. Silly idea. Just brain storming.

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Actualy, I have thought of that, maintaining counts for each wheel, dropping any that are beyond a median range for a given time period (ie: wheel spin or while slide), as well eventualy there will be functions for timing as per a stopwatch, and average speeds and what not...

but at the moment, I'm keeping it simple so that I can complete the project and once its done, start adding the other things to it.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I made a fuel computer for my car once which has a speed sensor that sends 8000 pulses per mile (a quite standard value). I didn't use floating point for my calculations but did everything with integer math.

Unfortunately, with int math, intermediate results can be very large if you want to maintain any precision and range. So I ended up writing an arbitrary precision math library (add,sub,mul,div,compare; a mix of asm and C) as I needed 56 bits for intermediate results. With fixed point math you have to watch out for overflows.

I used the input capture function of a 16 timer to measure speed and count distance traveled, so I need only one ISR to handle both.

To calculate average economy the equation is economy=distance/fuel_used. Both distance and fuel quickly become big numbers as I just accumulate counts and don't convert to some real engineering unit on each pulse received; this can lead to an accumulation of errors; 1 pulse of the speed sensor is 1.666666666667 meters.

For display purpose I convert to 0.1 units, so a value of 15 is displayed as 1.5. The equation then becomes economy=(distance*10*PPL)/(fuel*PPK) where PPL is pulses per litre (12636) and PPK is pulses per kilometer (6000). You need to multiply before dividing when using integers to maintain precision.
Both distance and fuel are 40 bits values, as I wanted to cover 1 million kilometers and that needs 33 bits :D I could have limited it to 500.000km but the intermediate results still would require more bits, so a long integer wouldn't have sufficed anyway.

These 40 and 56 bit calculations do take some time indeed :) but for display purposes it really doesn't matter.

When the equation is calculated I still need to convert from binary to decimal, this is just repeatedly dividing by 10 and modulus 10.