Discussion :

[gbdivers]

Salut à tous

Une idée d'exercice proposé par oodini :

Calcul Pi en utilisant la méta programmation avec template

Rien de compliqué, c'est un exercice pour débutant en méta programmation C++. Le principe de calcul est donné au début de la discussion cité et vous pouvez lire le tutoriel de Laurent Gomila sur la méta programmation : Réecriture des fonctions mathématiques

Pour ceux qui veulent, même exercice avec les constexpr en C++11. Comparer les 2 versions (temps de codage, sécurité du code, temps de compilation)

Vous avez 2 semaines pour faire l'exercice (je suis généreux )

Amuser vous bien

[Iradrille]

Prochaine étape : réaliser l'exercice en métaprogrammation.

Pas si facil

ira@linux-i7ac:~/projects> g++ pi.cpp -o pi && ./pi
pi.cpp:26:94: error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum) instantiating ‘struct pi<99100>’
pi.cpp:26:94: recursively required from ‘const pi_type pi<99999>::value’
pi.cpp:26:94: required from ‘const pi_type pi<100000>::value’
pi.cpp:36:27: required from here

pi.cpp:26:94: error: incomplete type ‘pi<99100>’ used in nested name specifier
pi.cpp:26:94: error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum) instantiating ‘struct sign<99101>’
pi.cpp:26:94: recursively required from ‘const pi_type pi<99999>::value’
pi.cpp:26:94: required from ‘const pi_type pi<100000>::value’
pi.cpp:36:27: required from here

pi.cpp:26:94: error: incomplete type ‘sign<99101>’ used in nested name specifier
ira@linux-i7ac:~/projects> g++ pi.cpp -o pi -ftemplate-depth=110000 && ./pi
g++: internal compiler error: Segmentation fault (program cc1plus)
Please submit a full bug report,
with preprocessed source if appropriate.
See <http://bugs.opensuse.org/> for instructions.
ira@linux-i7ac:~/projects>

edit: bien vu le déplacement, j'ai vu ton post qu'après

Sinon j'obtient quelques chose qui tend vers pi, mais très vite limité par le nombre de récursions. Je posterai mes sources plus tard pour laisser tout le monde chercher

[gbdivers]

Effectivement, j'avais oublié ce problème

Ben, faire l'exo sans en tenir compte, le principal est le code, pas le résultat (parce qu'en plus, on n'est pas c.n, on sait que Pi est une constante, si c'est le résultat qui compte, on fera un "const double Pi = ..." )

[oodini]

C++03 impose une profondeur d'instanciation d'au minimum 17, et C++11 de 1024, il me semble.

[germinolegrand]

1024 ? g++ s'arrête bien avant si mes souvenirs sont bons...
edit : Oui suis-je bête, à 900 par défaut ^^
En utilisant l'option appropriée, on peut augmenter ce nombre.

[Iradrille]

Pour le problème initial qui était de trouver k minimal tel que l'approximation de pi ait 5 décimales correctes, ça me semble "impossible" (possible en théorie, mais impossible à compiler à cause du coût énorme en ram) avec des templates.

On peut pas avoir de paramètres template de type double, donc pendant la recherche de k, on est obligé de recalculer pi entièrement à chaque itération (ce qui à un coût non négligeable ).

Il n'est pas non plus possible de faire une version template et constexpr car les fonctions template ne peuvent pas être spécialisées partiellement (ce qui gène pour les conditions d'arrêts).

Pour s'affranchir de la limite de niveau de récursion, en faisant plusieurs structs (pour les templates), ou plusieurs fonction (constexpr), on peut atteindre un très grand nombre d'itérations sans dépasser la limite de 900 / 512 appels récursifs.
Par exemple, une fonction "a" calculs 100 itérations (par récursion), une fonctions "b" appelle "a", puis elle même 100 fois. Ainsi on peut faire 100*99 itérations avec une profondeur d'appel d'au maximum 200 .

Exercice qui m'a permis de me rendre compte que même utilisés de la même façons templates et constexpr sont différents, et les constexpr ont ici un net avantage.
Seul "problème" des constexpr, si on fait pas gaffe elles repassent en fonctions normales toutes seules (si on dépasse le nombre de récursion maximum et qu'on utilise pas le résultat dans une constexpr).

Niveau temps de compilation, impossible de comparer avec une version utilisant des templates, mais quelques secondes pour la recherche de 5 décimales avec une PART_SIZE de 60, impossible à compiler pour une PART_SIZE de 80 et une recherche de 6 décimales.
(PART_SIZE = nombre d'itérations que chaque fonction fait; mes fonctions ont 3 parties pour éviter de dépasser la limite. Donc il y à au total PART_SIZE^3 itérations d'effectuées).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
// g++ -std=c++0x -o pi pi.cpp -DDIGITS=5 && ./pi
 
#if DIGITS < 1
#	error DIGITS < 1
#endif
 
#include <iostream>
#include <iomanip>
#include <array>
 
constexpr double make_target_prec(int i) {
	return (i > 1) ? 10.0 * make_target_prec(i-1) : 10.0;
}
 
const int PART_SIZE = 60;
const int TOTAL_RECURSION = PART_SIZE * PART_SIZE * PART_SIZE;
const double PI = 3.141592654;
const double TARGET_PREC = make_target_prec(DIGITS);
const double TARGET = (((int)(PI*TARGET_PREC))/TARGET_PREC);
 
#define PI_STEP(x) ((((x) % 2) == 0 ? 4.0: -4.0) / (2.0*(x)+1.0))
 
constexpr double pi_part2(int s, int c) {
	return
		(s <= 0 || c == PART_SIZE) ?
			0.0 :
			PI_STEP(s) + pi_part2(s-1, c+1);
}
 
constexpr double pi_part1(int s, int c) {
	return
		(s <= 0 || c == PART_SIZE) ?
			0.0 :
			pi_part2(s, 0) + pi_part1(s-PART_SIZE, c+1);
}
 
constexpr double pi(int s) {
	return
		(s <= 0) ?
			4.0 :
			pi_part1(s, 0) + pi(s-PART_SIZE*PART_SIZE);
}
 
constexpr int find_part2(int s, int c, double p) {
	return
		(c == PART_SIZE) ?
			-1 :
			(((int)((p+PI_STEP(s))*TARGET_PREC))/TARGET_PREC) == TARGET ?
				s : 
				find_part2(s+1, c+1, p+PI_STEP(s));
}
 
constexpr int find_part1(int s, int c, double p) {
	return
		(c == PART_SIZE) ?
			-1 :
			find_part2(s, 0, p) != -1 ?
				find_part2(s, 0, p) :
				find_part1(s+PART_SIZE,
					c+1,
					((s == 0) ? pi(0): 0.0) + p+pi_part2(s+PART_SIZE-1, 1));
}
 
constexpr int find_k(int s=0, int c=0, double p=0.0) {
	return
		(c == PART_SIZE) ?
			-1 :
			find_part1(s, 0, p) != -1 ?
				find_part1(s, 0, p) :
				find_k(s+PART_SIZE*PART_SIZE,
					c+1,
					((s == 0) ? pi(0): 0.0) + p+pi_part1(s+PART_SIZE*PART_SIZE-1, 0));
}
 
 
int main() {	
	constexpr int k = find_k();
 
	// être sur d'avoir une constante de compilation
	std::array<int, ((unsigned int)(k>>30)) + 1> a; 
 
	std::cout << "k=" << k << " target=" << TARGET
		<< " pi(k)=" << std::setprecision(15) << pi(k) << std::endl;
 
	return 0;
}