How to determine integer types that are twice the width as `int` and `unsigned`?

Question

Values of intermediate multiplication typically need twice the number of bits as inputs.

 // Example
int foo(int a, int b, int carry, int rem) {
  int2x c;  // Some type that is twice as wide at `int`
  c = (int2x)a * b + carry;
  return (int) (c % rem);
}

Considering the potential for padding, (which appears to limit sizeof() usefulness) and non-2`s complement integers (which limits bit dibbling), ...

Does the following always create the needed type? (when it exists.)
If not, how to code at least a reasonable solution, even if not entirely portable?

#include <limits.h>
#include <stdint.h>

#if LONG_MAX/2/INT_MAX - 2 == INT_MAX
  typedef long int2x;
  typedef unsigned long unsigned2x;
#elif LLONG_MAX/2/INT_MAX - 2 == INT_MAX
  typedef long long int2x;
  typedef unsigned long long unsigned2x;
#elif INTMAX_MAX/2/INT_MAX - 2 == INT_MAX
  typedef intmax_t int2x;
  typedef uintmax_t unsigned2x;
#else
  #error int2x/unsigned2x not available
#endif

[Edit]
Qualify:"always", if long, long long and intmax_t, do not work it is OK to #error.
What I want to know is if at least 1 of long, long long, or intmax_t will work, will int2x be correctly typed?

Notes: The above assumes xxx_MAX are some odd power-of-2 minus 1. Maybe a good assumption? The above works on at least 2 platforms, but that is hardly a great portability test.

+1 for an interesting question, but for a "reasonable solution" **AND** "entirely portable", why not just stay on the safe side and use `long long` in any case? You're casting back to `int` at the end anyway, so what's the point in being "cheap" on the intermediate variable? — barak manos, Sep 22 '14 at 21:04
No, it doesn't capture the weirdo possibilities. It says nowhere that such a type as you are looking for must exist. I'd compare `INT_MAX` with `INT16_MAX` and `INT32_MAX` to see if `int` is `16` or `32` bit wide. Then I'd use `int_least32_t` or `int_least64_t`, respectively, for `int2x`. — Jens Gustedt, Sep 22 '14 at 21:14
This seems an exercise in futility; why not just use explicitly sized types (`int16_t`, etc.) if you want reproducible maths? — Oliver Charlesworth, Sep 22 '14 at 21:40
@barak manos Using `long long` when `long` would work could quadruple execution time. A driving problem, of which th is is simplified, is a many `int` in length. As much of the code used used in embedded and also PC based, the `int` can easily be 16, or 32. — chux - Reinstate Monica, Sep 22 '14 at 22:03
Note that the problem is not necessarily solvable. In particular, `int`, `long`, and `long long` could all be exactly the same size (as long as they're 64-bit or larger). In this case you can break the multiplication down into half-sized units yourself rather than using `#error`, though... — R.. GitHub STOP HELPING ICE, Sep 22 '14 at 22:05
@R.. Agreed that integer types could all be the same size, but at least the `#else #error` would catch the problem - thought not solve it. Using half-width multiplication would be an approach — chux - Reinstate Monica, Sep 22 '14 at 22:11
@Jens Gustedt 1) Please provide a sample "weirdo possibilities" that fails. 2) Does not the `#else #error` capture the "type ... must exist."? 3) Thought of the `UINT16_MAX/UINT32_MAX` approach but that has trouble with the pre-processor. Should have re-considered the `INT16_MAX/INT32_MAX` approach. That appears more straight-forward, other than it doesn’t handle 18/36 bit `int` and other non-power-of-2 widths – I would suspect those are rare these days – but IDK. — chux - Reinstate Monica, Sep 22 '14 at 22:18
@Jens Gustedt Agree `int` could be 24-bit. But how does the posted solution fail for 24-bit, especially given such a machine may have a `long` or `long long` of 48-bit? (Aside: modern day PICs have a 24-bit integer type - though use 16-bit for `int`.) — chux - Reinstate Monica, Sep 23 '14 at 13:33
@chux they *may* have a 48 bit `long` or `long long`, but also these *may* have 32 and 64 bit. — Jens Gustedt, Sep 23 '14 at 14:59
@Jens Gustedt Appended an edit to deal with `weirdo possibilities`. — chux - Reinstate Monica, Jan 03 '15 at 02:35
@chux where you say "some odd power-of-2 minus 1" did you mean **even power-of-two**? — Weather Vane, Mar 24 '15 at 18:19
@Weather Vane I do mean "some odd power-of-2 minus 1". To clarify: Every signed integer type I have worked with (except 9-bit char) had a max value like `pow(2,31)-1` or `pow(2,some_odd)-1`, etc. OTOH, maximum value of unsigned integer types, that I have seen, have always been `pow(2,some_even)-1` . — chux - Reinstate Monica, Mar 24 '15 at 19:09
@Oliver Charlesworth (Sorry for the late response) as in "why not just use explicitly sized types"? In implementing some functions that performed with standard structures like `struct tm`, many of the fields are `int` and their type is not for me to alter. Code often need to cope with something like the sum `tm.tm_year + tm.tm_mon/12`. Without a type like `int2x`, the code to detect overflow is unnecessarily complicated. — chux - Reinstate Monica, Mar 24 '15 at 19:23

