Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > fr.comp.lang.python > #3861 > unrolled thread

Autre exercice : calculer la somme de x chiffres.

Back to article view | Back to fr.comp.lang.python

Contents

  Autre exercice : calculer la somme de x chiffres. Dominique <zzz@aol.com.invalid> - 2022-05-22 17:00 +0200
    Re: Autre exercice : calculer la somme de x chiffres. Dominique <zzz@aol.com.invalid> - 2022-05-22 17:11 +0200
      Re: Autre exercice : calculer la somme de x chiffres. Damien Wyart <damien.wyart@free.fr> - 2022-05-23 09:36 +0200
        Re: Autre exercice : calculer la somme de x chiffres. Dominique <zzz@aol.com.invalid> - 2022-05-23 18:38 +0200
      Re: Autre exercice : calculer la somme de x chiffres. Benoit Izac <use.reply.to@INVALID.ADDRESS> - 2022-05-23 10:58 +0200
        Re: Autre exercice : calculer la somme de x chiffres. Alain Ketterlin <alain@universite-de-strasbourg.fr.invalid> - 2022-05-23 12:56 +0200
          Re: Autre exercice : calculer la somme de x chiffres. Benoit Izac <use.reply.to@INVALID.ADDRESS> - 2022-05-23 14:20 +0200
            Re: Autre exercice : calculer la somme de x chiffres. Dominique <zzz@aol.com.invalid> - 2022-05-23 18:37 +0200
            Re: Autre exercice : calculer la somme de x chiffres. Alain Ketterlin <alain@universite-de-strasbourg.fr.invalid> - 2022-05-24 14:33 +0200
              Re: Autre exercice : calculer la somme de x chiffres. Benoit Izac <use.reply.to@INVALID.ADDRESS> - 2022-05-24 20:50 +0200
                Re: Autre exercice : calculer la somme de x chiffres. Nicolas <nicolasp@aaton.com> - 2022-05-25 08:51 +0200
                  Re: Autre exercice : calculer la somme de x chiffres. Benoit Izac <use.reply.to@INVALID.ADDRESS> - 2022-05-25 14:04 +0200
                    Re: Autre exercice : calculer la somme de x chiffres. Nicolas <nicolasp@aaton.com> - 2022-05-25 14:45 +0200
                Re: Autre exercice : calculer la somme de x chiffres. Alain Ketterlin <alain@universite-de-strasbourg.fr.invalid> - 2022-05-25 13:41 +0200
                  Re: Autre exercice : calculer la somme de x chiffres. Benoit Izac <use.reply.to@INVALID.ADDRESS> - 2022-05-25 13:57 +0200
                    Re: Autre exercice : calculer la somme de x chiffres. Alain Ketterlin <alain@universite-de-strasbourg.fr.invalid> - 2022-05-25 16:10 +0200
              Re: Autre exercice : calculer la somme de x chiffres. Olivier Miakinen <om+news@miakinen.net> - 2022-05-25 09:31 +0200
                Re: Autre exercice : calculer la somme de x chiffres. Alain Ketterlin <alain@universite-de-strasbourg.fr.invalid> - 2022-05-25 13:25 +0200
          Re: Autre exercice : calculer la somme de x chiffres. Dominique <zzz@aol.com.invalid> - 2022-05-23 18:42 +0200

#3861 — Autre exercice : calculer la somme de x chiffres.

Je trouve ce script qui fonctionne très bien et qui est en accord avec 
(n²+n)/2 :

def addition(x):
     return sum([i for i in range(0,x+1)])
print (addition(int(input('Fin de la sommielle '))))

Est-ce propre ?

Chercher la concision à tout prix est-ce un bon pari ? Je suis de 
l'ancienne école : j'ai commencé à programmer avec un Sharp PC1211 qui 
avait 1 KO de RAM. On apprenait à compacter...

Merci pour votre éclairage,

Dominique

[toc] | [next] | [standalone]

#3862

Le 22/05/2022 à 17:00, Dominique a écrit :

Inutile de passer par une composition de liste :

def addition(x):

     return sum(range(x+1))

print (addition(int(input('Fin de la sommielle '))))

Difficile sans doute d'être plus concis...

[toc] | [prev] | [next] | [standalone]

#3863

