Sign in to follow this  

Templated math

This topic is 3725 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm trying to make a simple math library (sqrt, pow, log, etc. ), but with templates instead of functions. E.g. const int a = 50; const int b = 2; const int c = log<a, b>::value; Now, I think I know how to do it with integers, but I is there a way to use floats? Floats can't be used as template parameters. They could be packed (casted) to ints or long longs (except long double), passed as parameters and unpacked, but is there an elegant way to cast bits of a float immediate value to int or long long? The same applies for unpacking, but this may be less elegant, since it will be hidden in the implementation. Anyways, supposing this problem is solved, the compiler might report too deep template recursion for floats, right?

Share this post


Link to post
Share on other sites
I have no idea what you are trying to do, maybe you could elaborate on that.

Casting the float "bits" to int "bits" can be done with a construct like that:

float f = 47.11f;
int& i = *((int*)&f);

And the other way round;

float& fr = *((float*)&i);

However, I don't see how this would help your problem.

Share this post


Link to post
Share on other sites
Quote:
Original post by Rattenhirn
I have no idea what you are trying to do, maybe you could elaborate on that.


It's template metaprogramming. I want the calculations to be done during compile time.

Quote:

Casting the float "bits" to int "bits" can be done with a construct like that:

float f = 47.11f;
int& i = *((int*)&f);

And the other way round;

float& fr = *((float*)&i);

However, I don't see how this would help your problem.


It won't :-) I need to cast immediate values like:

int i = something(4.7f); // i should contains bits of 4.7f NOT 4

Share this post


Link to post
Share on other sites
You could use a fixed-point representation (which means you really used integers). As you noted, floats cannot be non-type template arguments, so you're really out of luck there. Fixed-point is likely the best option you have.

Share this post


Link to post
Share on other sites
Unfortunately you cannot pack floats into ints without loss of information. That's why casting can be a dangerous thing to do. The computer representation of floats and ints is like comparing a slide rule and an abacus. The first uses logarithmic representation of decimal numbers, the second just counts numbers. They cannot be interchanged. Non-type template parameters are severely restricted at this point in time.

--random

Share this post


Link to post
Share on other sites
Quote:
Original post by random_thinker
Unfortunately you cannot pack floats into ints without loss of information. That's why casting can be a dangerous thing to do. The computer representation of floats and ints is like comparing a slide rule and an abacus. The first uses logarithmic representation of decimal numbers, the second just counts numbers. They cannot be interchanged. Non-type template parameters are severely restricted at this point in time.

--random


Assuming certain conditions, int and float both have 4 bytes. So there can't be a loss of information. I need to sth like *(int *) &4.7f

Share this post


Link to post
Share on other sites
You can't do it with casting, because reinterpreting an int as a float or vice-versa would require a reinterpret_cast (hence the name), which means operating on something in memory, which means doing the work at runtime (incompatible with the template, and defeating the purpose even if it could work). Template recursion won't be a problem unless you actually recurse :)

It would have to be done with some kind of macro I guess. Something like (making very non-portable assumptions of course):


#define F2I(x) /* you're on your own for this one. ;) */
#define I2F(x) /* similarly */
// Won't be able to call a function or look up in a table there - has to be
// known compile-time-evaluable.


template <int encoded_base, int encoded_operand>
class log { static const float value; };

template <int encoded_base, int encoded_operand>
const float log::value = std::log(I2F(encoded_base), I2F(encoded_operand));

const float log2of50 = log<F2I(2), F2I(50)>::value;

Share this post


Link to post
Share on other sites
OK...I stand corrected. Would something like this help:

Quote:

A C Solution

Fortunately, the 1999 ISO C Standard defines two functions which were not a part of earlier versions of the standard. These functions round doubles and floats to long ints and have the following function prototypes:

long int lrint (double x) ;
long int lrintf (float x) ;


These functions are defined in <math.h> but are only usable with the GNU C compiler if C99 extensions have been enabled before <math.h> is included. This is done as follows:

