Re: [C/algo] Cumul des termes d'un vecteur

[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 <knat...@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.

[philippe]

"JKB" <knat...@koenigsberg.fr> a écrit dans le message de
news:slrngoepmh.t...@rayleigh.systella.fr...

Bonjour

Tu tri ton vecteur par valeurs absolues croissantes puis tu sommes
"betement", plus il y en a mieux ca se porte !!
Espace = 2xTon vecteur
Cplx = n x lg(n) + n

[JKB]

Le 02-02-2009, ? propos de
Re: [C/algo] Cumul des termes d'un vecteur,

philippe ?crivait dans fr.comp.algorithmes :

> Bonjour
>
> Tu tri ton vecteur par valeurs absolues croissantes puis tu sommes
> "betement", plus il y en a mieux ca se porte !!
> Espace = 2xTon vecteur
> Cplx = n x lg(n) + n

Bonjour,

Ça ne fonctionne pas (en tout cas, ça n'est pas optimal en terme de
précision). On démontre que c'estt optimal dans le cas d'un vecteur de
termes tous positifs (ou négatifs) mais pas pour un vecteur dont les
termes sont quelconques, ce qui est mon cas...

Cordialement,

JKB

[Jean-Marc Bourguet]

JKB <knat...@koenigsberg.fr> writes:

> > 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.

http://bt.pa.msu.edu/TM/BocaRaton2006/talks/lauter.pdf

Vers la page 20.

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]

Le 03-02-2009, ? propos de

Re: [C/algo] Cumul des termes d'un vecteur,

Jean-Marc Bourguet ?crivait dans fr.comp.algorithmes :

> JKB <knat...@koenigsberg.fr> writes:
>
>> > 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.
>
> http://bt.pa.msu.edu/TM/BocaRaton2006/talks/lauter.pdf

Merci.

JKB