* Dominique <zzz@aol.com.invalid> in fr.comp.lang.python:
> Inutile de passer par une composition de liste :

> def addition(x):
>     return sum(range(x+1))

> print (addition(int(input('Fin de la sommielle '))))

> Difficile sans doute d'être plus concis...

Je trouve qu'imbriquer tous les appels n'est pas très lisible ; je
proposerais plutôt :

def sum_of_first_ints(n):
    return sum(range(n+1))

N = int(input("Please enter an integer: "))

print("The sum from 1 to", N, "is", sum_of_first_ints(N))

-- 
DW

[toc] | [prev] | [next] | [standalone]

#3873

Le 23/05/2022 à 09:36, Damien Wyart a écrit :

> 
> print("The sum from 1 to", N, "is", sum_of_first_ints(N))
> 

Cette présentation est intéressante. Je me la garde :-)

Merci,

Dominique

[toc] | [prev] | [next] | [standalone]

#3865

Bonjour,

Le 22/05/2022 à 17:11, Dominique a écrit dans le message
<t6djq7$1570$1@gioia.aioe.org> :

> Inutile de passer par une composition de liste :
>
> def addition(x):
>
>     return sum(range(x+1))
>
> print (addition(int(input('Fin de la sommielle '))))
>
> Difficile sans doute d'être plus concis...

Mais on peut faire mieux en terme d'algorithme :

def accumulate_sum_of(n):
    return (n + 1) // 2 * (n + (n + 1) % 2)

Ce qui fait du O(1) au lieu du O(n).

-- 
Benoit Izac

[toc] | [prev] | [next] | [standalone]

#3867

Benoit Izac <use.reply.to@INVALID.ADDRESS> writes:

> Le 22/05/2022 à 17:11, Dominique a écrit dans le message
> <t6djq7$1570$1@gioia.aioe.org> :
>
>> Inutile de passer par une composition de liste :
>>
>> def addition(x):
>>
>>     return sum(range(x+1))
>>
>> print (addition(int(input('Fin de la sommielle '))))
>>
>> Difficile sans doute d'être plus concis...
>
> Mais on peut faire mieux en terme d'algorithme :
>
> def accumulate_sum_of(n):
>     return (n + 1) // 2 * (n + (n + 1) % 2)

Hmm, pourquoi pas simplement n * (n+1) // 2 ? (Ou (n+1)*(n+2)//2 si on
veut la somme jusqu'à n+1.)

-- Alain.

[toc] | [prev] | [next] | [standalone]

#3870

Bonjour,

Le 23/05/2022 à 12:56, Alain Ketterlin a écrit dans le message
<877d6czfdn.fsf@universite-de-strasbourg.fr.invalid> :

>>> Inutile de passer par une composition de liste :
>>>
>>> def addition(x):
>>>
>>>     return sum(range(x+1))
>>>
>>> print (addition(int(input('Fin de la sommielle '))))
>>>
>>> Difficile sans doute d'être plus concis...
>>
>> Mais on peut faire mieux en terme d'algorithme :
>>
>> def accumulate_sum_of(n):
>>     return (n + 1) // 2 * (n + (n + 1) % 2)
>
> Hmm, pourquoi pas simplement n * (n+1) // 2 ? (Ou (n+1)*(n+2)//2 si on
> veut la somme jusqu'à n+1.)

Parce que c'est toujours plus compliqué de faire simple. ;-)

-- 
Benoit Izac qui n'a s'en doute pas assez réfléchi au problème

[toc] | [prev] | [next] | [standalone]

#3872

Le 23/05/2022 à 14:20, Benoit Izac a écrit :
> Bonjour,
> 
> Le 23/05/2022 à 12:56, Alain Ketterlin a écrit dans le message
> <877d6czfdn.fsf@universite-de-strasbourg.fr.invalid> :
> 
>>>> Inutile de passer par une composition de liste :
>>>>
>>>> def addition(x):
>>>>
>>>>      return sum(range(x+1))
>>>>
>>>> print (addition(int(input('Fin de la sommielle '))))
>>>>
>>>> Difficile sans doute d'être plus concis...
>>>
>>> Mais on peut faire mieux en terme d'algorithme :
>>>
>>> def accumulate_sum_of(n):
>>>      return (n + 1) // 2 * (n + (n + 1) % 2)
>>
>> Hmm, pourquoi pas simplement n * (n+1) // 2 ? (Ou (n+1)*(n+2)//2 si on
>> veut la somme jusqu'à n+1.)
> 
> Parce que c'est toujours plus compliqué de faire simple. ;-)
> 


