30

Sasume (./26) :
Oui mais là je ne calcule qu’une seule fois la racine carrée, avant la boucle et j’utilise la valeur dans le test de boucle.

J'espere que ton compilateur sait optimiser ca tout seul quand meme!
avatar
I'm on a boat motherfucker, don't you ever forget

31

Ce n'est pas si évident que ça, sqrt est une fonction, le compilateur ne sait pas forcément qu'elle est "pure" (sans effets de bord).
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

32

Au fait, est-ce qu’on n’a pas divisors(n(n+1)) = 2 * divisors(n(n+1)/2) + 1 ?
avatar
« Quand le dernier arbre sera abattu, la dernière rivière empoisonnée, le dernier poisson capturé, alors vous découvrirez que l'argent ne se mange pas. »

33

Kevin Kofler (./31) :
Ce n'est pas si évident que ça, sqrt est une fonction, le compilateur ne sait pas forcément qu'elle est "pure" (sans effets de bord).

Même s'il sait que c'est ue fonction qu'il peut traiter en une instruction ?

34

Ben je ne pense pas que le compilo "réfléchisse" jusque là.
avatar
Zeroblog

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo

35

./33 & ./34 > Sisi, mais pas avec tous les paramètres de compilation. Peut-être pas avec tous les compilateurs non plus, mais bon nombre de fonctions sont sujettes à un traitement spécial. Par exemple GCC peut aller vérifier (compile-time donc) la chaîne de format que tu files à printf, et les fonctions sur les nombres à virgule flottante peuvent être optimisées en instructions natives sur le CPU. (Evidemment ça ne peut pas marcher avec tous les CPU, ni tous les modèles de CPU, donc c'est optionnel)
(Et ce sont des fonctions bien définies (runtime c) donc connues à l'avance… Pas des fonctions utilisateurs où le compilateur a besoin du code source pour optimiser (e.g. fonctions inline))
avatar
Le scénario de notre univers a été rédigée par un bataillon de singes savants. Tout s'explique enfin.
T'as un problème ? Tu veux un bonbon ?
[CrystalMPQ] C# MPQ Library/Tools - [CrystalBoy] C# GB Emulator - [Monoxide] C# OSX library - M68k Opcodes

36

Il s'agit donc d'une optimisation peephole pour mieux tirer parti d'un processeur qui en est capable, c'est ça ? A moins que ce type d'optimisation désigne une optimisation toujours applicable pour un motif de code donné ?

37

Sasume (./32) :
Au fait, est-ce qu’on n’a pas divisors(n(n+1)) = 2 * divisors(n(n+1)/2) + 1 ?
Euh... divisors(1×2) = 2 est différent de 2×divisors(1×2/2)+1 qui vaut 3
divisors(2×3) = 4 est différent de 2×divisors(2×3/2)+1 qui vaut 5
etc.
donc je me demande d'où t'est venue l'idée de poser cette question ?

En fait ta formule n'est vérifiée dans absolument aucun cas (en effet le nombre de diviseurs d'un nombre n'est impair que s'il s'agit d'un carré parfait, ce qui n'est jamais le cas de n(n+1). Enfin sauf si n = 0 mais là le nombre de diviseurs est infini)
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#

38

Soit k = n(n+1)/2.
Je me suis dit que les diviseurs de 2×k contiendraient 2 et toutes les combinaisons de 2 avec les autres diviseurs, soit autant que de diviseurs de k.

Mais c’est vrai que j’aurais quand même pu tester avec quelques cas avant de proposer l’idée roll
avatar
« Quand le dernier arbre sera abattu, la dernière rivière empoisonnée, le dernier poisson capturé, alors vous découvrirez que l'argent ne se mange pas. »

39

Sinon, pour info il y a une solution encore plus rapide que celle avancée par Kevin (tu me déçois… embarrassed).

Considérons la suite 1 1 3 2 5 3 7 …
Elle est constitué des entiers naturels où les nombres pairs sont divisés par 2.

En prenant le produit de deux termes successifs de cette suite on obtient un terme de la série n(n+1)/2. Les deux termes de notre suite sont premiers entre eux donc pour obtenir les diviseurs de leur produit il suffit de multiplier leur nombre de diviseurs à chacun entre eux.

Pas besoin de trouver de m, comme dans la solution de Kevin !
avatar
« Quand le dernier arbre sera abattu, la dernière rivière empoisonnée, le dernier poisson capturé, alors vous découvrirez que l'argent ne se mange pas. »

40

Sasume (./38) :
Je me suis dit que les diviseurs de 2×k contiendraient 2 et toutes les combinaisons de 2 avec les autres diviseurs, soit autant que de diviseurs de k.
Alors déjà ça ne pourrait marcher que si k est impair, sinon tu recomptes plein de diviseurs du produit qui étaient déjà des diviseurs de k. Ensuite, même dans ce cas il ne faut pas oublier que l'un des diviseurs de k est le nombre 1. Par conséquent « toutes les combinaisons de 2 avec les autres diviseurs » ça contient entre autres le nombre 2×1, donc tu ne dois pas recompter 2 comme un diviseur de plus.

Mais sinon c'est l'idée de la formule que Kevin a donnée en ./22 ; simplement comme il faut obligatoirement un nombre impair¹ il décompose d'abord ton nombre k sous la forme une puissance de 2 fois un nombre impair. Ensuite seulement tu peux raisonner sur la relation entre divisors(k) et divisors(2k).

¹plus généralement, pour pouvoir compter séparément les diviseurs de deux facteurs de ton nombre et multiplier ces nombres pour avoir le total des combinaisons, il faut que ces deux facteurs soient premiers entre eux, c'est-à-dire que leur seul diviseur commun soit 1 (comme ça tu es sûr que rien n'est compté deux fois). Ce que Kevin a exprimé en disant que leur pgcd (Plus Grand Commun Diviseur) doit être égal à 1 : si 1 est le plus grand, c'est que c'est le seul.
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#

41

Sasume (./32) :
Au fait, est-ce qu’on n’a pas divisors(n(n+1)) = 2 * divisors(n(n+1)/2) + 1 ?

Non.
divisors(4*5)=divisors(20)=|{1,2,4,5,10,20}|=6 qui est pair et ne peut pas être égal à 2 divisors(10)+1.
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

42

Tiens sinon le problème posé a un rapport avec ça : http://fr.wikipedia.org/wiki/Nombre_hautement_composé
En regardant la liste des premiers nombres, on comprent pourquoi on divise les jours en 24 heures de 60 minutes et les angles en 360 degrés (et on comprend aussi l'avantage de ceci tripo)

Kevin > ./37 ? cheeky
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#