ansi-C question

[diep]

hi,

Perhaps someone can answer me this:

I want to achieve as fast as possible:

z = x * y (mod 2^32)

My simple idea:

unsigned int x,y;

x = something;
y = somethingelse;
z = x * y;

a) does it go ok?
b) does ansi-C garantuee this to go ok?

If not, then how do i achieve this in linux, in windows with intrinsics it is rather easy to achieve the goal.

Thanks,
Vincent

p.s. the goal is to speedup diep in 32 bits

[Zach Wegner]

What you wrote will work about anywhere. I'm not sure about ANSI C, but multiplication is done implicitly with mod x for x-bit arithmetic. For instance magic multiplication relies on this.

However, if z is more than 32 bit, then you must do a cast after the multiplication: (unsigned int)(x * y);

[Carey]

What you wrote will work about anywhere. I'm not sure about ANSI C, but multiplication is done implicitly with mod x for x-bit arithmetic. For instance magic multiplication relies on this.

However, if z is more than 32 bit, then you must do a cast after the multiplication: (unsigned int)(x * y);

Better make that uint32_t or some user defined data type is explicitly set as 32 bits, because simply doing (unsigned int) can cause portability issues when going between 32 & 64 bit systems.

On a 64 bit system, 'int' could be either 32 or 64 bits, depending on what the compiler writer chose to do. It can be 32 bits, but that violates the principle of C that says an 'int' is the register size. If you make it 64 bits, then you have trouble doing 32 & 16 bits.

So it's better to use explicit data types.


Also, if I remember right, C89 & C99 have a little bit of problem when doing type casts to smaller than normal types.

Whether you are trying to work with just floats or shorts or whatever, C may not always want to cooperate. It'll do the math, but it might choose an intermediate data type that is larger than desired and only do the size reduction when it stores the result. If it stores the result....

That's not really a problem with integers, but it can cause problems if you use float and depend on that specific precision. Or use 'double' and the math is done as 'long double'.

I think C99 might have worked around that by letting you put type casts through out the whole expression to tell the compiler to limit the intermediate types to exactly what you specifiy.

But since few C compilers are C99, I wouldn't bet on it always working right.

[Harald Johnsen]

hi,

Perhaps someone can answer me this:

I want to achieve as fast as possible:

z = x * y (mod 2^32)

My simple idea:

unsigned int x,y;

x = something;
y = somethingelse;
z = x * y;

a) does it go ok?
b) does ansi-C garantuee this to go ok?

If not, then how do i achieve this in linux, in windows with intrinsics it is rather easy to achieve the goal.

Thanks,
Vincent

p.s. the goal is to speedup diep in 32 bits

I doubt that ansi C can garantee anything that is processor dependant, and I don't see why a processor would garantee that when the results are wrong on overflow (but you are surely interested in only one processor type). The correct code is something like :

z = u32( u64(x) * u64(y) );

HJ.

[hMx]

I want to achieve as fast as possible:

z = x * y (mod 2^32)

My simple idea:

unsigned int x,y;

x = something;
y = somethingelse;
z = x * y;

a) does it go ok?
b) does ansi-C garantuee this to go ok?

Hi Vincent,

Yes, ANSI guarantees most of what you need.
Citing from chapter 6.1.2.5:

A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting unsigned integer type.

If you insist on mod 2^32 even if your (unsigned) is larger than 32 bits, you must of course still mask out the low 32 bits.
Also, make sure your (unsigned) is at least 32 bit... ah, yes, you knew that, already.

BTW: it is crucial to use unsigned operands, since signed operands are not guaranteed to work this way.

Cheers,
Heiner

[wgarvin]

BTW: it is crucial to use unsigned operands, since signed operands are not guaranteed to work this way.

C was designed in an era when not all machines used a 2's--complement representation for integers, so the language spec makes lots of allowances for different behaviour when shifting, multiplying, etc. with negative integer values so that implementations using a 1's-complement representation can still comply. However, pretty much every machine made in at least the last 20 years represents signed integers in a 2's-complement format, and uses the same mechanisms to deal with carry/borrow, overflow flags, etc.

