Jump to content

    

Как определить, что произведение двух чисел не переполнит uint64_t?

4 минуты назад, MegaVolt сказал:

Да. Но если не усложнять то для положительных чисел можно просто к y добавить некоторую дельту.

Дануна ! ( древнерусский бог удивления )

допустим дельта=1

а числа X=7FFF`FFFF`FFFF`FFFF и Y=2

тогда статическая проверка не пройдет, но и переполнения не будет =)

Share this post


Link to post
Share on other sites
3 минуты назад, megajohn сказал:

Дануна ! ( древнерусский бог удивления )

допустим дельта=1

а числа X=7FFF`FFFF`FFFF`FFFF и Y=2

тогда статическая проверка не пройдет, но и переполнения не будет =)

Я мысленно представлял дельту типа 1e-10 :))

Share this post


Link to post
Share on other sites

На 0 проверить отдельным условием не сложно. 

Share this post


Link to post
Share on other sites
1 час назад, MegaVolt сказал:

Я мысленно представлял дельту типа 1e-10 :))

    uint64_t x = 1000377;
    uint64_t y = 18439792272023;
    uint64_t z = x * y;
    printf( "%I64u * %I64u = %I64u\n", x, y, z ); // 1000377 * 18439792272023 = 1055
    printf( "%I64X * %I64X = %I64X\n", x, y, z ); // F43B9 * 10C55944A297 = 41F

    double xf = (double)x;
    double yf = (double)y;
    double ver1 = UINT64_MAX / ( xf + 1e-10 );
    double ver2 = UINT64_MAX / ( yf + 1e-10 );

    bool over1 = ver1 > yf;
    bool over2 = ver2 > xf;

    printf( "1=%s 2=%s", over1 ? "overflow" : "normal", over2 ? "overflow" : "normal" ); // 1=normal 2=normal

я правильно сделал ?

Share this post


Link to post
Share on other sites
3 часа назад, ViKo сказал:

Хочу в static_assert проверять оговоренное в заголовке условие. Как-то логарифмы сложить? Но не вижу, что получится точно.
К примеру, 7 * 4 = 28, а 7 * 7 = 49. Результат оккупирует разное количество битов.

Разрядность результата произведения равна сумме разрядностей множителей. Или log(x*y)=log(x)+log(y). В школе вроде ещё проходили.

Отсюда следует и возможность проверки.

3 часа назад, MegaVolt сказал:

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

Это не так. Подумайте над выражением например: 1*20 результат которого хотим впихнуть в 8 бит.

Share this post


Link to post
Share on other sites
13 минут назад, megajohn сказал:

    ....

    double ver1 = UINT64_MAX / ( xf + 1e-10 );

    double ver2 = UINT64_MAX / ( yf + 1e-10 );

    ....

я правильно сделал ?

Учитывая что UINT64_MAX не влазит в double без округления то похоже не правильно :) Надо бы long double использовать как я понимаю.

Share this post


Link to post
Share on other sites
26 минут назад, jcxz сказал:

Разрядность результата произведения равна сумме разрядностей множителей. Или log(x*y)=log(x)+log(y). В школе вроде ещё проходили.

Отсюда следует и возможность проверки.

Это не так. Подумайте над выражением например: 1*20 результат которого хотим впихнуть в 8 бит.

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

 

Ну, и, контрольный вопрос. Чему равен логарифм 2, и сколько разрядов требуется числу 2? 

Share this post


Link to post
Share on other sites
static_assert(x*y/x==y)

x и y типа uint64_t или int64_t, x != 0

 

Share this post


Link to post
Share on other sites
3 часа назад, ViKo сказал:

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

И что? Хоть одинаковое, хоть разное - формула работает одинаково.

3 часа назад, ViKo сказал:

Но нашлось решение проще и красивее, и точнее.

Умножить-поделить-сравнить? Это вроде как само собой очевидное решение. По-крайней мере для использования внутри условных выражений си-компилятора.

3 часа назад, ViKo сказал:

Ну, и, контрольный вопрос. Чему равен логарифм 2, и сколько разрядов требуется числу 2? 

