Discussion :

[Virgile le chat]

Bonjour,
Dans tous les cours de complexité algorithmique, on trouve que le temps d'exécution d'une somme de deux entiers m et n est proportionnel à la taille de ces entiers. Plus précisément, le temps est proportionnel à max( Log2(m), Log2(n) ). Or quand je teste, j'obtiens un temps constant, indépendant de la taille des entiers.
Quelqu'un aurait-il une explication ?
Merci bien.

[Clodion]

Bonjour,
Dans tous les cours de complexité algorithmique, on trouve que le temps d'exécution d'une somme de deux entiers m et n est proportionnel à la taille de ces entiers. Plus précisément, le temps est proportionnel à max( Log2(m), Log2(n) ). Or quand je teste, j'obtiens un temps constant, indépendant de la taille des entiers.
Quelqu'un aurait-il une explication ?
Merci bien.

Bonjour,
N'étant pas du tout spécialiste, pas de réponse définitive.
Mais, il me semblait que l'addition d'entiers se faisait en un cycle d'horloge… Après, il faudrait voire sur quelle gamme d'entier est sous-entendu cette affirmation.
De même, avec les unités math, la plupart des multiplications (au moins dans certaines gammes) ne doivent pas non plus prendre plus de temps (toujours sous les mêmes conditions).

Est-il possible de savoir d'où vient cette affirmation?

Clodion

[Biribibi]

Je rajouterai que l'addition d'entiers se faisant en un cycle d'horloge n'est vrai que pour les entiers tenant dans un registre du processeur donc inférieurs à 2^64 pour un processeur 64 bits.
Or Python gère les entiers de taille arbitrairement grande.
Pour faire l'addition de grands entiers (ne tenant pas sur un registre), il faut découper les entiers en blocs de 64 bits et faire la somme bloc par bloc ce qui explique la complexité en temps max( Log2(m), Log2(n) ).

[Clodion]

Je rajouterai que l'addition d'entiers se faisant en un cycle d'horloge n'est vrai que pour les entiers tenant dans un registre du processeur donc inférieurs à 2^64 pour un processeur 64 bits.
Or Python gère les entiers de taille arbitrairement grande.
Pour faire l'addition de grands entiers (ne tenant pas sur un registre), il faut découper les entiers en blocs de 64 bits et faire la somme bloc par bloc ce qui explique la complexité en temps max( Log2(m), Log2(n) ).

Bonsoir,
Oui, sans doutes… Quoique, les fpu ne sont pas du tout utilisés pour les entiers?
D'autre part cela fait un bon moment que les cpu font de l'optimisation de code… Donc bon, pour mesurer cela… :-(

En particulier en Python, je ne sais pas comment il est possible de mesurer, car "timeit" ne voit pas trop la différence:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
from timeit import timeit
def compte():
    for cpt in range(2**8):
        x = 2**(2**cpt)
        y = x + 1
        print("2^", (2**cpt), "\t", timeit("x + y",
                setup = "from __main__ import x, y", number = 100000000))
 
x = y = 0
# Tests
if __name__=="__main__":
    compte()

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
Python 3.3.1 (default, Sep 25 2013, 19:29:01) 
[GCC 4.7.3] on linux
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>> 
2^ 1 	 6.609399238997867
2^ 2 	 6.579540694998286
2^ 4 	 6.567646725001396
2^ 8 	 6.734527710999828
2^ 16 	 6.581780365002487
2^ 32 	 6.547674912999355
2^ 64 	 6.720862008998665
2^ 128 	 6.58790963499996
2^ 256 	 6.57463895500041
2^ 512 	 6.582332669997413
2^ 1024 	 6.714150540999981
2^ 2048 	 6.564520908999839
2^ 4096 	 6.595583796002757
2^ 8192 	 6.7459448049994535
2^ 16384 	 6.597321725999791
2^ 32768 	 6.5872846960010065
2^ 65536 	 6.730992066997715
2^ 131072 	 6.5998513770027785
2^ 262144 	 6.595837459000904
2^ 524288 	 6.739885096998478
2^ 1048576 	 6.575958954999805
2^ 2097152 	 6.598494779998873
2^ 4194304 	 6.745096653001383
2^ 8388608 	 6.745996486999502
2^ 16777216 	 6.747960983000667
2^ 33554432 	 6.587806830000773
2^ 67108864 	 6.573335715998837
2^ 134217728 	 6.735632599997189
2^ 268435456 	 6.606245205999585
2^ 536870912 	 6.590101533998677
2^ 1073741824 	 6.740713413997582
2^ 2147483648 	 6.586884087002545
2^ 4294967296 	 6.5960511729972495
2^ 8589934592 	 6.823408839998592
 
KeyboardInterrupt
>>>

PS: j'ai stoppé avant la fin, car c'est ma mémoire qui ne gérait plus du tout…
2^8589934592, cela commence à faire un paquet de chiffres (on doit être à plusieurs milliards)!

Si quelqu'un a des informations, il est le bienvenu!
Clodion

[marco056]

Bonjour,
Dans tous les cours de complexité algorithmique, on trouve que le temps d'exécution d'une somme de deux entiers m et n est proportionnel à la taille de ces entiers. Plus précisément, le temps est proportionnel à max( Log2(m), Log2(n) ). Or quand je teste, j'obtiens un temps constant, indépendant de la taille des entiers.
Quelqu'un aurait-il une explication ?
Merci bien.

Pourrais-tu donner ton OS et fournir ton script ? (Je pense à un souci avec time : time.time et time.clock diffèrent mais j'ai la flemme de m'y pencher pour l'instant, surtout si tu as utilisé autre chose.