J'avais bien pensé à aller au plus court avec (n2+n)/2. Mais l'exercice 
voulait qu'on balaye la plage de 1 à n :-)

[toc] | [prev] | [next] | [standalone]

#3875

Benoit Izac <use.reply.to@INVALID.ADDRESS> writes:

>>> def accumulate_sum_of(n):
>>>     return (n + 1) // 2 * (n + (n + 1) % 2)
>>
>> Hmm, pourquoi pas simplement n * (n+1) // 2 ?
>
> Parce que c'est toujours plus compliqué de faire simple. ;-)

Cela étant, ta version est mieux adaptée aux contextes où la précision
est limitée, parce qu'elle évite les overflows quand n*(n+1) n'est pas
représentable mais que n*(n+1)/2 l'est.

(Ça ne concerne pas Python, mais c'est la même idée qu'un bug qui a été
célèbre en Java, dont la correction a consisté à remplacer (a+b)/2 par
a + (b-a)/2.)

-- Alain.

[toc] | [prev] | [next] | [standalone]

#3876

Bonjour,

Le 24/05/2022 à 14:33, Alain Ketterlin a écrit dans le message
<87zgj7xg89.fsf@universite-de-strasbourg.fr.invalid> :

> (Ça ne concerne pas Python, mais c'est la même idée qu'un bug qui a été
> célèbre en Java, dont la correction a consisté à remplacer (a+b)/2 par
> a + (b-a)/2.)