Across the actual implementations that are out there, I think signed integer multiplication is probably just as portable as unsigned integer multiplication. (I haven't tried it myself though! Buyer beware).

[Bo Persson]

BTW: it is crucial to use unsigned operands, since signed operands are not guaranteed to work this way.

C was designed in an era when not all machines used a 2's--complement representation for integers, so the language spec makes lots of allowances for different behaviour when shifting, multiplying, etc. with negative integer values so that implementations using a 1's-complement representation can still comply. However, pretty much every machine made in at least the last 20 years represents signed integers in a 2's-complement format, and uses the same mechanisms to deal with carry/borrow, overflow flags, etc.

Across the actual implementations that are out there, I think signed integer multiplication is probably just as portable as unsigned integer multiplication. (I haven't tried it myself though! Buyer beware).

For a chess playing program, you can limit yourself to the kind of hardware you want to run it on.

When you design a programming language, you probably cannot. We still have important applications running mainframes, like this one with ones complement, and 36-bit registers:

http://unisys.com/products/mainframes/o ... /index.htm

Or this one, Brand New, not using IEEE floating point:

http://www-03.ibm.com/systems/z/

C and C++ are designed to allow native implementations on these machines. Java requires hardware addons!

This one is available at $125.000 a piece (multi configurations possible!)

http://www-03.ibm.com/systems/z/advantages/zaap/

[bob]

What you wrote will work about anywhere. I'm not sure about ANSI C, but multiplication is done implicitly with mod x for x-bit arithmetic. For instance magic multiplication relies on this.

However, if z is more than 32 bit, then you must do a cast after the multiplication: (unsigned int)(x * y);

The problem is the "unsigned int". It is not guaranteed to be 32 bits wide. It can be 64 bits wide just as easily. Unfortunately the ANSI committee didn't give us data types that allow us to specify 32 bits in a portable way. That "unsigned int" is 64 bits on a Cray, for example. And on the Dec Alphas depending on the O/S you are using.

[Carey]

What you wrote will work about anywhere. I'm not sure about ANSI C, but multiplication is done implicitly with mod x for x-bit arithmetic. For instance magic multiplication relies on this.

However, if z is more than 32 bit, then you must do a cast after the multiplication: (unsigned int)(x * y);

The problem is the "unsigned int". It is not guaranteed to be 32 bits wide. It can be 64 bits wide just as easily. Unfortunately the ANSI committee didn't give us data types that allow us to specify 32 bits in a portable way. That "unsigned int" is 64 bits on a Cray, for example. And on the Dec Alphas depending on the O/S you are using.

Sure they did, Bob. That's what uint32_t does.

It's guaranteed to be exactly 32 bits. No more and no less.

True, that's C99. It wasn't practical to do it back in C89 (that would have been too 'radical' of an idea, and they were already reaching the limit of what people were ready to tolerate).

That and more is in stdint.h They even provide things like uint_fast32_t for math that needs to be at least 32 bits but can be more if it would be faster (or more convenient) for the compiler or platform.

If you are using a compiler that doesn't provide stdint.h (and inttypes.h), then you probably should find a better compiler.

Or if you are desperate, you can at least fake it tolerably well (with custom headers) and still use those standard types in your program.

There are some portable ones floating around on the web, and I think a few people have posted similar headers here in the forum.

There's no reason to use vague sizes or compiler specific types in your code. Hasn't been for years.


I do realize that Microsoft refuses to support even a tiny bit of C99. Not even something as simple as stdint.h You can either switch to GNU C, or Intel C (I think it has it). Or you can do some custom headers to hide all that with #ifdef's etc. and let your own program be blissfully unaware of the low level details.

[bob]

What you wrote will work about anywhere. I'm not sure about ANSI C, but multiplication is done implicitly with mod x for x-bit arithmetic. For instance magic multiplication relies on this.

However, if z is more than 32 bit, then you must do a cast after the multiplication: (unsigned int)(x * y);

The problem is the "unsigned int". It is not guaranteed to be 32 bits wide. It can be 64 bits wide just as easily. Unfortunately the ANSI committee didn't give us data types that allow us to specify 32 bits in a portable way. That "unsigned int" is 64 bits on a Cray, for example. And on the Dec Alphas depending on the O/S you are using.

Sure they did, Bob. That's what uint32_t does.

That is not a natural data type. short, int, float are the usual types. Yes those came long later but not until the standard was already well-mangled. For example, exactly what is a "char"???

It's guaranteed to be exactly 32 bits. No more and no less.

True, that's C99. It wasn't practical to do it back in C89 (that would have been too 'radical' of an idea, and they were already reaching the limit of what people were ready to tolerate).

That and more is in stdint.h They even provide things like uint_fast32_t for math that needs to be at least 32 bits but can be more if it would be faster (or more convenient) for the compiler or platform.

If you are using a compiler that doesn't provide stdint.h (and inttypes.h), then you probably should find a better compiler.

Or if you are desperate, you can at least fake it tolerably well (with custom headers) and still use those standard types in your program.

There are some portable ones floating around on the web, and I think a few people have posted similar headers here in the forum.

There's no reason to use vague sizes or compiler specific types in your code. Hasn't been for years.


I do realize that Microsoft refuses to support even a tiny bit of C99. Not even something as simple as stdint.h You can either switch to GNU C, or Intel C (I think it has it). Or you can do some custom headers to hide all that with #ifdef's etc. and let your own program be blissfully unaware of the low level details.

Again, that is a portability issue that I have to deal with, since 99% of the machines on the planet are running windows, and the majority of those use MSVC variants, rather than gcc/icc... I would not mind writing purely for Linux in fact, as it would make the code _far_ cleaner, and I may well one day take this plunge as the current conditional compile stuff is a mess...