1

I'm implementing floating-point arithmetic, for a micro-controller which does not support floating point numbers, in either hardware or software. (Software being "written" in a sort of electrical diagram program.) I've finished encoding/decoding from/to integers, adding, subtracting, and multiplication. My "floats" are represented as C * 10^E, where:

  1. C, the coefficient, is a 32-bit signed integer in the range 100000000-999999999, or 0.
    • (Nine digits of precision, plus the special case of zero.)
  2. E, the exponent, is a 32-bit signed integer covering the whole 32-bit range.
    • (Yes, it's overkill.)

I chose round base-10 numbers to make the verification of the math easy. My strategy for the multiplication was to split up the two numbers AaaBbbCcc and DddEeeFff into three pieces each (millions, thousands, and ones) and compute the multiplication as

(ABC * 10^Y) * (DEF * 10^Z) =
  ((AD * 10^12) +
   ((AE + BD) * 10^9) +
   ((AF + BE + CD) * 10^6) +
   ((BF + CE) * 10^3) +
   (CF * 10^0))
  * 10^Y+Z

Each * and + representing a normal multiplication or addition, and 10^N being faked with me hard-coding in a 1000, 1000000, etc. Also note that this neither recurses or loops, and any answer cannot recurse or loop. I've got access to integer addition, subtraction, division, multiplication, modulo, cos/sin/tan/arccos/arcsin/arctan, absolute value, and square root.

Main Question:

I can/will eventually figure out how to do division with a similar approach of splitting the coefficients into smaller numbers which will be better for 32-bit division. I haven't done my algebra in a long time, so multiplication took me about a day and a half. Since I presume division to be more complicated conceptually, it would be super handy if somebody on SE could do the hard math for me. So, how do I do this?

Improve this question
5
  • You might find this useful: drdobbs.com/cpp/optimizing-math-intensive-applications-w/…
    – Robert Harvey
    Commented Apr 4, 2013 at 22:57
  • Your multiplication is a bit overkill. You're multiplying two 9-digit numbers, so the result will have 17 or 18 digits. You then want to reduce to 9 digits, so you're dropping 8 or 9 digits. Therefore you can safely drop the bottom 3 digits from each number before multiplying, and eliminate all of the terms containing C or F.
    – Peter Taylor
    Commented Apr 5, 2013 at 9:37
  • @PeterTaylor Actually, you can't drop them. The sums from the lower digits' multiplication can carry to the next higher digits, so you'll be introducing error. Plus, the hard part is working out the math. Actually setting up the function in the program is pretty straightforward.
    – E.T.
    Commented Apr 5, 2013 at 14:52
  • How do you do trig functions or square root without any floating point?
    – Brad
    Commented Apr 5, 2013 at 20:02
  • I don't. Those are all provided by the programming environment I work in. Presumably they either use integer approximations or lookup tables under the hood. The inputs are, for obvious reasons, scaled to non-fractional numbers, e.g. 0-10000 for input to cos(x).
    – E.T.
    Commented Apr 5, 2013 at 20:14

2 Answers 2

Reset to default
2

The Handbook of Floating-point Arithmetic, while rather expensive, is about as comprehensive a reference as you can get on the subject. It's designed with applicative uses in mind though it may be hard to parse the formal sections of math contained there-in. However, it will give a solution set for division in both hardware and software if you can parse the content which is not particularly mathy unless you delve into the proof sections of the book.

Wikipedia also lists a number of division algorithms, most of which are covered in mind-numbing detail in the above book. The article even links a Javascript simulator to test out various algorithms.

Improve this answer
1

Given the division: AAABBBCCC / X it can be rewritten to the form: (AAA * 10^6 / X) + (BBB * 10^3 / X) + (CCC / X).

These algebraic formulae, plus or minus some division or multiplication by powers of 10, will get the answer.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.