calculations in the preprocessing stage

[Pedro Graca]

Is there a way (preprocessor magic, perhaps ???) to use a type with
twice as many bits as `unsigned` (or `int`) with no changes to the
source code?

====
#define SINGLE_TYPE unsigned
#define DOUBLE_TYPE ???
====


I tried the following, and it worked in 2 different computers, with 2
different results.


#include <limits.h>
#include <stdio.h>

#define SINGLE_TYPE unsigned
#if UINT_MAX < ULONG_MAX / UINT_MAX
# define DOUBLE_TYPE unsigned long
# define DOUBLE_TYPE_STRING "unsigned long"
#else
# if UINT_MAX < ULLONG_MAX / UINT_MAX
# define DOUBLE_TYPE unsigned long long
# define DOUBLE_TYPE_STRING "unsigned long long"
# else
# error No available "DOUBLE_TYPE"
# endif
#endif

int main(void) {
printf("sizeof(SINGLE_TYPE) is %d; sizeof(DOUBLE_TYPE) is %d\n",
(int)sizeof(SINGLE_TYPE), (int)sizeof(DOUBLE_TYPE));
printf("DOUBLE_TYPE is \"%s\"\n", DOUBLE_TYPE_STRING);
return 0;
}


Is the above guaranteed to work, provided one of `unsigned long` or
`unsigned long long` is at least twice as large as `unsigned`?
It worked for me in two different compilers, but I'm not confident on
the preprocessing calculations.

(And, yes!, I realize `unsigned long long` is not defined by C89, but
I couldn't find the option to use only C89 in the compiler where I
needed that type)

 

[Michael Mair]

Is there a way (preprocessor magic, perhaps ???) to use a type with
twice as many bits as `unsigned` (or `int`) with no changes to the
source code?

====
#define SINGLE_TYPE unsigned
#define DOUBLE_TYPE ???
====


I tried the following, and it worked in 2 different computers, with 2
different results.


#include <limits.h>
#include <stdio.h>

#define SINGLE_TYPE unsigned
#if UINT_MAX < ULONG_MAX / UINT_MAX
# define DOUBLE_TYPE unsigned long
# define DOUBLE_TYPE_STRING "unsigned long"
#else
# if UINT_MAX < ULLONG_MAX / UINT_MAX
# define DOUBLE_TYPE unsigned long long
# define DOUBLE_TYPE_STRING "unsigned long long"
# else
# error No available "DOUBLE_TYPE"
# endif
#endif

Consider using typedef instead of #define for producing
identifiers that are meant for types.

int main(void) {
printf("sizeof(SINGLE_TYPE) is %d; sizeof(DOUBLE_TYPE) is %d\n",
(int)sizeof(SINGLE_TYPE), (int)sizeof(DOUBLE_TYPE));
printf("DOUBLE_TYPE is \"%s\"\n", DOUBLE_TYPE_STRING);
return 0;
}

Is the above guaranteed to work, provided one of `unsigned long` or
`unsigned long long` is at least twice as large as `unsigned`?
It worked for me in two different compilers, but I'm not confident on
the preprocessing calculations.

(And, yes!, I realize `unsigned long long` is not defined by C89, but
I couldn't find the option to use only C89 in the compiler where I
needed that type)

What is it exactly you are trying to do?
Just demanding "has at least twice as many bits as" (as your code
above does) seems strange to me.

The C99 header <stdint.h> can be used to determine whether exact
width two's complement integer types are available; if int<N>_t
is available as well as int<2N>_t (or uint<N>_t and uint<2N>_t,
respectively), then you have a valid pairing.
There are freely available <stdint.h> implementations / wrappers
for non-C99 compilers, see e.g.
http://clc-wiki.net/wiki/stdint.h


Cheers
Michael

 

[Flash Gordon]

Michael Mair wrote, On 18/02/08 20:34:

What is it exactly you are trying to do?
Just demanding "has at least twice as many bits as" (as your code
above does) seems strange to me.

Seems strange to me as well. Twice the range is more likely to be useful
(remember padding bits) but still seems unlikely to me.

The C99 header <stdint.h> can be used to determine whether exact
width two's complement integer types are available; if int<N>_t
is available as well as int<2N>_t (or uint<N>_t and uint<2N>_t,
respectively), then you have a valid pairing.
There are freely available <stdint.h> implementations / wrappers
for non-C99 compilers, see e.g.
http://clc-wiki.net/wiki/stdint.h

