Предполагая, что uint
является самым большим интегральным типом на моей платформе с фиксированной точкой, у меня есть:
uint func(uint a, uint b, uint c);
Что должно вернуть хорошее приближение a * b / c
.
Значение c
больше, чем значение a
и значение b
.
Итак, мы точно знаем, что значение a * b / c
поместится в uint
.
Однако само значение a * b
превышает размер uint
.
Таким образом, одним из способов вычисления значения a * b / c
будет:
return a / c * b;
Или даже:
if (a > b)
return a / c * b;
return b / c * a;
Однако значение c
больше, чем значение a
и значение b
.
Таким образом, приведенное выше предложение просто вернет ноль.
Мне нужно уменьшить a * b
и c
пропорционально, но опять же - проблема в том, что a * b
переполняется.
В идеале я мог бы:
- Замените
a * b
наuint(-1)
- Замените
c
наuint(-1) / a / b * c
.
Но как бы я ни заказывал выражение uint(-1) / a / b * c
, я сталкиваюсь с проблемой:
uint(-1) / a / b * c
усекается до нуля из-заuint(-1) / a / b
uint(-1) / a * c / b
переполняется из-заuint(-1) / a * c
uint(-1) * c / a / b
переполняется из-заuint(-1) * c
Как я могу решить этот сценарий, чтобы найти хорошее приближение a * b / c
?
Изменить 1
У меня нет таких вещей, как _umul128
на моей платформе, когда самый большой целочисленный тип — uint64
. Мой самый большой тип — uint
, и у меня нет поддержки чего-то большего (ни на аппаратном уровне, ни в какой-то уже существующей стандартной библиотеке).
Мой самый большой тип uint
.
Редактировать 2
В ответ на многочисленные повторяющиеся предложения и комментарии:
У меня нет под рукой какого-то более крупного шрифта, который я мог бы использовать для решения этой задачи. Вот почему вступительное утверждение вопроса:
Предполагая, что
uint
является самым большим интегральным типом на моей платформе с фиксированной точкой
Я предполагаю, что другого типа не существует ни на уровне ПО (через некоторую встроенную стандартную библиотеку), ни на уровне оборудования.
a
, либоb
должны быть больше половины размераuint
, поэтому, возможно, мне следует заменить большее из них, например,a
наuint(-1) / a
. Затем я могу исправитьc
пропорционально... просто мысль... - person goodvibration   schedule 28.10.2020double
. - person chux - Reinstate Monica   schedule 28.10.2020c
константами времени компиляции? Почему бы вам не рассказать нам, что они собой представляют? Знание их заранее значительно упрощает задачу. - person KevinZ   schedule 01.11.2020a
,b
иc
) не имеет постоянных значений. - person goodvibration   schedule 01.11.2020c
не является единственной константой времени компиляции, она должна находиться в очень ограниченном наборе констант времени компиляции, для всех из которых можно жестко закодировать. Деление против известного делителя также намного быстрее, чем деление против неизвестного делителя. Тем не менее, возможно, есть альтернативный способ упростить это, еслиc
не может быть постоянным: если вы можете пообещать, чтоc < sqrt(UINT_MAX)
, то возможен другой способ сокращения. - person KevinZ   schedule 01.11.2020c
) непостоянно. Более того, я опубликовал ограниченную ситуацию, с которой пытался справиться для начала (a < c && b < c
), хотя на самом деле в моей системе возможен любой сценарий. Я уже разработал решение с постоянным временем (то есть без циклов), которое вы можете увидеть ниже. Спасибо. - person goodvibration   schedule 01.11.2020