Беззнаковое деление с фиксированной точкой в ​​C

Мне нужен алгоритм для беззнакового деления с фиксированной точкой в ​​C. Я могу использовать не более 32-битных слов.

Я хочу минимизировать количество битов, необходимых для представления целой части, при этом имея возможность использовать числа в диапазоне [0..15]. Таким образом, очевидно, что минимальное количество бит - 4. Проблема в том, что алгоритм, который я придумал, работает только с использованием 5 бит. Поскольку он сравнивает остаток с делителем, а затем сдвигает остаток, пока он не станет больше делителя, если у делителя самый значимый бит 1, то алгоритм ничего не сделает, кроме сдвига остатка (он никогда не будет больше). Вот код:

int divu(int a, int b){
   int pt_int, r, pt_frac=0;
   int i;

   pt_int = ((unsigned) a/b) << BITS_FRAC;
   r = (unsigned) a%b;

   for (i=BITS_FRAC; i>=0; i--){
      if ((unsigned) r < b)
         r <<= 1;
      else{
         r -= b;
        pt_frac += 01 << i;
        r <<= 1;
      }
   }
   return pt_int + pt_frac;
}

Если у вас есть решение, но вы не хотите разбираться в коде, просто опубликуйте его. :)

Пример:

Мы хотим разделить 1,5 на 2, что дает 0,75. Предположим, мы используем 4 бита для целой части и 28 бит для дроби. Итак, наши числа в шестнадцатеричном формате:

1.5:    0x18000000
2:      0x20000000
result: 0x0c000000

c division fixed-point
person Kei Nivky    schedule 14.12.2011    source источник
comment
Я не понимаю вопроса. Можете ли вы предоставить пример ввода, а также ожидаемый и фактический результат.   -  person Oliver Charlesworth    schedule 14.12.2011
comment
Если вы пытаетесь разделить значения без знака, по крайней мере, вы можете указать это в объявлении функции.   -  person unwind    schedule 14.12.2011
comment
Не похоже, что ваш код обрабатывает деление на ноль или переполнение. Например, если вы разделите 4 на 0,25, у вас возникнет проблема.   -  person Jonathan Leffler    schedule 14.12.2011
comment
@ Дэвид Хефферман: Да. Это домашнее задание. Но по крайней мере я пытаюсь это сделать.   -  person Kei Nivky    schedule 14.12.2011
comment
@unwind Извините за это. В приложении, которое я собираюсь использовать, это должно быть так, я просто вставил написанный мной код. Я его отредактирую.   -  person Kei Nivky    schedule 14.12.2011
comment
@Jonathan Leffler На самом деле, с кодом есть несколько проблем, но они не нуждаются в лечении. Их просто не будет в приложении.   -  person Kei Nivky    schedule 14.12.2011
comment
@JonathanLeffler Если ваш компилятор не предупреждает о неявном преобразовании типов из float в int, деление на ноль - наименьшая из ваших проблем ...   -  person Lundin    schedule 14.12.2011
comment
@KeiNivky Никакой критики. Я просто хотел знать, чтобы мы могли пометить вопрос соответствующим образом. Теперь мы теперь, как вам помочь.   -  person David Heffernan    schedule 14.12.2011

Ответы (2)


arrow_upward
2
arrow_downward

У вас есть число с фиксированной точкой 4,28, и вы хотите разделить его на число 4,28. Вы найдете точность после деления, вычтя точность числителя из знаменателя, поэтому прямое деление даст 4,28 - 4,28 = 0 - никаких значащих битов. Очевидно, это не сработает.

     1.5  [4.28] 0x18000000 
   / 2.0  [4.28] 0x20000000 
   =  0?  [0.00] 0x00000000

Идеальный способ сделать это - увеличить числитель до 8,56 (умножив на 2 ^ 28), а затем выполнить 64-битное деление:

                     .   .   .   .
     1.5  [8.56] 0x180000000000000
   / 2.0  [4.28]        0x20000000 
   = 0.75 [4.28]        0x0c000000

Если вы действительно не можете использовать 64-битные числа, ваш единственный выход - уменьшить знаменатель. Например, вы можете использовать половину точности, разделив на 2 ^ 14

     1.5  [4.28] 0x18000000 
   / 2.0  [2.14]     0x8000
   = 0.75 [2.14]     0x3000

Затем вы можете умножить результат на тот же коэффициент, чтобы вернуться к числу 4,28: 0x3000 *(1<<14) = 0x0c000000

Таким образом вы теряете некоторую точность, но это неизбежно без использования более крупных числителей. Например 5.0/3.0 = 1.66667 = 0x1AAAAAA [4.28], но
((5.0<<28)/(3<<14))<<14 = 0x1AAA8000 [4.28] = 1.66662

person AShelly    schedule 14.12.2011
comment
Думаю, лучше поступить по-своему. Цель не использовать 5 бит для целой части - избежать потери точности, потеря с вашим алгоритмом больше, чем мой 1 бит. - person Kei Nivky; 16.12.2011
comment
Ваш точнее, к тому же довольно медленный. Обычная мотивация для фиксированной точки - это скорость процессора с медленной математикой с плавающей запятой. Но если вам нужна точность, лучше всего подходит ваш метод. Я думаю, что потеря хотя бы одного бита неизбежна. - person AShelly; 17.12.2011

arrow_upward
1
arrow_downward

Как указано здесь (пример: умножение целого числа на обратное значение константа), вы можете повторно реализовать свое деление путем умножения на обратную. После этого вы сможете представить целую часть с помощью 4 бит.

person Sebastian Dressler    schedule 14.12.2011
comment
Ваша ссылка выполняет обратное и умножение с полной точностью? В этом случае это не сработает - ваш метод округляет «правильный» ответ вместо выполнения деления с фиксированной точкой. В целом оба метода дают разные результаты. - person EML; 10.05.2013