Идеальный метод умножения смешанного дробного числа для предотвращения переполнения? - PullRequest
Новая
       8

Идеальный метод умножения смешанного дробного числа для предотвращения переполнения?

1 голос
/ 29 января 2011

У меня есть простой класс, который содержит три беззнаковых целочисленных поля: целое значение, числитель и знаменатель, представляющие смешанное число в форме: 

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

Я бы хотел иметь возможность умножать экземпляры этих классов друг на друга, но, поскольку мое основное приложение использует относительно большие числа, меня беспокоит переполнение. Существует ли алгоритм для выполнения этого вида умножения, который сводит к минимуму вероятность переполнения умножения?

У меня все в порядке с переполнением, если оно неизбежно, я ищу способ «умного» умножения, чтобы избежать переполнения, если это возможно.

Ответы [ 3 ]

2 голосов
/ 29 января 2011

Я не уверен, нужна ли вам информация о умножении смешанных чисел ... но этот сайт объясняет, как сделать это довольно просто: Умножение смешанных чисел .

В любом случае... созданная вами структура данных унаследовала ограничения своих частей.То есть, даже если вы просто работали с округленными беззнаковыми целочисленными значениями, вы все равно могли столкнуться с возможностью переполнения.Если вы беспокоитесь о том, чтобы вытеснить свой неподписанный int, вам следует подумать о том, чтобы увеличить тип, который вы используете, до чего-то, что может обрабатывать большие числа.обработка: Арифметическое переполнение

1 голос
/ 29 января 2011

Вычисление наименьшего общего кратного (LCM) двух знаменателей может помочь сохранить малые числа.В википедии много информации, смотрите раздел «Сокращение по наибольшему общему делителю» http://en.wikipedia.org/wiki/Least_common_multiple и раздел «Реализации» http://en.wikipedia.org/wiki/Euclidean_algorithm.

0 голосов
/ 29 января 2011

Есть способ сделать это, не прибегая также к произвольной арифметике. Если вы не пишете код на ассемблере, это скорее любопытство, чем полезный алгоритм, но, возможно, стоит упомянуть. 

    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;

Я знаю, что цикл неуклюжий, но мой разум пуст, и я не могу перефразировать его так, чтобы все в него аккуратно вписалось, но вы должны понять общую идею, которая заключается в том, чтобы выполнять умножение по крупицам, пока вы делает разделение.

...