#define _ISOC9X_SOURCE 1
#define _ISOC99_SOURCE 1

#include <math.h>


Two versions of the defines ensure that the required functions are picked up with older header files. In the GLIBC (the standard version of the C library on Linux) header files, these functions are defined as inline functions and are in fact inlined by gcc (the standard C compiler on Linux) when optimisation is switched on. If optimisation is switched off, the functions are not inlined and an executable calling these functions will need to be linked with the maths library.


Edit---

There's a good thread already on this subject here. Apparently SiCrane indicated that MSVC6 allows double and float as non type parameters and most C++ compilers will allow references to const double.

Hope it's of use...

--random

[Edited by - random_thinker on October 2, 2007 1:05:12 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
You can't do it with casting, because reinterpreting an int as a float or vice-versa would require a reinterpret_cast (hence the name), which means operating on something in memory, which means doing the work at runtime (incompatible with the template, and defeating the purpose even if it could work). Template recursion won't be a problem unless you actually recurse :)

It would have to be done with some kind of macro I guess. Something like (making very non-portable assumptions of course):


#define F2I(x) /* you're on your own for this one. ;) */
#define I2F(x) /* similarly */
// Won't be able to call a function or look up in a table there - has to be
// known compile-time-evaluable.


template <int encoded_base, int encoded_operand>
class log { static const float value; };

template <int encoded_base, int encoded_operand>
const float log::value = std::log(I2F(encoded_base), I2F(encoded_operand));

const float log2of50 = log<F2I(2), F2I(50)>::value;



Well, that's actually what I DON'T want to do. You are using std::log which gets computed at runtime.

