J'ai besoin d'évaluer la somme de la ligne: 1/1 + 1/2 + 1/3 + ... + 1 / n. Considérant que dans les évaluations C ++ ne sont pas complètes précises, l'ordre de résumé joue un rôle important. 1 / N + 1 / (N-1) + ... + 1/2 + 1/1 L'expression donne le résultat plus précis. J'ai donc besoin de trouver l'ordre de résumé, qui fournit la précision maximale. Je ne sais même pas où commencer. Le langage de réalisation préféré est C ++. Désolé pour mon anglais, s'il y a des erreurs.
8 Réponses :
http://fr.wikipedia.org/wiki/arbittrary-precision_arithmetic Vous pouvez trouver des bibliothèques avec la mise en oeuvre prête à utiliser pour C / C ++.
Par exemple http://www.apfloat.org/apflat/
En fait, je dois écrire "mon propre programme". Parce que c'est une sorte de tâche éducative.
Oui, mais au lieu d'utiliser des doubles doubles à basse précision, vous pouvez utiliser des apflages et obtenir aussi haute précision que nécessaire.
Je ne suis pas sûr de l'ordre de résumé jouer un rôle important, je n'ai pas entendu dire cela auparavant. Je suppose que vous voulez faire cela dans le point flottant arithmétique de sorte que la première chose à penser est de penser plus en ligne de (1.0 / 1.0 + 1.0 / 2.0 + 1.0 / 3.0) - sinon le compilateur fera une division entier
pour déterminer l'ordre d'évaluation , peut-être une boucle ou des crochets?
par exemple Oh a oublié de dire que les compilateurs auront normalement des commutateurs pour déterminer le mode d'évaluation du point flottant. Ceci est peut-être lié à ce que vous dites sur ordre de résumé - dans Visual C + Ceux-ci figurent dans les paramètres de compilation de génération de code, dans g ++, des options -float qui gèrent ce réellement, l'autre gars est droit - vous devriez faire la somme par ordre de plus petit composant en premier; alors
1/1 + 1 / (n-1) .. 1/1 En effet, la précision d'un numéro de point flottant est liée à la balance, si vous commencez à 1, vous aurez 23 bits de précision par rapport à 1.0. Si vous commencez à un nombre plus petit, la précision est relative au nombre plus petit, vous obtiendrez donc 23 bits de précision par rapport à 1XE-200 ou autre. Ensuite, lorsque le numéro obtient une erreur d'arrondi plus grande apparaîtra, mais l'erreur globale sera inférieure à l'autre direction
Utiliser des mathématiques à virgule flottante, ajoutez 1E-19 à 1 et regardez le résultat.
Oui, vous voulez résumer tous vos petits termes afin que l'effet de l'ajout 1 sera moins susceptible de les déplacer hors de la partie de votre flotteur.
La définition de la tâche indique qu'il joue un rôle. En point flottant, sûr. J'ai écrit la rangée "en voie mathématique". Et oui, j'ai pensé à une simple boucle, mais cela ne semble pas très bien, à cause d'un grand nombre de permutations de ce type.
La raison du manque de précision est la précision des types flottants, doubles et longs de longue durée. Ils ne stockent que tant de places "décimales". Ainsi, ajouter une très petite valeur à une valeur importante n'a aucun effet, le terme petit terme est "perdu" dans le plus grand.
La série que vous sommant a une "queue longue", dans le sens où les petits termes devraient ajouter une contribution importante. Mais si vous résumez en ordre décroissant, alors après un certain temps, chaque nouveau terme aura lieu sans effet (même avant cela, la plupart de ses décimales seront jetées). Une fois que vous arrivez à ce point, vous pouvez ajouter un milliard de termes plus, et si vous les faites une à la fois, cela n'a toujours aucun effet.
Je pense que le résumé de la commande ascendante devrait donner la meilleure précision de ce type de série, bien qu'il soit possible de certains cas d'angle étranges où des erreurs dues à l'arrondi aux pouvoirs de (1/2) pourraient aussi se rapprocher de répondre à des ordres d'addition que d'autres. Vous ne pouvez probablement pas vraiment prédire cela, cependant.
Le problème est que la série diverge, alors même si vous ajoutez les termes de l'ordre croissant, vous pouvez accéder à un point où l'ajout de chaque nouveau terme un à la fois n'a aucun effet.
Pour le grand n, vous feriez mieux d'utiliser des formules asymptotiques, comme ceux sur http: // fr. wikipedia.org/wiki/harmonic_number ;
Un autre moyen est d'utiliser la transformation des journaux d'exp. Fondamentalement:
h_n = 1 + 1/2 + 1/3 + ... + 1 / N = journal (exp (1 + 1/2 + 1/3 + ... + 1 / N)) = journal (exp (1) * exp (1/2) * exp (1/3) * ... * exp (1 / n)).
Les exposants et les logarithmes peuvent être calculés assez rapidement et accuratelly par votre bibliothèque standard. Utilisation de la multiplication, vous devriez obtenir des résultats beaucoup plus précis.
S'il s'agit de vos devoirs et que vous devez utiliser un ajout simple, vous ferez mieux d'ajouter du plus petit au plus grand, comme les autres suggérées.
Ces solutions sont bien meilleures que les miennes, s'ils sont autorisés.
ah gamma. Une constante proche de mon coeur!
Ugh, c'est deux réponses dans un poste. upvote est pour la formule contenant de la gamma. La chose du journal (exp ...) ne va pas aider, car il a le même problème de perte de bits tout en accumulant de nombreuses valeurs.
Comme tous vos chiffres sont des rationnels, le plus facile (et peut-être le plus rapide, comme il devra faire moins d'opérations de point variant) serait de faire les calculs avec des rationnels (tuples de 2 entiers P, Q), puis Faites une seule division de points flottants à la fin.
Mise à jour Pour utiliser cette technique, vous devrez utiliser efficacement les Bigints pour P & Q, car ils se développent assez rapidement ... < p> Un prototype rapide dans Lisp, qui a construit en rationns montre: Ainsi, la prochaine option meilleure pourrait être de manipuler la liste des points flottants et de la réduire les deux plus petits nombres dans chaque étape ...
Cela pourrait être délicat. Je pense que vous auriez besoin de faire le dénominateur le produit de tous les nombres 1 à N afin de pouvoir les ajouter correctement. Cela signifie n! qui fonctionnerait de 32 bits int très rapidement.
Vous n'avez pas essayé cela, avez-vous? Le dénominateur pousse très vite, il est n! Pour n. Vous devez utiliser une implémentation de BigInteger.
C'est vrai ... Je pensais que peut-être qu'il y avait des diviseurs communs en cours de route qui pourraient simplifier la fraction ... Je vais l'essayer dans Lisp qui a des fractionnaires intégrés.
Je ne sais même pas où commencer.
ici: Ce que chaque scientifique doit savoir sur l'arithmétique de point flottant
Il aurait été plus utile de lier directement à la section la plus pertinente de cet article, à savoir la section sur les optimiseurs et la formule de sommation de Kahan: docs.sun.com/source/806-3568/ncg_goldberg.html#1070
En réalité, si vous faites la sommation pour le grand N, l'addition de la plus petite au plus grande n'est pas la meilleure solution - vous pouvez toujours entrer dans une situation où les chiffres que vous ajoutez sont trop petits par rapport à la somme pour produire un résultat précis.
Regardez le problème de cette façon: vous avez n sommation, quelle que soit la commande, et que vous souhaitez avoir l'erreur la moins totale. Ainsi, vous devriez pouvoir obtenir l'erreur la moins totale en minimisant l'erreur de chaque sommation - et vous minimisez l'erreur dans une somme en ajoutant des valeurs aussi proches les unes des autres que possible. Je crois que la suite de cette chaîne de logique vous donne un arbre binaire de sommes partielles:
et ainsi de suite jusqu'à ce que vous arriviez à une seule réponse.
Bien sûr, lorsque N n'est pas une puissance de deux, vous vous retrouverez avec des restes à chaque étape, que vous devez emporter dans les sommations à la prochaine étape.
(les marges de Stackoverflow sont bien sûr trop petites pour inclure une preuve que celle-ci est optimale. En partie parce que je n'ai pas pris le temps de le prouver. Mais cela fonctionne pour tout N, aussi grand, comme tous les Les ajouts ajoute des valeurs d'une magnitude presque identique. Eh bien, tout sauf journal (n) d'entre eux dans le pire non-Power-of-2 cas, et qui est trop petit par rapport à n.) somme [0, i] = valeur [i]
somme [1, i / 2] = somme [0, i] + somme [0, i + 1]
somme [j + 1, i / 2] = somme [j, i] + somme [j, i + 1]
Sauf si vous utilisez une représentation précise de forme fermée, une sommation ordonnée de petite taille est susceptible d'être une solution simple la plus précise (ce n'est pas clair pour moi pourquoi un journal d'identité aiderait - c'est une astuce soignée, mais vous «Ne rien gagnez avec cela ici, autant que je puisse dire).
Vous pouvez accroître encore une précision en réalisant qu'après un moment, la somme deviendra "quantifiée": efficacement, lorsque vous avez 2 chiffres de précision, l'ajout de 1,3 à 41 résultats en 42, pas 42,3 - mais vous obtenez presque une précision doubler en maintenant une «erreur». C'est ce qu'on appelle Sommation de Kahan . Vous devriez calculer le terme d'erreur (42-41-1.3 == -0,3) et corrigez que dans l'ajout suivant en ajoutant 0,3 au terme suivant avant de l'ajouter à nouveau.
Sommation de Kahan En plus d'une commande de petite à une grande commande est susceptible d'être aussi précise que vous aurez jamais besoin d'obtenir. Je doute sérieusement que vous auriez déjà besoin de quelque chose de mieux pour la série harmonique - après tout, même après 2 ^ 45 itérations (beaucoup de folles), vous ne traiteriez toujours qu'un chiffre d'au moins 1/2 ^ 45 grand, et une somme qui est de l'ordre de 45 (<2 ^ 6), pour une différence d'ordre de magnitude de 51 puissances de deux - c'est-à-dire encore toujours représentables dans une variable de précision à double précision si vous ajoutez dans le "mauvais" ordre.
Si vous allez de petite taille et utilisez la somme de Kahan, le soleil va probablement éteindre avant que les processeurs d'aujourd'hui atteignent un pourcentage d'erreur - et vous rencontrerez d'autres problèmes de précision délicats simplement en raison de l'erreur de terme individuelle sur cette échelle d'abord de toute façon (étant qu'un certain nombre de l'ordre de 2 ^ 53 ou plus ne peut pas être représenté avec précision comme un double du tout.)
(Notez que vous devrez peut-être faire attention aux paramètres d'optimisation si vous utilisez Sommation de Kahan, comme un compilateur pourrait le réécrire autrement dans l'oubli).
Essayez-vous de calculer pour un n ou pour n = infini. Si ce dernier, utilisez simplement x = 2; :-)
@Pax: La somme à l'infini de cette série est infinie.
Et une chose que j'ai oubliée: comment calculer la valeur "précise" exacte de la somme? Ce n'est pas défini aussi.
@Pax: Non, la somme est divergente, elle doit donc être pour un n. Vous pensez à 1 + 1/2 + 1/4 + ... + 1 / N ^ 2
Ah, excuses, je pensais que c'était le 1,2,4,8, ... séquence que vous vouliez, pas 1,2,3,4, ...
Oh, il est assez bien défini, soit par la définition du numéro harmonique, soit par une série Taylor. Regarde ma réponse.