Il y a intérêt a avoir un beau commentaire juste à côté car il y a fort
à parier que quelqu'un qui passe sur le code sans être courant risque de
simplifier (et c'est logique).

Question bête : si c'est (a+b) qui provoque le dépassement, pourquoi pas
« a/2 + b/2 » ? Perte de précision ?

Et pour ma culture, il vient d'où ce bug ?

-- 
Benoit Izac

[toc] | [prev] | [next] | [standalone]

#3877

Bonjour,

Le 24/05/2022 à 20:50, Benoit Izac a écrit :
> Bonjour,
> 
> Le 24/05/2022 à 14:33, Alain Ketterlin a écrit dans le message
> <87zgj7xg89.fsf@universite-de-strasbourg.fr.invalid> :
> 
>> (Ça ne concerne pas Python, mais c'est la même idée qu'un bug qui a été
>> célèbre en Java, dont la correction a consisté à remplacer (a+b)/2 par
>> a + (b-a)/2.)
> 
> Il y a intérêt a avoir un beau commentaire juste à côté car il y a fort
> à parier que quelqu'un qui passe sur le code sans être courant risque de
> simplifier (et c'est logique).
> 
> Question bête : si c'est (a+b) qui provoque le dépassement, pourquoi pas
> « a/2 + b/2 » ? Perte de précision ?
Tout à fait.

Avec des calculs sur des entiers :

(5 + 7) // 2 = 12 // 2 = 6

(5//2) + (7//2) = 2 + 3 = 5


Note : J'ai mis la notation Python pour du calcul sur les entiers, pas 
la notation mathématique (qui ne se différencie pas de la notation des 
calculs sur les réels).

> 
> Et pour ma culture, il vient d'où ce bug ?
> 
Ce "bug" n'existe pas avec les versions de Python qui font du calcul sur 
des entiers de taille indéfinie.

Il ne s'agit en fait pas d'un bug au sens que l'on donne à ce terme 
habituellement mais du fonctionnement des processeurs depuis l'origine 
de leur création.

Pour simplifier, disons que nous utilisons un processeur 8 bits. Les 
nombres manipulés par ce processeur, avec des entiers positifs, vont de 
0 à (2**8)-1.
En binaire : 00000000 à 11111111
En décimal : 0 à 255

Soit une variable V qui contient la valeur 240 (11110000 en binaire).
Ajoutons la valeur 16 :
V = V + 20

En binaire, cela donne :
   11110000
+ 00010100
----------
  100000100

Le résultat est sur 9 bits. Comme le processeur ne sait manipuler que 
des nombres sur 8 bits, le résultat est tronqué à 8 bits ce qui donne 4.

Pour reprendre le problème d'origine (avec des nombres sur 8 bits) :

(130 + 200) / 2 = 300 /2 -> 44 / 2 = 22	==> !!! BUG !!!

130 + (200-130) / 2 = 130 + 70 / 2 = 165 ==> OK


Les processeurs actuels manipulent des nombres sur 32 bits ou 64 bits 
(voire plus) ce qui permet une plus grande latitude d'utilisation mais 
le phénomène de troncature est toujours présent.

J'espère avoir été clair dans mes explications ;)

Bonne journée,
Nicolas

[toc] | [prev] | [next] | [standalone]

#3882

Bonjour,

Le 25/05/2022 à 08:51, Nicolas a écrit dans le message
<628dd1d5$0$2996$426a74cc@news.free.fr> :

> J'espère avoir été clair dans mes explications ;)

Très clair mais je savais déjà ce qu'était un overflow, je voulais juste
savoir où était le bug dans la bibliothèque standard de Java. Réponse :
binarySearch() du module java.util.Arrays.

-- 
Benoit Izac

[toc] | [prev] | [next] | [standalone]

#3883

Le 25/05/2022 à 14:04, Benoit Izac a écrit :
> Bonjour,
> 
> Le 25/05/2022 à 08:51, Nicolas a écrit dans le message
> <628dd1d5$0$2996$426a74cc@news.free.fr> :
> 
>> J'espère avoir été clair dans mes explications ;)
> 
> Très clair mais je savais déjà ce qu'était un overflow, je voulais juste
> savoir où était le bug dans la bibliothèque standard de Java. Réponse :
> binarySearch() du module java.util.Arrays.
> 

Ha bah mince alors.
Bon, ben mon message pourra éventuellement éclairer quelqu'un d'autre...

[toc] | [prev] | [next] | [standalone]

#3880

Benoit Izac <use.reply.to@INVALID.ADDRESS> writes:

>> (Ça ne concerne pas Python, mais c'est la même idée qu'un bug qui a été
>> célèbre en Java, dont la correction a consisté à remplacer (a+b)/2 par
>> a + (b-a)/2.)
>
> Il y a intérêt a avoir un beau commentaire juste à côté car il y a fort
> à parier que quelqu'un qui passe sur le code sans être courant risque de
> simplifier (et c'est logique).
>
> Question bête : si c'est (a+b) qui provoque le dépassement, pourquoi pas
> « a/2 + b/2 » ? Perte de précision ?

Oui, parce que dans ce cas le milieu de 3 et 5 est 3 (3//2 == 1 et 5//2
= 2), ce qui n'est pas utile dans les algos dichotomiques.

(Si tu penses à la division flottante, alors tu as un problème encore
plus grave, puisqu'on a alors en général seulement 53 bits de précision
-- pour les double IEEE 754. Sans compter les blagues du genre
0.1+0.1+0.1 != 0.3)

> Et pour ma culture, il vient d'où ce bug ?

Voici ce que j'ai trouvé de plus ancien sur le bug dans la bibliothèque
standard de Java :

https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html

-- Alain.

[toc] | [prev] | [next] | [standalone]

#3881

Bonjour,

Le 25/05/2022 à 13:41, Alain Ketterlin a écrit dans le message
<87r14hyh3a.fsf@universite-de-strasbourg.fr.invalid> :

>>> (Ça ne concerne pas Python, mais c'est la même idée qu'un bug qui a été
>>> célèbre en Java, dont la correction a consisté à remplacer (a+b)/2 par
>>> a + (b-a)/2.)
>>
>> Il y a intérêt a avoir un beau commentaire juste à côté car il y a fort
>> à parier que quelqu'un qui passe sur le code sans être courant risque de
>> simplifier (et c'est logique).
>>
>> Question bête : si c'est (a+b) qui provoque le dépassement, pourquoi pas
>> « a/2 + b/2 » ? Perte de précision ?
>
> Oui, parce que dans ce cas le milieu de 3 et 5 est 3 (3//2 == 1 et 5//2
> = 2), ce qui n'est pas utile dans les algos dichotomiques.
>
> (Si tu penses à la division flottante, alors tu as un problème encore
> plus grave, puisqu'on a alors en général seulement 53 bits de précision
> -- pour les double IEEE 754. Sans compter les blagues du genre
> 0.1+0.1+0.1 != 0.3)

En fait, j'étais focalisé sur la division flottante. Pour la division
entière c'est plus évident.

>> Et pour ma culture, il vient d'où ce bug ?
>
> Voici ce que j'ai trouvé de plus ancien sur le bug dans la bibliothèque
> standard de Java :
>
> https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html

Je vois, du coup les autres qui ont fait des bibliothèques dans d'autres
langages (C par exemple) ont rencontrés le même problème (bien avant
Java).

-- 
Benoit Izac

[toc] | [prev] | [next] | [standalone]

#3884

Benoit Izac <use.reply.to@INVALID.ADDRESS> writes:

>> Voici ce que j'ai trouvé de plus ancien sur le bug dans la bibliothèque
>> standard de Java :
>>
>> https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html
>
> Je vois, du coup les autres qui ont fait des bibliothèques dans d'autres
> langages (C par exemple) ont rencontrés le même problème (bien avant
> Java).

Oh oui. En C le problème est doublé, parce que l'overflow sur le type
int provoque un comportement indéfini. Mais de toute façon, le problème
s'était posé il y a longtemps, quand les fichiers ont pu avoir une
taille supérieure à 2^31, et donc toutes les tailles et position doivent
être de type size_t (avec les variantes POSIX dans sys/types.h).

-- Alain.

[toc] | [prev] | [next] | [standalone]

#3878

Le 24/05/2022 14:33, Alain Ketterlin a écrit :
> 
> Cela étant, ta version est mieux adaptée aux contextes où la précision
> est limitée, parce qu'elle évite les overflows quand n*(n+1) n'est pas
> représentable mais que n*(n+1)/2 l'est.
> 
> (Ça ne concerne pas Python, mais c'est la même idée qu'un bug qui a été
> célèbre en Java, dont la correction a consisté à remplacer (a+b)/2 par
> a + (b-a)/2.)

Et là, si on prend pour a et b un très grand nombre positif et un très
grand nombre négatif, c'est la correction qui fait planter alors que la
version d'origine fonctionne très bien. ;-)


-- 
Olivier Miakinen

[toc] | [prev] | [next] | [standalone]

#3879

Olivier Miakinen <om+news@miakinen.net> writes:

> Le 24/05/2022 14:33, Alain Ketterlin a écrit :
>> 
>> Cela étant, ta version est mieux adaptée aux contextes où la précision
>> est limitée, parce qu'elle évite les overflows quand n*(n+1) n'est pas
>> représentable mais que n*(n+1)/2 l'est.
>> 
>> (Ça ne concerne pas Python, mais c'est la même idée qu'un bug qui a été
>> célèbre en Java, dont la correction a consisté à remplacer (a+b)/2 par
>> a + (b-a)/2.)
>
> Et là, si on prend pour a et b un très grand nombre positif et un très
> grand nombre négatif, c'est la correction qui fait planter alors que la
> version d'origine fonctionne très bien. ;-)

Oui, tu as tout à fait raison : on ne peut pas avoir le beurre et
l'argent du beurre.

J'aurais du préciser que le bug auquel je faisais allusion concernait la
recherche dichotomique dans un très grand tableau, et donc mettant en
jeu des valeurs positives uniquement. Voici une description

https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html

Il semble que le rapport de bug original (du temps ou Sun Microsystems
s'occupait de Java) est perdu...

-- Alain.

[toc] | [prev] | [next] | [standalone]

#3874

Le 23/05/2022 à 12:56, Alain Ketterlin a écrit :

> 
> Hmm, pourquoi pas simplement n * (n+1) // 2 ? (Ou (n+1)*(n+2)//2 si on
> veut la somme jusqu'à n+1.)


J'y ai bien pensé, mais l'exercice ne voulait pas de cette solution :-) 
Au passage, elle ne fonctionne que pour une plage de 1 à n, pas de x 
(1<x<n) jusqu'à n. De plus, elle est plus compliquée à gérer si on veut 
ne travailler que sur une valeur sur deux : 1, 3, 5 ou 2, 4, 6...

Merci à vous tous,

Dominique

[toc] | [prev] | [standalone]

Back to top | Article view | fr.comp.lang.python

csiph-web