Ideal method of multiplying mixed fractional number to prevent overflow?

I have a simple class that contains three unsigned integer fields: a whole value, a numerator, and a denominator, representing a mixed number of the form:

<Whole> <Num>/<Den>  // e.g. 3 1/2

I'd like to be able to multiply instances of these classes with each other, but since my main app uses relatively large numbers, I'm concerned about overflow. Is there an algorithm for performing this kind of multiplication that minimizes the potential for multiplication overflow?

I'm OK with having overflow if it's unavoidable, what I'm looking for is for a way to "intelligently" multiply to av开发者_运维技巧oid having overflow if it's possible.

I'm not sure if you actually needed info on multiplying mixed numbers... but this site explains how to do it fairly simply: Multiplying Mixed Numbers.

At any rate... the data structure you've created has inherited the limitations of its parts. That is to say, even if you were just working with rounded up unsigned ints, you were still going to end up with the potential for overflow. If you're worried about blowing out your unsigned int then you should consider bumping the type you're using up to something that can handle larger numbers.

Wikipedia has a pretty good summary on Arithmetic Overflow and some ideas for handling it: Arithmetic Overflow

Calculating the least-common-multiple (LCM) of the two denominators can help to keep the numbers small. There is a lot of info on wikipedia, have a look at the "Reduction by greatest common divisor" section of http://en.wikipedia.org/wiki/Least_common_multiple and the "Implementations" section of http://en.wikipedia.org/wiki/Euclidean_algorithm.

There is a way of doing it without resorting to arbitrary presision arithmetics as well. Unless you are coding in assembly, it's more of a curiosity rather than a useful algorithm, but it may be worth mentioning.

    int dividend = 0;
    int result = 0;
    int remainder = 0;

    while( num != 0 ) {
        boolean bit = <take the topmost bit of num>
        dividend = remainder << 1;
        if( bit ) {
          dividend += whole;
        }
        int quotient = dividend / div;
        result = (result << 1) + quotient;
        remainder = dividend % div;
        num = num << 1;
    }
    result <<= 1;
    result += ( remainder << 1 ) / div; 

I know the loop is clumsy but my mind's gone blank and I can't rephrase it so that everything fits neatly into it, but you should get the general idea, which is basically perform the multiplication bit by bit while you're doing the division.