Now, I (probably, haven't done yet) know how do write a log template, like:


template <int number, int base>
struct log {
static const int value = /* .... */;
};


The difference with your example is tht I can use it everywhere a constant is needed, e.g. array declaration:


char digits[log<pow<2, sizeof(unsigned) * CHAR_BITS>::value, 10>::value + 1];



As for floats, theoretically it is possible to do all the calculations using emulated FP arithmetic, so it's definitely possible to use floats in templates.

Because of lack of other options, maybe use:


template <int mantissa, int exp = 0>
struct tfloat {
static const int value = /* some bit shifts etc. according to IEEE 754 */;
};


The use:


const float x = logf<tfloat<5, 2>, tfloat<3> >;

Share this post


Link to post
Share on other sites
Non-integral non-template type parameters can be used with pointers or references to non-integral objects with external linkage. Example:

template <const float & theta>
struct Sin {
static float sin() {
return theta - theta * theta * theta / 6;
}
};

extern const float theta = 0.7853981633975f;
extern const float sin_theta = Sin<theta>::sin();

Produces:

_TEXT ENDS
PUBLIC ?sin_theta@@3MB ; sin_theta
_DATA SEGMENT
?sin_theta@@3MB DD 03f34641er ; 0.704653 ; sin_theta
_DATA ENDS
END

In MSVC 7.1 in a release build.

Share this post


Link to post
Share on other sites
Quote:
Original post by random_thinker
OK...I stand corrected. Would something like this help:

Quote:

A C Solution

Fortunately, the 1999 ISO C Standard defines two functions which were not a part of earlier versions of the standard. These functions round doubles and floats to long ints and have the following function prototypes:

long int lrint (double x) ;
long int lrintf (float x) ;


These functions are defined in <math.h> but are only usable with the GNU C compiler if C99 extensions have been enabled before <math.h> is included. This is done as follows:

#define _ISOC9X_SOURCE 1
#define _ISOC99_SOURCE 1

#include <math.h>


Two versions of the defines ensure that the required functions are picked up with older header files. In the GLIBC (the standard version of the C library on Linux) header files, these functions are defined as inline functions and are in fact inlined by gcc (the standard C compiler on Linux) when optimisation is switched on. If optimisation is switched off, the functions are not inlined and an executable calling these functions will need to be linked with the maths library.


--random



Not really, because these are FUNCTIONS which are computed at runtime. What is needed here is some kind of expression that as computed at compile time.

[Edited by - rozz666 on October 2, 2007 1:41:30 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
Non-integral non-template type parameters can be used with pointers or references to non-integral objects with external linkage.

Is it portable?
Quote:

Example:

template <const float & theta>
struct Sin {
static float sin() {
return theta - theta * theta * theta / 6;
}
};

extern const float theta = 0.7853981633975f;
extern const float sin_theta = Sin<theta>::sin();

Produces:

_TEXT ENDS
PUBLIC ?sin_theta@@3MB ; sin_theta
_DATA SEGMENT
?sin_theta@@3MB DD 03f34641er ; 0.704653 ; sin_theta
_DATA ENDS
END

In MSVC 7.1 in a release build.


But again, Sin::sin is a function not a constant.

[Edited by - rozz666 on October 2, 2007 2:00:56 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by rozz666
It won't :-) I need to cast immediate values like:

int i = something(4.7f); // i should contains bits of 4.7f NOT 4


Well, that's exactly what my examples are doing.

However, reading all the replies till now, I'm pretty sure I've understood what you want:

Calculating (complex) mathematical expressions at compile time.

Frankly, I think your best bet are macros.

If you want type safety, you may want to try inline functions. In theory, those should be computed at compile time as well. The compiler should expand the inline function and then calculate any constant operations.
But unfortunately, that depends on the compiler and the exact code you write.

Templates won't help you at all, because, basically, they are about doing the same operations to different type, and you want different things for different types. (Calculating the logarithm of int's is different than calculating the logarithm of floats) That's exactly what polymorphism is for.

Additionally, if you can calculate those logarithms with a bunch of few bit shifts, I wouldn't worry about the clock cycles spent to do that.

Lastly, before I'd add stuff like this "const float x = logf<tfloat<5, 2>, tfloat<3> >;" into my code, I'd use a calculator, add the result, and add a comment how I got that value.

But then again, I might still not be getting it. ;)

Share this post


Link to post
Share on other sites
If you want it to be a constant you can do:

template <const float & theta>
struct Sin {
static const float value;
};

template <const float & theta>
const float Sin<theta>::value = theta - theta * theta * theta / 6.0f;

extern const float theta = 0.7853981633975f;
extern const float sin_theta = Sin<theta>::value;

This is standard C++; however, some compilers without good template support will barf on it. IIRC, MSVC 7 will internal compiler error, though 7.1 should accept it.

Share this post


Link to post
Share on other sites
Quote:
Original post by Rattenhirn
Quote:
Original post by rozz666
It won't :-) I need to cast immediate values like:

int i = something(4.7f); // i should contains bits of 4.7f NOT 4


Well, that's exactly what my examples are doing.

However, reading all the replies till now, I'm pretty sure I've understood what you want:

Calculating (complex) mathematical expressions at compile time.

Frankly, I think your best bet are macros.


but macros don't allow specialization which is needed in recursive algorithms like log and sqrt.

Quote:


If you want type safety, you may want to try inline functions. In theory, those should be computed at compile time as well. The compiler should expand the inline function and then calculate any constant operations.
But unfortunately, that depends on the compiler and the exact code you write.


and inline functions with constant arguments aren't constant by definition.

Quote:


Templates won't help you at all, because, basically, they are about doing the same operations to different type, and you want different things for different types. (Calculating the logarithm of int's is different than calculating the logarithm of floats) That's exactly what polymorphism is for.


What you mean by polimorphism here?

Quote:


Additionally, if you can calculate those logarithms with a bunch of few bit shifts, I wouldn't worry about the clock cycles spent to do that.



The problem isn't about running time.
As for the bit shifts, you mean this?


template <int mantissa, int exp = 0>

struct tfloat {

static const int value = /* some bit shifts etc. according to IEEE 754 */;

};


It's not log, it's encoding a float.

Quote:


