Double integer precision multiplication in C++

Question

Is there any standard C++ way (e.g. class library) which provides integer multiplication with double precision? What I mean is: given two unsigned int's a,b the multiplication of them should give me an array of two unsigned int's {c, d} such that a*b = c + d*(UINT_MAX+1) ?

No, I guess not. I am talking about multiplication of natural numbers. Fixed point means that you have numbers in decimal notation with a fixed number of positions before and after the comma, isn't it? Idon't have any comma here. — Christian Lomp, Aug 23 '11 at 16:09

score 1 · Answer 1 · answered Aug 23 '11 at 15:55

1

GMP could be an option

answered Aug 23 '11 at 15:55

DumbCoder

5,696
3
29
40

Or code your own, I found switching to double (real - fp type) to afford sufficient precision for my needs, but got close to coding my own :) – John Aug 23 '11 at 16:00

score 1 · Answer 2 · answered Aug 23 '11 at 15:57

1

If you are restricted to the C++ standard libraries, the answer is no, there is no such predefined type. You can confirm that here. @DumbCoder suggested an alternative

answered Aug 23 '11 at 15:57

dario_ramos

7,118
9
61
108

score 1 · Answer 3 · answered Aug 23 '11 at 15:57

1

I'm not sure if this solves the problem, but as a crude built-in solution, you may try to use unsigned long long int, which is a 64-bit integer.

answered Aug 23 '11 at 15:57

Marek Waligórski

144
3

Not guaranteed to be portable though. – John Aug 23 '11 at 15:58
Don't you mean `unsigned long long`? @John Silver: `unsigned long long` was added to C++0x, so it is now part of the standard. – Praetorian Aug 23 '11 at 16:03
`unsigned long long int` and `unsigned long long` are names for the same time. – Keith Thompson Aug 23 '11 at 16:12
Thanks for the comment. I tried this with g++, but `unsigned long long (int)` seems to have the same size as `UINT_MAX.` (Which results in 1 if you multiply `UINT_MAX * UINT_MAX`). – Christian Lomp Aug 23 '11 at 16:13
1

@Christian: you should multiply `((unsigned long long)UINT_MAX) * UINT_MAX`. The type of an arithmetic expression only depends on the types of the operands, not the type you store it in: http://www.ideone.com/yvw0U – Steve Jessop Aug 23 '11 at 16:30
Yes, it works. Thanks. Although I am not sure whether `long long` is compiler independent. However with g++ it's fine. – Christian Lomp Aug 24 '11 at 10:28

score 1 · Answer 4 · answered Aug 23 '11 at 16:02

1

The BigInt class lets you work with arbitrary precision integers.

answered Aug 23 '11 at 16:02

Praetorian

106,671
19
240
328

score 1 · Answer 5 · edited May 23 '17 at 12:04

You were on the right track with splitting up the multiplication into pieces, except where you had h=(UINT_MAX+1)/2 it should be h=sqrt(UINT_MAX+1). If you have 32-bit integers for example h=0x10000. Multiplying by such a constant is the same as shifting left by a number of bits, so your equation becomes:

a0 = a & 0xffff;
a1 = a >> 16;
b0 = b & 0xffff;
b1 = b >> 16;
a*b = a0*b0 + ((a1*b0)<<16 + (a0*b1)<<16) + (a1*b1)<<32

Since each component is 16 bits or less, each multiplication is guaranteed to fit into an unsigned 32 bit result.

For adding multiple-precision values together, see How can I add and subtract 128 bit integers in C or C++ if my compiler does not support them?

Double integer precision multiplication in C++

5 Answers5