Не понял - к чему этот вопрос?  :unknw:

Share this post


Link to post
Share on other sites
2 часа назад, MegaVolt сказал:

Учитывая что UINT64_MAX не влазит в double без округления то похоже не правильно :) Надо бы long double использовать как я понимаю.

да, но в ARM ( что использует ТС ) double и long double это одно и тоже

http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0774h/vuz1493281532660.html

http://supp.iar.com/filespublic/updinfo/004916/arm/doc/EWARM_DevelopmentGuide.ENU.pdf

Share this post


Link to post
Share on other sites
6 hours ago, jcxz said:

Разрядность результата произведения равна сумме разрядностей множителей. Или log(x*y)=log(x)+log(y).

Вроде этим все сказано (только логарифм по 16): сдвинуть сомножители влево до первого ненулевого байта, сумма оставшихся байт даст разрядность произведения. Вроде катит...

Share this post


Link to post
Share on other sites
53 минуты назад, Axel сказал:

Вроде этим все сказано (только логарифм по 16): сдвинуть сомножители влево до первого ненулевого байта, сумма оставшихся байт даст разрядность произведения. Вроде катит...

Да, грубо - можно так.

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

Share this post


Link to post
Share on other sites
1 hour ago, jcxz said:

Да, грубо - можно так.

Если точнее - сумма количества значащих бит сомножителей даст разрядность произведения с погрешностью -1 бит.

Share this post


Link to post
Share on other sites

Накидал на скорую руку макрос, показывающий переполнение при перемножении 2 8-битных множителей.

Для 64-битных множителей все по аналогии. Да, простынь будет в коде, зато работает (вроде):biggrin:

// макрос, разбивающий входные множители на простые слагаемые
#define u8mulovf(x, y) u8ovf((u8)((x)*((y) >> 0 & 1)), \
                             (u8)((x)*((y) >> 1 & 1)), \
                             (u8)((x)*((y) >> 2 & 1)), \
                             (u8)((x)*((y) >> 3 & 1)), \
                             (u8)((x)*((y) >> 4 & 1)), \
                             (u8)((x)*((y) >> 5 & 1)), \
                             (u8)((x)*((y) >> 6 & 1)), \
                             (u8)((x)*((y) >> 7 & 1)))

// макрос, оценивающий переполнение в старшем разряде + контроль старших бит, если переполнение в 8 бите не обнаружено
#define u8ovf(a, b, c, d, e, f, g, h) ((((((((((((((((a >> 1 & 1) + (b & 1)) >> 1) +                                                                          \
                                      (a >> 2 & 1) + (b >> 1 & 1) + (c & 1)) >> 1) +                                                                          \
                                      (a >> 3 & 1) + (b >> 2 & 1) + (c >> 1 & 1) + (d & 1)) >> 1) +                                                           \
                                      (a >> 4 & 1) + (b >> 3 & 1) + (c >> 2 & 1) + (d >> 1 & 1) + (e & 1)) >> 1) +                                            \
                                      (a >> 5 & 1) + (b >> 4 & 1) + (c >> 3 & 1) + (d >> 2 & 1) + (e >> 1 & 1) + (f & 1)) >> 1) +                             \
                                      (a >> 6 & 1) + (b >> 5 & 1) + (c >> 4 & 1) + (d >> 3 & 1) + (e >> 2 & 1) + (f >> 1 & 1) + (g & 1)) >> 1) +              \
                                      (a >> 7 & 1) + (b >> 6 & 1) + (c >> 5 & 1) + (d >> 4 & 1) + (e >> 3 & 1) + (f >> 2 & 1) + (g >> 1 & 1) + (h & 1)) >> 1) \
                                      || (b & 0x80) || (c & 0xC0) || (d & 0xE0) || (e & 0xF0) || (f & 0xF8) || (g & 0xFC) || (h & 0xFE))

 

Макрос u8mulovf(x, y) вернет 1, если было обнаружено переполнение при перемножении x на y, которые ограничены 8 битами.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now