Je suis en train de me poser un problème d'algorithmie (peut-être de
base, mais sur ce coup, google n'est pas mon ami...). J'ai un vecteur de
real*8, enfin de double ;-) d'une taille imposante (plusieurs milliers
de termes de tout ordre de grandeur). Je cherche à obtenir la somme des
termes avec le minimum de perte de précision.
Lors de mes lointaines études, j'ai appris qu'il fallait toujours
additionner les termes d'une accumulation en partant des plus petits en
valeur absolue. J'ai donc écrit la chose suivante :
real8
sommation_vecteur_reel(real8 *vecteur, unsigned long *taille,
logical1 *erreur_memoire)
{
unsigned long nombre_elements;
unsigned long pointeur;
/*
* Sommation des termes en commençant par le plus petit
*/
qui a le mérite de respecter la règle précédente (même si c'est du
goret-coding...) . Maintenant, sur un vecteur de quelques millions d'éléments,
le temps de calcul peut être très long... tri_vecteur est un tri shell Metzner
qui trie en fonction de la valeur _non_ signée. Je suppose qu'il existe un algo
largement plus optimal. Quelqu'un aurait-il un pointeur, un article ?
Merci de vos lumières,
JKB
--
Le cerveau, c'est un véritable scandale écologique. Il représente 2% de notre
masse corporelle, mais disperse à lui seul 25% de l'énergie que nous
consommons tous les jours.
Si tu en as vraiment beaucoup, tu peux pas te contenter de faire ca ordre de grandeur par ordre de grandeur ?
Ton algo deviendrait lineaire, du coup...
Jean-Marc Bourguet
JKB writes:
Je suis en train de me poser un problème d'algorithmie (peut-être de base, mais sur ce coup, google n'est pas mon ami...). J'ai un vecteur de real*8, enfin de double ;-) d'une taille imposante (plusieurs milliers de termes de tout ordre de grandeur). Je cherche à obtenir la somme des termes avec le minimum de perte de précision.
Ça, c'est une question pour Vincent.
En attendant un spécialiste d'analyse numérique, tu peux faire quelque chose qui s'approche de la double précision (et que j'ai trouvé si j'ai bonne mémoire chez D.E.K.)
real8 sum(real8 const* array, int size) { real8 result = 0.0, error = 0.0; int i; for (i = 0; i < size; ++i) { real8 temp = result; real8 y = array[i] + error; result = temp + y; error = (temp - result) + y; } return result;
}
Sinon j'ai un vague souvenir que le meilleur moyen (pas nécessairement un ordre, tu peux faire des sommes partielles puis les sommer) dépend des données. Si tous les nombres sont positifs, effectivement l'ordre croissant est la réponse, mais si il y a des valeurs négative, le trouver est dans l'absolu un problème NP-complet.
A+
-- Jean-Marc FAQ de fclc: http://www.levenez.com/lang/c/faq Site de usenet-fr: http://www.usenet-fr.news.eu.org
JKB <knatschke@koenigsberg.fr> writes:
Je suis en train de me poser un problème d'algorithmie (peut-être
de base, mais sur ce coup, google n'est pas mon ami...). J'ai un vecteur
de real*8, enfin de double ;-) d'une taille imposante (plusieurs milliers
de termes de tout ordre de grandeur). Je cherche à obtenir la somme des
termes avec le minimum de perte de précision.
Ça, c'est une question pour Vincent.
En attendant un spécialiste d'analyse numérique, tu peux faire quelque
chose qui s'approche de la double précision (et que j'ai trouvé si j'ai
bonne mémoire chez D.E.K.)
real8 sum(real8 const* array, int size)
{
real8 result = 0.0, error = 0.0;
int i;
for (i = 0; i < size; ++i) {
real8 temp = result;
real8 y = array[i] + error;
result = temp + y;
error = (temp - result) + y;
}
return result;
}
Sinon j'ai un vague souvenir que le meilleur moyen (pas nécessairement un
ordre, tu peux faire des sommes partielles puis les sommer) dépend des
données. Si tous les nombres sont positifs, effectivement l'ordre
croissant est la réponse, mais si il y a des valeurs négative, le trouver
est dans l'absolu un problème NP-complet.
A+
--
Jean-Marc
FAQ de fclc: http://www.levenez.com/lang/c/faq
Site de usenet-fr: http://www.usenet-fr.news.eu.org
Je suis en train de me poser un problème d'algorithmie (peut-être de base, mais sur ce coup, google n'est pas mon ami...). J'ai un vecteur de real*8, enfin de double ;-) d'une taille imposante (plusieurs milliers de termes de tout ordre de grandeur). Je cherche à obtenir la somme des termes avec le minimum de perte de précision.
Ça, c'est une question pour Vincent.
En attendant un spécialiste d'analyse numérique, tu peux faire quelque chose qui s'approche de la double précision (et que j'ai trouvé si j'ai bonne mémoire chez D.E.K.)
real8 sum(real8 const* array, int size) { real8 result = 0.0, error = 0.0; int i; for (i = 0; i < size; ++i) { real8 temp = result; real8 y = array[i] + error; result = temp + y; error = (temp - result) + y; } return result;
}
Sinon j'ai un vague souvenir que le meilleur moyen (pas nécessairement un ordre, tu peux faire des sommes partielles puis les sommer) dépend des données. Si tous les nombres sont positifs, effectivement l'ordre croissant est la réponse, mais si il y a des valeurs négative, le trouver est dans l'absolu un problème NP-complet.
A+
-- Jean-Marc FAQ de fclc: http://www.levenez.com/lang/c/faq Site de usenet-fr: http://www.usenet-fr.news.eu.org
Eric Levenez
Le 02/02/09 20:34, dans , « JKB » a écrit :
Je suis en train de me poser un problème d'algorithmie (peut-être de base, mais sur ce coup, google n'est pas mon ami...).
fr.comp.algorithmes est ton ami.
-- Éric Lévénez FAQ de fclc : <http://www.levenez.com/lang/c/faq/>
Le 02/02/09 20:34, dans <slrngoeilo.t00.knatschke@rayleigh.systella.fr>,
« JKB » <knatschke@koenigsberg.fr> a écrit :
Je suis en train de me poser un problème d'algorithmie (peut-être de
base, mais sur ce coup, google n'est pas mon ami...).
fr.comp.algorithmes est ton ami.
--
Éric Lévénez
FAQ de fclc : <http://www.levenez.com/lang/c/faq/>
Ça me semble tellement gros que j'ai l'impression qu'il y a une subtilité qui m'échappe ce soir, mais pourquoi recommencer le tri pour chaque élément ? Qu'est ce qui ne va pas avec quelque chose comme :
tri_vecteur(vecteur, *taille); unsigned i; real8 somme = 0.0; for (i = 0 ; i < taille ; i++) somme += vecteur[i]; return somme;
Ensuite, pour le tri, ça ne coûte pas grand chose de comparer avec le qsort standard avant de chercher plus loin.
Arnaud
Lundi 02 février 2009, vers 20:34:23 (+0100), JKB a écrit:
Ça me semble tellement gros que j'ai l'impression qu'il y a une
subtilité qui m'échappe ce soir, mais pourquoi recommencer le tri pour
chaque élément ? Qu'est ce qui ne va pas avec quelque chose comme :
tri_vecteur(vecteur, *taille);
unsigned i;
real8 somme = 0.0;
for (i = 0 ; i < taille ; i++)
somme += vecteur[i];
return somme;
Ensuite, pour le tri, ça ne coûte pas grand chose de comparer avec le
qsort standard avant de chercher plus loin.
Ça me semble tellement gros que j'ai l'impression qu'il y a une subtilité qui m'échappe ce soir, mais pourquoi recommencer le tri pour chaque élément ? Qu'est ce qui ne va pas avec quelque chose comme :
tri_vecteur(vecteur, *taille); unsigned i; real8 somme = 0.0; for (i = 0 ; i < taille ; i++) somme += vecteur[i]; return somme;
Ensuite, pour le tri, ça ne coûte pas grand chose de comparer avec le qsort standard avant de chercher plus loin.
Arnaud
Arnaud Giersch
Lundi 02 février 2009, vers 21:24:14 (+0100), j'ai écrit:
Ça me semble tellement gros que j'ai l'impression qu'il y a une subtilité qui m'échappe ce soir, mais pourquoi recommencer le tri pour chaque élément ?
Je me réponds tout seul... pour faire à chaque fois la somme des deux éléments les plus petits. Dans ce cas, tu peux essayer de maintenir une structure de tas (heap). Ça derait être moins coûteux que de recommencer le tri à chaque fois.
Arnaud
Lundi 02 février 2009, vers 21:24:14 (+0100), j'ai écrit:
Ça me semble tellement gros que j'ai l'impression qu'il y a une
subtilité qui m'échappe ce soir, mais pourquoi recommencer le tri pour
chaque élément ?
Je me réponds tout seul... pour faire à chaque fois la somme des deux
éléments les plus petits. Dans ce cas, tu peux essayer de maintenir
une structure de tas (heap). Ça derait être moins coûteux que de
recommencer le tri à chaque fois.
Lundi 02 février 2009, vers 21:24:14 (+0100), j'ai écrit:
Ça me semble tellement gros que j'ai l'impression qu'il y a une subtilité qui m'échappe ce soir, mais pourquoi recommencer le tri pour chaque élément ?
Je me réponds tout seul... pour faire à chaque fois la somme des deux éléments les plus petits. Dans ce cas, tu peux essayer de maintenir une structure de tas (heap). Ça derait être moins coûteux que de recommencer le tri à chaque fois.
Arnaud
JKB
Le 02-02-2009, ? propos de Re: [C/algo] Cumul des termes d'un vecteur, Jean-Marc Bourguet ?crivait dans fr.comp.lang.c :
JKB writes:
Je suis en train de me poser un problème d'algorithmie (peut-être de base, mais sur ce coup, google n'est pas mon ami...). J'ai un vecteur de real*8, enfin de double ;-) d'une taille imposante (plusieurs milliers de termes de tout ordre de grandeur). Je cherche à obtenir la somme des termes avec le minimum de perte de précision.
Ça, c'est une question pour Vincent.
En attendant un spécialiste d'analyse numérique, tu peux faire quelque chose qui s'approche de la double précision (et que j'ai trouvé si j'ai bonne mémoire chez D.E.K.)
real8 sum(real8 const* array, int size) { real8 result = 0.0, error = 0.0; int i; for (i = 0; i < size; ++i) { real8 temp = result; real8 y = array[i] + error; result = temp + y; error = (temp - result) + y; } return result;
}
Sinon j'ai un vague souvenir que le meilleur moyen (pas nécessairement un ordre, tu peux faire des sommes partielles puis les sommer) dépend des données. Si tous les nombres sont positifs, effectivement l'ordre croissant est la réponse, mais si il y a des valeurs négative, le trouver est dans l'absolu un problème NP-complet.
C'est bien mon problème ;-) Et comme ça entre dans un autre algo NP-complet...
JKB
-- Le cerveau, c'est un véritable scandale écologique. Il représente 2% de notre masse corporelle, mais disperse à lui seul 25% de l'énergie que nous consommons tous les jours.
Le 02-02-2009, ? propos de
Re: [C/algo] Cumul des termes d'un vecteur,
Jean-Marc Bourguet ?crivait dans fr.comp.lang.c :
JKB <knatschke@koenigsberg.fr> writes:
Je suis en train de me poser un problème d'algorithmie (peut-être
de base, mais sur ce coup, google n'est pas mon ami...). J'ai un vecteur
de real*8, enfin de double ;-) d'une taille imposante (plusieurs milliers
de termes de tout ordre de grandeur). Je cherche à obtenir la somme des
termes avec le minimum de perte de précision.
Ça, c'est une question pour Vincent.
En attendant un spécialiste d'analyse numérique, tu peux faire quelque
chose qui s'approche de la double précision (et que j'ai trouvé si j'ai
bonne mémoire chez D.E.K.)
real8 sum(real8 const* array, int size)
{
real8 result = 0.0, error = 0.0;
int i;
for (i = 0; i < size; ++i) {
real8 temp = result;
real8 y = array[i] + error;
result = temp + y;
error = (temp - result) + y;
}
return result;
}
Sinon j'ai un vague souvenir que le meilleur moyen (pas nécessairement un
ordre, tu peux faire des sommes partielles puis les sommer) dépend des
données. Si tous les nombres sont positifs, effectivement l'ordre
croissant est la réponse, mais si il y a des valeurs négative, le trouver
est dans l'absolu un problème NP-complet.
C'est bien mon problème ;-) Et comme ça entre dans un autre algo
NP-complet...
JKB
--
Le cerveau, c'est un véritable scandale écologique. Il représente 2% de notre
masse corporelle, mais disperse à lui seul 25% de l'énergie que nous
consommons tous les jours.
Le 02-02-2009, ? propos de Re: [C/algo] Cumul des termes d'un vecteur, Jean-Marc Bourguet ?crivait dans fr.comp.lang.c :
JKB writes:
Je suis en train de me poser un problème d'algorithmie (peut-être de base, mais sur ce coup, google n'est pas mon ami...). J'ai un vecteur de real*8, enfin de double ;-) d'une taille imposante (plusieurs milliers de termes de tout ordre de grandeur). Je cherche à obtenir la somme des termes avec le minimum de perte de précision.
Ça, c'est une question pour Vincent.
En attendant un spécialiste d'analyse numérique, tu peux faire quelque chose qui s'approche de la double précision (et que j'ai trouvé si j'ai bonne mémoire chez D.E.K.)
real8 sum(real8 const* array, int size) { real8 result = 0.0, error = 0.0; int i; for (i = 0; i < size; ++i) { real8 temp = result; real8 y = array[i] + error; result = temp + y; error = (temp - result) + y; } return result;
}
Sinon j'ai un vague souvenir que le meilleur moyen (pas nécessairement un ordre, tu peux faire des sommes partielles puis les sommer) dépend des données. Si tous les nombres sont positifs, effectivement l'ordre croissant est la réponse, mais si il y a des valeurs négative, le trouver est dans l'absolu un problème NP-complet.
C'est bien mon problème ;-) Et comme ça entre dans un autre algo NP-complet...
JKB
-- Le cerveau, c'est un véritable scandale écologique. Il représente 2% de notre masse corporelle, mais disperse à lui seul 25% de l'énergie que nous consommons tous les jours.
JKB
Le 02-02-2009, ? propos de Re: [C/algo] Cumul des termes d'un vecteur, Arnaud Giersch ?crivait dans fr.comp.lang.c :
Lundi 02 février 2009, vers 21:24:14 (+0100), j'ai écrit:
Ça me semble tellement gros que j'ai l'impression qu'il y a une subtilité qui m'échappe ce soir, mais pourquoi recommencer le tri pour chaque élément ?
Je me réponds tout seul... pour faire à chaque fois la somme des deux éléments les plus petits.
C'est exactement ça.
Dans ce cas, tu peux essayer de maintenir une structure de tas (heap). Ça derait être moins coûteux que de recommencer le tri à chaque fois.
Je pensais à un truc dans ce style, mais soit ce l'ai codé n'importe comment, soit la technique n'apporte pas grand chose sur mes données.
Cordialement,
JKB
-- Le cerveau, c'est un véritable scandale écologique. Il représente 2% de notre masse corporelle, mais disperse à lui seul 25% de l'énergie que nous consommons tous les jours.
Le 02-02-2009, ? propos de
Re: [C/algo] Cumul des termes d'un vecteur,
Arnaud Giersch ?crivait dans fr.comp.lang.c :
Lundi 02 février 2009, vers 21:24:14 (+0100), j'ai écrit:
Ça me semble tellement gros que j'ai l'impression qu'il y a une
subtilité qui m'échappe ce soir, mais pourquoi recommencer le tri pour
chaque élément ?
Je me réponds tout seul... pour faire à chaque fois la somme des deux
éléments les plus petits.
C'est exactement ça.
Dans ce cas, tu peux essayer de maintenir
une structure de tas (heap). Ça derait être moins coûteux que de
recommencer le tri à chaque fois.
Je pensais à un truc dans ce style, mais soit ce l'ai codé n'importe
comment, soit la technique n'apporte pas grand chose sur mes données.
Cordialement,
JKB
--
Le cerveau, c'est un véritable scandale écologique. Il représente 2% de notre
masse corporelle, mais disperse à lui seul 25% de l'énergie que nous
consommons tous les jours.
Le 02-02-2009, ? propos de Re: [C/algo] Cumul des termes d'un vecteur, Arnaud Giersch ?crivait dans fr.comp.lang.c :
Lundi 02 février 2009, vers 21:24:14 (+0100), j'ai écrit:
Ça me semble tellement gros que j'ai l'impression qu'il y a une subtilité qui m'échappe ce soir, mais pourquoi recommencer le tri pour chaque élément ?
Je me réponds tout seul... pour faire à chaque fois la somme des deux éléments les plus petits.
C'est exactement ça.
Dans ce cas, tu peux essayer de maintenir une structure de tas (heap). Ça derait être moins coûteux que de recommencer le tri à chaque fois.
Je pensais à un truc dans ce style, mais soit ce l'ai codé n'importe comment, soit la technique n'apporte pas grand chose sur mes données.
Cordialement,
JKB
-- Le cerveau, c'est un véritable scandale écologique. Il représente 2% de notre masse corporelle, mais disperse à lui seul 25% de l'énergie que nous consommons tous les jours.
JKB
Le 02-02-2009, ? propos de Re: [C/algo] Cumul des termes d'un vecteur, Jean-Marc Bourguet ?crivait dans fr.comp.lang.c :
JKB writes:
Je suis en train de me poser un problème d'algorithmie (peut-être de base, mais sur ce coup, google n'est pas mon ami...). J'ai un vecteur de real*8, enfin de double ;-) d'une taille imposante (plusieurs milliers de termes de tout ordre de grandeur). Je cherche à obtenir la somme des termes avec le minimum de perte de précision.
Ça, c'est une question pour Vincent.
En attendant un spécialiste d'analyse numérique, tu peux faire quelque chose qui s'approche de la double précision (et que j'ai trouvé si j'ai bonne mémoire chez D.E.K.)
real8 sum(real8 const* array, int size) { real8 result = 0.0, error = 0.0; int i; for (i = 0; i < size; ++i) { real8 temp = result; real8 y = array[i] + error; result = temp + y; error = (temp - result) + y; } return result;
}
Je ne vois pas bien ce soir comment ce truc fonctionne (enfin, théoriquement parlant...). S'il y avait quelque part un pointeur avec une explication, je suis preneur.
Sinon j'ai un vague souvenir que le meilleur moyen (pas nécessairement un ordre, tu peux faire des sommes partielles puis les sommer) dépend des données. Si tous les nombres sont positifs, effectivement l'ordre croissant est la réponse, mais si il y a des valeurs négative, le trouver est dans l'absolu un problème NP-complet.
J'ai aussi commencé par scinder mon problème pour avoir des sommes partielles. Le souci est que je ne maîtrise plus la dérive...
Cordialement,
JKB
Xpost et fu2 à fca (que j'avais oublié...) -- Le cerveau, c'est un véritable scandale écologique. Il représente 2% de notre masse corporelle, mais disperse à lui seul 25% de l'énergie que nous consommons tous les jours.
Le 02-02-2009, ? propos de
Re: [C/algo] Cumul des termes d'un vecteur,
Jean-Marc Bourguet ?crivait dans fr.comp.lang.c :
JKB <knatschke@koenigsberg.fr> writes:
Je suis en train de me poser un problème d'algorithmie (peut-être
de base, mais sur ce coup, google n'est pas mon ami...). J'ai un vecteur
de real*8, enfin de double ;-) d'une taille imposante (plusieurs milliers
de termes de tout ordre de grandeur). Je cherche à obtenir la somme des
termes avec le minimum de perte de précision.
Ça, c'est une question pour Vincent.
En attendant un spécialiste d'analyse numérique, tu peux faire quelque
chose qui s'approche de la double précision (et que j'ai trouvé si j'ai
bonne mémoire chez D.E.K.)
real8 sum(real8 const* array, int size)
{
real8 result = 0.0, error = 0.0;
int i;
for (i = 0; i < size; ++i) {
real8 temp = result;
real8 y = array[i] + error;
result = temp + y;
error = (temp - result) + y;
}
return result;
}
Je ne vois pas bien ce soir comment ce truc fonctionne (enfin,
théoriquement parlant...). S'il y avait quelque part un pointeur avec
une explication, je suis preneur.
Sinon j'ai un vague souvenir que le meilleur moyen (pas nécessairement un
ordre, tu peux faire des sommes partielles puis les sommer) dépend des
données. Si tous les nombres sont positifs, effectivement l'ordre
croissant est la réponse, mais si il y a des valeurs négative, le trouver
est dans l'absolu un problème NP-complet.
J'ai aussi commencé par scinder mon problème pour avoir des sommes
partielles. Le souci est que je ne maîtrise plus la dérive...
Cordialement,
JKB
Xpost et fu2 à fca (que j'avais oublié...)
--
Le cerveau, c'est un véritable scandale écologique. Il représente 2% de notre
masse corporelle, mais disperse à lui seul 25% de l'énergie que nous
consommons tous les jours.
Le 02-02-2009, ? propos de Re: [C/algo] Cumul des termes d'un vecteur, Jean-Marc Bourguet ?crivait dans fr.comp.lang.c :
JKB writes:
Je suis en train de me poser un problème d'algorithmie (peut-être de base, mais sur ce coup, google n'est pas mon ami...). J'ai un vecteur de real*8, enfin de double ;-) d'une taille imposante (plusieurs milliers de termes de tout ordre de grandeur). Je cherche à obtenir la somme des termes avec le minimum de perte de précision.
Ça, c'est une question pour Vincent.
En attendant un spécialiste d'analyse numérique, tu peux faire quelque chose qui s'approche de la double précision (et que j'ai trouvé si j'ai bonne mémoire chez D.E.K.)
real8 sum(real8 const* array, int size) { real8 result = 0.0, error = 0.0; int i; for (i = 0; i < size; ++i) { real8 temp = result; real8 y = array[i] + error; result = temp + y; error = (temp - result) + y; } return result;
}
Je ne vois pas bien ce soir comment ce truc fonctionne (enfin, théoriquement parlant...). S'il y avait quelque part un pointeur avec une explication, je suis preneur.
Sinon j'ai un vague souvenir que le meilleur moyen (pas nécessairement un ordre, tu peux faire des sommes partielles puis les sommer) dépend des données. Si tous les nombres sont positifs, effectivement l'ordre croissant est la réponse, mais si il y a des valeurs négative, le trouver est dans l'absolu un problème NP-complet.
J'ai aussi commencé par scinder mon problème pour avoir des sommes partielles. Le souci est que je ne maîtrise plus la dérive...
Cordialement,
JKB
Xpost et fu2 à fca (que j'avais oublié...) -- Le cerveau, c'est un véritable scandale écologique. Il représente 2% de notre masse corporelle, mais disperse à lui seul 25% de l'énergie que nous consommons tous les jours.
Marc
JKB wrote:
Arnaud Giersch ?crivait dans fr.comp.lang.c :
Dans ce cas, tu peux essayer de maintenir une structure de tas (heap). Ça derait être moins coûteux que de recommencer le tri à chaque fois.
D'accord avec ça.
Je pensais à un truc dans ce style, mais soit ce l'ai codé n'importe comment, soit la technique n'apporte pas grand chose sur mes données.
Pour rester dans le code trivial, on peut remplacer le tri par une recherche du plus petit élément et son échange avec le premier (ou dernier, je n'ai pas bien suivi).
JKB wrote:
Arnaud Giersch ?crivait dans fr.comp.lang.c :
Dans ce cas, tu peux essayer de maintenir
une structure de tas (heap). Ça derait être moins coûteux que de
recommencer le tri à chaque fois.
D'accord avec ça.
Je pensais à un truc dans ce style, mais soit ce l'ai codé n'importe
comment, soit la technique n'apporte pas grand chose sur mes données.
Pour rester dans le code trivial, on peut remplacer le tri par une
recherche du plus petit élément et son échange avec le premier (ou
dernier, je n'ai pas bien suivi).
Dans ce cas, tu peux essayer de maintenir une structure de tas (heap). Ça derait être moins coûteux que de recommencer le tri à chaque fois.
D'accord avec ça.
Je pensais à un truc dans ce style, mais soit ce l'ai codé n'importe comment, soit la technique n'apporte pas grand chose sur mes données.
Pour rester dans le code trivial, on peut remplacer le tri par une recherche du plus petit élément et son échange avec le premier (ou dernier, je n'ai pas bien suivi).