There are also the least and fast types in stdint.h which may be more
appropriate depending on the exact requirements.

 

[Pedro Graca]

What is it exactly you are trying to do?
Just demanding "has at least twice as many bits as" (as your code
above does) seems strange to me.

I have been tackling some of the UVa Online Judge problems
( http://icpcres.ecs.baylor.edu/onlinejudge/ ).
One of the last problems I addressed was to print large fibonacci
numbers (1000+ digits).
The first version of my code used char arrays and added them together
almost like I did at school; but I thought I could improve that
version by using unsigned ints to store the numbers and perform the
calculation with long unsigned ints MOD 1000000000 -- it would be more
useful for multiplication

My idea for multiplication is to end up with something like this:

SINGLE_TYPE f1[3], f2[2];
DOUBLE_TYPE tmp;
SINGLE_TYPE result[5];

for (k=0; k<2; ++k) for (j=0; j<3; ++j) {
tmp = (DOUBLE_TYPE)f1[j] * f2[k];
result[k+j] += tmp % 1000000000;
result[k+j+1] += tmp / 1000000000;
}

In real code f1, f2, and result would be arrays (or pointers to
malloc'd memory).

The C99 header <stdint.h> can be used to determine whether exact
width two's complement integer types are available; if int<N>_t
is available as well as int<2N>_t (or uint<N>_t and uint<2N>_t,
respectively), then you have a valid pairing.
There are freely available <stdint.h> implementations / wrappers
for non-C99 compilers, see e.g.
http://clc-wiki.net/wiki/stdint.h

Thank you. But my issue was how to code something like that with no
assumptions whatsoever (the 1000000000 would also be #defined based on
UINT_MAX).
In 10 years time `sizeof(unsigned)` will be 8; in 20 years it will be
16; 32 in 30 years; ...


PS: the version of the Fibonacci program with the char array was
faster on the UVa computer, the one with the unsigned array and long
unsigned helper variable was faster on my computer.

 

[Ben Bacarisse]

My idea for multiplication is to end up with something like this:

SINGLE_TYPE f1[3], f2[2];
DOUBLE_TYPE tmp;
SINGLE_TYPE result[5];

for (k=0; k<2; ++k) for (j=0; j<3; ++j) {
tmp = (DOUBLE_TYPE)f1[j] * f2[k];
result[k+j] += tmp % 1000000000;
result[k+j+1] += tmp / 1000000000;
}

The C99 header <stdint.h> can be used to determine whether exact
width two's complement integer types are available; if int<N>_t
is available as well as int<2N>_t (or uint<N>_t and uint<2N>_t,
respectively), then you have a valid pairing.
There are freely available <stdint.h> implementations / wrappers
for non-C99 compilers, see e.g.
http://clc-wiki.net/wiki/stdint.h

Thank you. But my issue was how to code something like that with no
assumptions whatsoever (the 1000000000 would also be #defined based on
UINT_MAX).

I don't think you followed this advice very thoroughly. You can't do
it with no assumptions at all, but if you assume that <stdint.h> is
there you can do what you want.

One key will be to loose the 1000000000. Big num calculations are
fast if you can avoid doing all those % and / operations. Replacing
them with & and >> is a good start:

uint_fast32_t *f1, *f2;
....
for (k=0; k<2; ++k) for (j=0; j<3; ++j) {
uint_least64_t tmp = (uint_least64_t)f1[j] * f2[k];
result[k+j] += tmp & 0xffffffffU;
result[k+j+1] += tmp >> 32;
}

In 10 years time `sizeof(unsigned)` will be 8; in 20 years it will be
16; 32 in 30 years; ...

I am not so sure! sizeof(char *) maybe, but plain unsigned?

 

[Pedro Graca]

One key will be to loose the 1000000000.

LOL, I'm too lazy.
To print one of my bignums I just do

printf("%u", bignum[0]);
for (k=1; k<bignum_size; ++k) printf("%09u", bignum[k]);

or the other way around if I store it little-endian

 

[Ben Bacarisse]

One key will be to loose the 1000000000.

LOL, I'm too lazy.
To print one of my bignums I just do

printf("%u", bignum[0]);
for (k=1; k<bignum_size; ++k) printf("%09u", bignum[k]);

or the other way around if I store it little-endian

OK, but most people would buy compute speed at the expense of slightly
more complex printing!