Bon, comme je galère comme un noob et que mes potes normaliens se sont aussi cassé les dents sur ce problème (bon, peut-être que je le leur ai mal expliqué aussi), j’implore votre aide !

Le problème à résoudre est donné ici : http://projecteuler.net/index.php?section=problems&id=12

Mon implémentation naïve, en O(N²), en C :

Quand, à la place du 500, je mets 300, ça va encore, mais dès que je dépasse 320 mon PC explose… Je me dis qu’il doit donc y avoir des astuces arithmétiques pour simplifier les calculs.

Les nombres dont on cherche à connaître le nombre de diviseurs sont de la forme , peut-être que ça peut simplifier le calcul du nombre de diviseurs ?

De même, ma stratégie pour calculer le nombre de diviseurs d’un nombre n est très naïve, elle consiste simplement à essayer tous les nombres entre 1 et n / 2, il y a peut-être moyen d’aller plus vite ?

Sasume (./0) :
De même, ma stratégie pour calculer le nombre de diviseurs d’un nombre n est très naïve, elle consiste simplement à essayer tous les nombres entre 1 et n / 2, il y a peut-être moyen d’aller plus vite ?

Certainement
Déjà tu peux t'arrêter à racine carrée de n, au lieu de n/2.
Ensuite tu n'as pas besoin de tester tous les diviseurs, les nombres premiers suffisent (je connais pas de bon algo pour générer les nombres premiers mais je sais qu'il en existe).

EDIT : ah en fait tu veux avoir tous les diviseurs, pas juste les facteurs premiers. Mais si on connaît les facteurs premiers, on peut en déduire le nombre de diviseurs facilement.

le crible, a générer d'avance par élimination des multiples successifs.

Le crible est la méthode la plus simple ouais, mais j'ai évité de la citer parce qu'avec des nombres aussi grands je doute que ce soit faisable...
(ah ben non tiens, j'ai mal lu, les nombres sont pas si grands que ça)

Zerosquare (./1) :
Déjà tu peux t'arrêter à racine carrée de n, au lieu de n/2.

Et comment je connais sqrt(n) ?

ah en fait tu veux avoir tous les diviseurs, pas juste les facteurs premiers. Mais si on connaît les facteurs premiers, on peut en déduire le nombre de diviseurs facilement.

Pourquoi pas, faut voir le coût global Mais je doute que ça réduise significativement les choses

squalyl (./2) :
le crible, a générer d'avance par élimination des multiples successifs.

Et je vais jusqu’où ? 10⁹ ? Ça va bouffer pas mal de RAM

tu donnes N dans divisors(), tu peux calculer sqrt(N)

pour le crible, pareil, tu vas jusqu'au sqrt du max possible, 1+2+3...+500

PS: http://209.85.229.132/search?q=cache:ziO7ua-ZcmoJ:en.wikipedia.org/wiki/Shifting_nth_root_algorithm+square+root+algorithm+binary&cd=2&hl=en&ct=clnk (wikipedia marche pas chez nous)

Hm, finalement après une vingtaine de minutes mon PC a craché la bonne réponse : 76576500
C’est beau.

./5 Je n’ai rien compris

int divisors(long n)
04 {
long q=sqrt(n);
05 int d = 0;
06 long i = 1;
07
08 while (i <= q) {
09 if (n % i == 0)
10 d++;
11 i++;
12 }
13
14 return d + 1;
15 }

edit: génial les sources

./7 C’est 2×d qu’il faut renvoyer dans ce cas, non ?
Et comment j’écris la fonction sqrt ?

Bah c'est une fonction mathématique de base

Oui, ce que je voulais dire, c’est que je ne suis pas certain que le gain en nombre de diviseurs en moins à calculer ne soit pas compensé par le coût du calcul de la racine carrée.

Je vais tester.

Sur un processeur de PC, une racine carrée en virgule flottante se fait en une seule instruction hein ^^

Alors il y a sûrement des algos d'approximation très raisonnables.

(cross, finalement ya encore mieux )

(pour l'anecdote, y'avait une très bonne routine de racine carrée [ou peut être 1 / racine carrée, je sais plus] en virgule fixe dans Quake 3 ; à l'époque c'était plus rapide que de la faire en flottant, mais c'est l'inverse avec les processeurs récents)

Ah mais en fait il y a une propriété super intéressante que je peux exploiter : http://fr.wikipedia.org/wiki/Racine_carr%C3%A9e#Les_racines_carr.C3.A9es.2C_approximations_enti.C3.A8res

ah bah oui, là c'est win

Sinon, tu pourrais générer le crible à la demande, par petits bouts, et stocker la liste des nombres premiers que tu as trouvés dans une liste de ton choix. Pour chaque nombre tu gardes un paramètre supplémentaire te permettant de reprendre le calcul du crible à la prochaine itération. Egalement si tu utilises des bits pour représenter chaque entier (pendant la génération) ça bouffe pas tant de ram que ça (au moins 8 fois moins par rapport à des octets, 32 fois moins pour le « BOOL » souvent défini par int en C)
Pour être efficace dans la génération du crible, tu peux envisager de doubler sa taille à chaque fois qu'il est devenu trop petit (tu travailles donc sur un bloc temporaire deux fois plus gros à chaque fois, mais tu peux le libérer dès que tu n'en a plus besoin).
(Et tout ça sans aucune notion de racine carrée ou autre )

