Type that can hold the product of two size_t

Question

I have two size_t integers and need to take their product. In what type should I store the result?

#include <limits>
#include <vector>
#include <iostream>

int main() {
    typedef std::size_t size_t;
    typedef unsigned long long product_t;

    std::vector<double> a(100000);
    std::vector<double> b(100000);

    size_t na {a.size()};
    size_t nb {b.size()};

    product_t prod = na * nb;

    std::cout << prod << std::endl;
}

It looks like gcc defines size_t as an unsigned long long so I am not guaranteed I will be able to store the product... any alternatives?

Edit:

The point here is that I am developing a library that needs to handle vectors of an arbitrary size, compute some statistic on it

double stat = computeStatisticOnVectors(a, b);

and then compute the following:

double result = stat / prod

Answer 1

It really depends on what you are trying to achieve with your code.

If you are later on going to use the value as a size_t (in other words, for sizing a vector, allocating memory, or some such), then you probably should do some checks that it's not overflowing, but store the value as a size_t. You won't be able to use a bigger type anyway, if the purpose is to create a new object based on the size.

If you are doing something like "calculating the number of possible combinations from these X vectors", then using a floating point type will probably be "good enough".

Answer 2

Have you considered not restricting yourself to a primitive type? If it's important to your application that such huge size_type values are handled, why not create a custom type which holds both original values?

Answer 3

Up until 128 bits, and assuming you don't need much portability, you may just use built-in types such as uint128_t (supported at least by gcc and clang on x86_64 platforms).

If you wish for more portability than this, then 128-bits integers are not standard, so you will need to:

1. Define your own, a pair of 64-bits integer with overload operators would work
2. Use an existing library, such as GMP (LGPL though, but much more generic)
3. From Marc Glisse: Boost.Multiprecision (without the license issue)

Of course, if you could simply eliminate this requirement it would be easier; this product you are computing does not seem to mean much in itself, so just doing stat / na / nb might well be enough.

Answer 4

In your example you're multiplying 100000 and 100000 (rather untypically large values for sizes), where apparently you would want to obtain 10^10 exactly as a result.

As a rough calculation based on 2^10 ~= 10^3, divide the 10's exponent by 3 and multiply by 10 to get the number of bits. Now 10*10/3 is roughly 33, which means you need more than 32 bits, which means 64 bits. Thus, use a 64-bit type.

In addition to being 64-bit the type should be signed, because it's a good idea to use signed types for numbers (otherwise, due to implicit conversions you risk inadvertently using modular arithmetic, with hard to track down bugs). So, the built-in type that you're looking for is – signed 64-bit integer – oh, that's long long.

Or you can use one of the type aliases from <stdint.h>.

That said, why on Earth are you multiplying large sizes, and why do you need the result as an exact integer?

Answer 5

Your statistics will be computed on vectors, which size will not exceed size_t capacity. I think it's enough to detect overflow in your case. I can think of a double conversion of each size, then compare the two products (size_t based product vs double product)