score 5 · Answer 1 · answered Sep 22 '14 at 22:19

5

The assumption that all *_MAX constants are of the form (2^n)-1 is valid. See 6.2.6 Representations of Types, and particularly 6.2.6.2 Integer types, where the representations of unsigned integer types and the positive values of signed integer types are fully defined as pure binary, thus yielding a maximum which is one less than a power of two.

answered Sep 22 '14 at 22:19

R.. GitHub STOP HELPING ICE

208,859
35
376
711

I had hope to garner an answer than addressed the post more clearly with the bounty. But to no avail. As this answer better addresses parts of the post clearly, +50 to you. – chux - Reinstate Monica Mar 31 '15 at 00:00
Bounties don't seem to be as prominently displayed as they used to. I haven't noticed bounties for a long time... :-( – R.. GitHub STOP HELPING ICE Mar 31 '15 at 00:32

pablo1977 · Answer 2 · 2014-09-22T22:56:48.183

For signed types it's better to work just with the range of values of the considered types and compare them.

Firstly, one would try to calculate INT_MAX*INTMAX+INT_MAX in order to have the maximum possible value in the expression a*b+carry. By casting to intmax_t seems the more reasonable approach:

 #define MAX_EXPRESSION ((intmax_t) INT_MAX * INTMAX + INT_MAX)

However, we can fall in trouble if the true mathematical value of MAX_EXPRESSION is greater than INTMAX_MAX. So, let's do some maths to surround this problem.

Let's denote c = INT_MAX and m = INTMAX_MAX. We want to know if c*c+c <= m, mathematically speaking. This leads us to the inequation: c <= (m - c) / c. Since the division is integer, the result is truncated, so the exact maths are lost in the last operation. Thus, we have to write a more precise expression, like this: `c <= floor((m - c) / c) + fractional_part_of((m - c) / c).

If c > floor((m - c) / c), strictly, then c >= floor((m - c) / c) + 1 > (m - c) / c, where the division is taken in mathematical sense (with exact decimals). which gives us c*c+c > m, contradiction. So, we conclude that c <= floor((m - c) / c), again, mathematically speaking.

This expression is more handy in C, because m - c will give us a correct value when calculated with type intmax_t (in other words: it's not an out-of-range value). Now, the division (m - c) / c will give us an integer number in the range of intmax_t, again, although possibly truncated, because the division is integer. Actually, it gives us the value floor((m - c) / c, without hesitation.

It this comparisson gives true, then we can say that c*c+c is representable in the greatest signed integer type of your systen, that is, intmax_t. In particular: there exists a signed integer type which is capable of representing the value c*c+c in your system.

Now, in C code, we can write:

  #define c INT_MAX
  #define m INTMAX_MAX

  #if (c <= (m - c) / c)
     // There exists a signed type in your system
     // such that INT_MAX*INTMAX+INT_MAX is representable
     // as a value in that type.
  #else
      #error Sorry, the size of INT_MAX cannot be doubled...
  #endif

Once you have determined that intmax_t does the job, you simply can start a search for the signed integer type with minimal rank that solves the problem: We can ask again the same question we did for intmax_t, for example for long and long long:

  #include <stdint.h>
  #include <limits.h>
  #define c INT_MAX

  #if (c <= (INTMAX_MAX - c) / c)
      #if (c <= (LLONG_MAX - c) / c)
          #if (c <= (LONG_MAX - c) / c)
             typedef long int2x;
          #else
             typedef long long int2x;
          #endif
      #else
         typedef intmax_t int2x;
      #endif
  #else
      #error Sorry, the size of type "int" cannot be doubled...
  #endif

Thought: could not `INT_MIN*INT_MIN + INT_MAX` be greater than `INT_MAX*INT_MAX+INT_MAX`? — chux - Reinstate Monica, Sep 22 '14 at 23:13
Yes, it can. mmmm... Perhaps it would be enough if I add a comment about this issue at the end of the answer. — pablo1977, Sep 22 '14 at 23:31
But then does not that larger value affect the rest of the equations to the point they differ little from the post? — chux - Reinstate Monica, Sep 22 '14 at 23:36
Probably the negative values require an alternative analysis. I cannot do that in this moment. i will think about, later. — pablo1977, Sep 22 '14 at 23:57

How to determine integer types that are twice the width as `int` and `unsigned`?

2 Answers2

Linked