Lastly, before I'd add stuff like this "const float x = logf<tfloat<5, 2>, tfloat<3> >;" into my code, I'd use a calculator, add the result, and add a comment how I got that value.

But then again, I might still not be getting it. ;)


Most of the time I use calculator also, but what if you've got 20 constants like that?

It'll be easier to use formulas.

This is a bit exaggerated but useful example:

char digits[log<pow<2, sizeof(unsigned) * CHAR_BITS>::value, 10>::value + 1];

It's a buffer for itoa or a strstream.

It could be simplified to:

char digits[sizeof(unsigned) * CHAR_BITS / log<10, 2>::value + 1];

and log<10, 2> can be calculated on a calculator, but in general such function are useful. E.g.

template <int base>
struct digit_buffer {
char digits[sizeof(unsigned) * CHAR_BITS / log<base, 2>::value + 1];
};

Anyways, I suppose I'd have to stick with integers only, for now at least.
If log<base, 2>::value == floor(log(base, 2)) the buffer should be ok.

Share this post


Link to post
Share on other sites
I am a major fan of Generic Programming. And in C++, templates and some types of metaprogramming.

But for the record, I simply don't understand why anyone wants to use C++ as a compile time scientific calculator?

In your example usage all of the top-level inputs need to be 100% known at compile time, and then they trickle down at compile time through template calculations into becoming additional values that can be used at compile time.

How is this any different functionally then just RUNNING A PROGRAM which yields a source file. You know, have some LISP, perl, or ruby script which generates a C++ source file, or whatever.

The template facilities in C++ are MUCH MUCH too weak to do all the millions of cool code generation tasks out there. So you are left trying desperately to fill a hole using a toothpick and a pair of scissors as your shovel (both extremely useful tools, just the wrong tools for the job).

The point of a calculator is to compute answers, the point of generic programming is to store general truth in a generally usable form (for instance formulas, container classes, algorithms, etc), the point of code generation is to produce something which can be directly referenced by a compiler.

So in your example. This c of which you speak that is derived as the log of a and b. If these are relatively fixed, then a calculator is your answer. If the fact that the C concept is fixed as being related to the A and B concept that way, then a generic (templated) method is your answer (run-time based). And if the above don't seem to fit right, then a code-generator is probably your answer.

Also worth noting is a code generator has a much better ability to do truly useful things. For instance if your engine needs some precomputed matrices for some algorithm you have, a true program can emit whatever artifact is ideal - int constants, float matrices, doubles, arrays, arrays of arrays of float matices, whatever, database records of relations of entities in your persistant world. Trying to build this level of smarts into a precompiler and compiler is just kinda crazy.

Share this post


Link to post
Share on other sites
Quote:
Original post by Xai
I am a major fan of Generic Programming. And in C++, templates and some types of metaprogramming.

But for the record, I simply don't understand why anyone wants to use C++ as a compile time scientific calculator?


Do you really mean you never tried to make a compile-time raytracer? There are crazy and very high-skilled people out there. A challenge just like others, I suppose.
I won't never engage in similar things, for sure! :-)

Share this post


Link to post
Share on other sites
Quote:
Original post by cignox1
Quote:
Original post by Xai
I am a major fan of Generic Programming. And in C++, templates and some types of metaprogramming.

But for the record, I simply don't understand why anyone wants to use C++ as a compile time scientific calculator?


Do you really mean you never tried to make a compile-time raytracer? There are crazy and very high-skilled people out there. A challenge just like others, I suppose.
I won't never engage in similar things, for sure! :-)


:), that made me laugh. You know it does remind me though, I don't mean to say anyone shouldn't do something they find fun. I personally draw a line between advice I give to people who are trying to get results, and advice I give to people who are enjoying the journey. A compile time math library could be fun, the same way an assembly game dev consest could be fun. But I certainly wouldn't pitch my next game engine to a publisher that way :).

Share this post


Link to post
Share on other sites

This topic is 3725 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this