Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
    
You might find this useful: drdobbs.com/cpp/optimizing-math-intensive-applications-w/… –  Robert Harvey Apr 4 '13 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 Apr 5 '13 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. Apr 5 '13 at 14:52
    
How do you do trig functions or square root without any floating point? –  Brad Apr 5 '13 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. Apr 5 '13 at 20:14
add comment

2 Answers

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.

share|improve this answer
add comment
up vote 1 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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