Template Recursion
My version isn't optimized to a constant in debug - there are actual function calls to value() in the debug build. The version that doesn't use function calls does resolve to a constant even in debug but as has been pointed out it relies on undefined behaviour and so won't work in general, or indeed in this specific case under VC :-)
Look at mathworld:
http://mathworld.wolfram.com/e.html
You can write e as a nested radical:
e = 1 + (1 + (1 + (1 + (...) / 4) / 3) / 2) / 1
(the mathworld version looks more beatiful)
The resulting code produced by gcc is:
As you can see, no additional code is generated.
Also no factorials are calculated, since that is not necessary.
BTW a similar formula for Pi is:
pi/2 = 1 + (1/3)*(1 + (2/5)*(1 + (3/7)*(1 + (4/8)*(1 + ...
http://mathworld.wolfram.com/e.html
You can write e as a nested radical:
e = 1 + (1 + (1 + (1 + (...) / 4) / 3) / 2) / 1
(the mathworld version looks more beatiful)
template <unsigned N>struct E{ static double calc(double d) { return E<N-1>::calc(1.0 + d / (double)N); }};template <>struct E<0>{ static double calc(double d) { return d; }};double foo(){ double e = E<55>::calc(1.0); return e;}/*#include <iostream>#include <iomanip>using namespace std;int main(){ cout << "d: " << setprecision(20) << foo() << endl; return 0;}*/The resulting code produced by gcc is:
C:\TEMP>gcc -c -O3 o3_test.ccC:\TEMP>objdump -DCzh o3_test.oo3_test.o: file format pe-i386Sections:Idx Name Size VMA LMA File off Algn 0 .text 00000010 00000000 00000000 000000b4 2**4 CONTENTS, ALLOC, LOAD, RELOC, READONLY, CODE 1 .data 00000000 00000000 00000000 00000000 2**4 ALLOC, LOAD, DATA 2 .bss 00000000 00000000 00000000 00000000 2**4 ALLOC 3 .rdata 00000010 00000000 00000000 000000c4 2**4 CONTENTS, ALLOC, LOAD, READONLY, DATADisassembly of section .text:00000000 <foo()>: 0: 55 push %ebp 1: 89 e5 mov %esp,%ebp 3: 5d pop %ebp 4: dd 05 00 00 00 00 fldl 0x0 a: c3 ret b: 90 nop c: 90 nop d: 90 nop e: 90 nop f: 90 nopDisassembly of section .rdata:00000000 <.rdata>: 0: 69 57 14 8b 0a bf 05 imul $0x5bf0a8b,0x14(%edi),%edx 7: 40 inc %eax 8: 00 00 add %al,(%eax) a: 00 00 add %al,(%eax) c: 00 00 add %al,(%eax) e: 00 00 add %al,(%eax)C:\TEMP>gcc -vReading specs from C:/MinGW/bin/../lib/gcc/mingw32/3.4.2/specsConfigured with: ../gcc/configure --with-gcc --with-gnu-ld --with-gnu-as --host=mingw32 --target=mingw32 --prefix=/mingw --enable-threads --disable-nls --enable-languages=c,c++,f77,ada,objc,java --disable-win32-registry --disable-shared --enable-sjlj-exceptions --enable-libgcj --disable-java-awt --without-x --enable-java-gc=boehm --disable-libgcj-debug --enable-interpreter --enable-hash-synchronization --enable-libstdcxx-debugThread model: win32gcc version 3.4.2 (mingw-special)As you can see, no additional code is generated.
Also no factorials are calculated, since that is not necessary.
BTW a similar formula for Pi is:
pi/2 = 1 + (1/3)*(1 + (2/5)*(1 + (3/7)*(1 + (4/8)*(1 + ...
Author
Hmmm. That's interesting. In the version I used, I am not showing any assmebly calls other than to cout to print it.
[edit]
This is compiled in VS2003, and 2005 beta 2
[/edit]
#define _USE_MATH_DEFINES#include <iostream>#include <cmath>template <unsigned int Value>struct Factorial{ enum { result = Value * Factorial<(Value - 1)>::result };};template <>struct Factorial <0>{ enum { result = 1 };};template <unsigned int Value, typename T>struct Invert{};template <unsigned int Value>struct Invert <Value, float>{ static const float result;};template <unsigned int Value>const float Invert <Value, float>::result = (1.0f / Value);template <unsigned int Value>struct Invert <Value, double>{ static const double result;};template <unsigned int Value>const double Invert <Value, double>::result = (1.0 / Value);template<unsigned int Limit>struct E{public: static const double result; static inline double f() { return Invert<Factorial<Limit>::result, double>::result + E<(Limit > 0) ? (Limit - 1) : 0>::f(); }};template<unsigned int Limit>const double E<Limit>::result = f();template <>struct E <0>{ //static const double result; static inline double f() { return 1.0; }};#define QUICK_CHANGE 12int main(void){ std::cout << Factorial<QUICK_CHANGE>::result << std::endl; std::cout.precision(36); std::cout << Invert<Factorial<QUICK_CHANGE>::result, float>::result << std::endl; std::cout << Invert<Factorial<QUICK_CHANGE>::result, double>::result << std::endl; std::cout << "-----------------------------------" << std::endl; double result = E<12>::result; std::cout << result << std::endl; std::cout << E<QUICK_CHANGE>::result << std::endl; std::cout << M_E << std::endl; return 0;}[edit]
This is compiled in VS2003, and 2005 beta 2
[/edit]
Author
I have seen 2 different methods of computing e
The one I used was
e = sum (1 / x!)
x = 0 -> infinity
and another
e = lim (1 + (1/N)^N
N->infinity
Since I had found the sum method first, that is what I went with. This mostly started out as a personal exercise in metalanguage templates.
The one I used was
e = sum (1 / x!)
x = 0 -> infinity
and another
e = lim (1 + (1/N)^N
N->infinity
Since I had found the sum method first, that is what I went with. This mostly started out as a personal exercise in metalanguage templates.
Your version has no extra function calls even in debug because you initialize the static data member with the function call whereas my version actually makes the function call when the value is needed in cout.
If you want to not have problems with the initialization order then you'll have to use a compile-time representation of, for example, a floating point number -- a template which has a sign, mantissa, and exponent as template parameters. Perform all of your calculations at compile-time with metafunctions on instantatiations of that template to result in a type which represents the value entirely at compile-time. Finally, you initialize the runtime float, double, or long double directly from its compile-time representation. Making a compile-time floating point type is no simple task, especially if you wish to account for infinities, posititive and negative zero representations, proper promotion when working with other compile-time arithmetic types, and have the exact same results as the runtime counter-part.
Because of this, I recommend checking out boost's metamath library which is currently in development and can be downloaded from the vault for your tinkering pleasure. It contains a compile-time double implementation and is capable of all of these things. As well, they are currently working on compile-time trigonometric functions with it and other math functions. Unfortunately, the Boost vault mysteriously got hosed recently, losing just about everything, meaning you'll have to wait for people to re-upload. Once everything is back in order, you will be able to find the metamath library here, in expaler's directory.
Because of this, I recommend checking out boost's metamath library which is currently in development and can be downloaded from the vault for your tinkering pleasure. It contains a compile-time double implementation and is capable of all of these things. As well, they are currently working on compile-time trigonometric functions with it and other math functions. Unfortunately, the Boost vault mysteriously got hosed recently, losing just about everything, meaning you'll have to wait for people to re-upload. Once everything is back in order, you will be able to find the metamath library here, in expaler's directory.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
