Переполнение при умножении

[aml]

Есть классная книжка "Алгоритмические трюки для программистов" — в ней ещё много полезных приёмов по целочисленному умножению и делению.

[oleg1977]

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

[aml]

Олег, вы неправильно меня поняли. Я коммент написал не чтобы уличить Вас в переизобретении велосипеда, а к тому, что есть ещё и другие интересные приёмы, про которые полезно почитать, и которые могут часто пригодиться.

[qehgt]

результат умножения имеет ту же разрядность, что и множители.

Да ну? Какого типа тогда будет результат умножения unsigned char на unsigned char?

[jcmvbkbc]

Все арифметические типы Уже int перед арифметикой приводятся к типу int. Т.е. unsigned char * unsigned char = int.

[oleg1977]

Согласен. Нужно было написать что-то вроде:
«результат умножения целых типа не короче int имеет ту же разрядность, что и множители»

[oleg1977]

Еще точнее: «C++ не умеет умножать целые короче int, а для целых не короче int разрядность результата совпадает с разрядностью умножения». Для long тоже можно изобрести что-то вроде:
long a, b;
//...
long long c = a*static_cast<long long>(b);

Но это уже выходит за рамки условий поста. Там задача — остаться в рамках исходной разрядности.

[Damaskus]

> В C/C++, в отличие от большинства ассемблеров,
> результат умножения имеет ту же разрядность, что и множители.

unsigned short a = 60000;
unsigned short b = 60000;
unsigned int i = a*b;

А так?

[jcmvbkbc]

4.5 Integral promotions — это часть «usual arithmetic conversions».

[oleg1977]

Вы правы, смотрите мой ответ на предыдущий комментарий

[sic]

Модельный пример несколько высосан из пальца, ибо гораздо лучшим решением будет использование функции QueryPerformanceCounter.

[sic]

LARGE_INTEGER c;
QueryPerformanceCounter(&c);
return c.QuadPart;

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

[sic]

нет, все же наврал. делить нужно на соответствующее значение QueryPerformanceFrequency. отличие разве что в том, что делитель здесь небольшой.

[lorc]

… особенно, где-нить на embedded системе вообще без ОС :)

[oleg1977]

Нет, моедльный пример — в реально работающем проекте. Вот только операционка там — ядро линукс, а все драйвера — свои. Из сторонних библиотек только libc

[f0rbidik]

Не проще ли один раз посчитать TICKS_PER_NSEC?

[oleg1977]

И чему оно будет равно? Обратите внимание, что в соответствии с условием вещественные типы использовать нельзя

[f0rbidik]

unsigned long long getNsec(unsigned long long ticks) {
    static const unsigned long long _GCD_TPS_NSPS = gcd(NSEC_PER_SECOND, TICKS_PER_SECOND);
    return ticks * (NSEC_PER_SECOND / _GCD_TPS_NSPS) / (TICKS_PER_SECOND / _GCD_TPS_NSPS);
};

[oleg1977]

Я для упрощения округлил до 1999000000ULL, полагая, что значение роли не играет. Считайте gcd = 1, такое будет, например, для TICKS_PER_SECOND = 1999000001ULL;

[oleg1977]

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

[GrossHo]

Все корректно. Кое где можно было бы привести умножение вместо второй операции '%' — может съэкономить пару тактов, если часто вызываема будет, поскольку операция деления и взятия остатка не сможет быть даже гипотетически объединена в одну операцию конвеером процессора (существуют в разрыв им другие операции). Нахождение общего делителя интересный момент, но гораздо хуже, если коэффициенты будут иметь единицу в качестве онного.