Zerosquare (./13) :
(pour l'anecdote, y'avait une très bonne routine de racine carrée [ou peut être 1 / racine carrée, je sais plus] en virgule fixe dans Quake 3 ; à l'époque c'était plus rapide que de la faire en flottant, mais c'est l'inverse avec les processeurs récents)

http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/

Oui voilà, flemme de retrouver le lien

Ca c'est typiquement le genre d'algo facilement parallélisable sur carte graphique ou le speedup que l'on peut atteindre pourait tourner autour de 60 à 120..

En fait utiliser sqrt(n) était effectivement largement suffisant pour améliorer significativement les perfs, moi je croyais que l’appel à sqrt déclenchait un algorithme complexe alors qu’en fait l’instruction est déjà câblée dans le fpu…

Merci.

Alors déjà ça ne sert à rien de calculer une racine carrée pour une boucle i<=sqrt(n), parce que ça revient au même que i*i<=n, de plus, sur une machine où les multiplications sont lentes, une boucle for (i=0; i*i<=n; i++) est plus rapide si elle est notée: for (i=i2=0; i2<=n; i2+=i,i++,i2+=i).

Ensuite, je signale qu'il existe la propriété que divisors(ab)=divisors(a)divisors(b) si pgcd(a,b)=1.

Or, pgcd(i,i+1)=1 pour tout i, donc divisors(i(i+1))=divisors(i)divisors(i+1). De plus, soit i(i+1)=2^mj où j impair et m entier. Alors divisors(i(i+1)/2)=divisors(2^m-1j)=divisors(2^m-1)divisors(j)=divisors(2^m-1)divisors(i(i+1))/divisors(2^m)=m divisors(i(i+1))/(m+1). Et m peut se trouver facilement à l'aide d'opérations sur les bits.

Bref, on peut aller beaucoup plus vite en appliquant un peu de Mathématiques (comme partout dans Project Euler).

Et puis, bref, ENS sux, Uni Wien rulez!

geogeo (./19) :
Ca c'est typiquement le genre d'algo facilement parallélisable sur carte graphique ou le speedup que l'on peut atteindre pourait tourner autour de 60 à 120..

lol. comme vient de le montrer KK, parfois c'est plus efficace de brancher son cerveau que sa carte graphique

je suis assez impressionne quand meme que tout le monde ait 50000 idees tordues pour ameliorer la vitesse d'une boucle for ou d'une racine carree, alors que c'est pas du tout le point critique de l'algo, mais par contre personne ne se pose la question de reduire la complexite asymptotique !? des le premier coup d'oeil ca parait quand meme mechamment overkill l'algo de sasume. chais pas moi mais des que je vois du bruteforce ca me fait dresser les cheveux sur la tete, pas vous?

Ouais mais on ne vas pas réfléchir à sa place non plus, hein

damnvoid (./22) :
chais pas moi mais des que je vois du bruteforce ca me fait dresser les cheveux sur la tete, pas vous?

Ben c'est deja le cas meme sans en voir si tu as toujours ta coupe afro

Kevin Kofler (./21) :
Alors déjà ça ne sert à rien de calculer une racine carrée pour une boucle i<=sqrt(n), parce que ça revient au même que i*i<=n, de plus, sur une machine où les multiplications sont lentes, une boucle for (i=0; i*i<=n; i++) est plus rapide si elle est notée: for (i=i2=0; i2<=n; i2+=i,i++,i2+=i).

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. Je pense que ce n’est pas plus lent que ce que tu proposes, si effectivement sqrt est une instruction machine, non ?

Sinon merci pour l’autre idée, je vais tester ça tout de suite

Bref, on peut aller beaucoup plus vite en appliquant un peu de Mathématiques (comme partout dans Project Euler).

C’est bien ce que je pensais, et c’est pour ça que je vous ai demandé de l’aide, je ne connais pas les mathématiques

Sasume (./25) :
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. Je pense que ce n’est pas plus lent que ce que tu proposes, si effectivement sqrt est une instruction machine, non ?

En général, une opération sur les flottants est plus lente qu'une opération sur les entiers (et il n'y a pas de sqrt sur les entiers), mais ça dépend de la machine. Il me semble que surtout les opérations complexes comme sqrt peuvent prendre beaucoup de cycles même sur certains x86.

Ok, en tout cas j’ai amélioré ma solution en suivant l’approche que tu as décrite en ./21 et le résultat est instantanné

Sasume (./25) :
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!