1

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 : #include <stdio.h> int divisors(long n) { int d = 0; long i = 1; while (i <= n / 2) { if (n % i == 0) d++; i++; } return d + 1; } long euler12() { long n = 1; long i = 2; while (divisors(n) < 500) { n += i; i++; } return n; } int main(int argc, char *argv[]) { printf("%ld\n", euler12()); }
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 24629.png, 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 ?
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. »

2

Sasume (./1) :
De même, ma stratégie pour calculer le nombre de diviseurs dâ&#x20AC;™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â&#x20AC;™aller plus vite ?
Certainement smile
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.
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

3

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

4

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)
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

5

Zerosquare (./2) :
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 smile Mais je doute que ça réduise significativement les choses sad
squalyl (./3) :
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 sad
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. »

6

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)

7

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

./6 Je n’ai rien compris confus
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. »

8

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 hum2

9

./8 C’est 2×d qu’il faut renvoyer dans ce cas, non ?
Et comment j’écris la fonction sqrt ?
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. »

10

Bah c'est une fonction mathématique de base confus
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

11

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.
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. »

12

Sur un processeur de PC, une racine carrée en virgule flottante se fait en une seule instruction hein ^^
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

13

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

(cross, finalement ya encore mieux grin)

14

(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)
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

15

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
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. »

16

17

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 tongue)
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

18

Zerosquare (./14) :
(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/
avatar
Que cache le pays des Dieux ? - Forum Ghibli - Forum Littéraire

La fin d'un monde souillé est venue. L'oiseau blanc plane dans le ciel annonçant le début d'une longue ère de purification. Détachons-nous à jamais de notre vie dans ce monde de souffrance. Ô toi l'oiseau blanc, l'être vêtu de bleu, guide nous vers ce monde de pureté. - Sutra originel dork.

19

Oui voilà, flemme de retrouver le lien hehe
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

20

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.. smile
avatar
la Nature nous montre seulement la queue du lion. Mais je suis certain que le lion a qui elle appartient pense qu'il ne peut pas se révéler en une fois en raison de son immense taille.

- Fondateur de Ti-Gen -: http://www.tigen.org

- Membre du Groupe Orage Studio -: http://oragestudio.free.fr/

- Mon site perso -: http://tisofts.free.fr

Projets TI68K en cours:
GFA-Basic = http://www.tigen.org/gfabasic
Arkanoid.
PolySnd 3.0.

21

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.
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. »

22

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)=2mjj impair et m entier. Alors divisors(i(i+1)/2)=divisors(2m-1j)=divisors(2m-1)divisors(j)=divisors(2m-1)divisors(i(i+1))/divisors(2m)=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! tongue
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é

23

geogeo (./20) :
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.. smile

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

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?
avatar
I'm on a boat motherfucker, don't you ever forget

24

Ouais mais on ne vas pas réfléchir à sa place non plus, hein tongue
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

25

damnvoid (./23) :
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 trioui
avatar
納 豆パワー!
I becamed a natto!!!1!one!

26

Kevin Kofler (./22) :
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 top
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 sad
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. »

27

!call Flanker
--- Call : Flanker appelé(e) sur ce topic ...
avatar
Webmaster du site Ti-FRv3 (et aussi de DevLynx)
Si moins de monde enculait le système, alors celui ci aurait plus de mal à nous sortir de si grosses merdes !
"L'erreur humaine est humaine"©Nil (2006) // topics/6238-moved-jamais-jaurais-pense-faire-ca

28

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. 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.
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é

29

Ok, en tout cas j’ai amélioré ma solution en suivant l’approche que tu as décrite en ./22 et le résultat est instantanné top
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. »

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