Boo
./1
- Posté le 24/03/2010 à 18:07 Membre depuis le 28/08/2003, 8213 messages
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
- Posté le 24/03/2010 à 18:14 - Edité par Zerosquare le 24/03/2010 à 18:17 Membre depuis le 27/04/2006, 43576 messages
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.
avatarZeroblog

« 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
- Posté le 24/03/2010 à 18:16 Membre depuis le 16/06/2001, 59978 messages
le crible, a générer d'avance par élimination des multiples successifs.
./4
- Posté le 24/03/2010 à 18:20 - Edité par Zerosquare le 24/03/2010 à 18:21 Membre depuis le 27/04/2006, 43576 messages
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)
avatarZeroblog

« 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
- Posté le 24/03/2010 à 18:21 Membre depuis le 28/08/2003, 8213 messages
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
- Posté le 24/03/2010 à 18:29 - Edité par squalyl le 24/03/2010 à 18:32 Membre depuis le 16/06/2001, 59978 messages
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
- Posté le 24/03/2010 à 18:31 Membre depuis le 28/08/2003, 8213 messages
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
- Posté le 24/03/2010 à 18:33 Membre depuis le 16/06/2001, 59978 messages
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
- Posté le 24/03/2010 à 18:38 Membre depuis le 28/08/2003, 8213 messages
./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. »
- Posté le 24/03/2010 à 18:40 Membre depuis le 27/04/2006, 43576 messages
Bah c'est une fonction mathématique de base confus
avatarZeroblog

« 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
- Posté le 24/03/2010 à 18:42 Membre depuis le 28/08/2003, 8213 messages
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. »
- Posté le 24/03/2010 à 18:44 Membre depuis le 27/04/2006, 43576 messages
Sur un processeur de PC, une racine carrée en virgule flottante se fait en une seule instruction hein ^^
avatarZeroblog

« 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
- Posté le 24/03/2010 à 18:44 Membre depuis le 18/06/2001, 30165 messages
Alors il y a sûrement des algos d'approximation très raisonnables.

(cross, finalement ya encore mieux grin)
avatar <<< Kernel Extremist©®™ >>>
Saint Qt, priez pour nous.
- Posté le 24/03/2010 à 18:48 Membre depuis le 27/04/2006, 43576 messages
(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)
avatarZeroblog

« 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
- Posté le 24/03/2010 à 18:51 Membre depuis le 28/08/2003, 8213 messages
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. »
- Posté le 24/03/2010 à 18:55 Membre depuis le 16/06/2001, 59978 messages
ah bah oui, là c'est win smile
- Posté le 24/03/2010 à 18:58 Membre depuis le 15/06/2003, 7956 messages
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
- Posté le 24/03/2010 à 19:08 Membre depuis le 30/06/2001, 35372 messages
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 ? - Ximoon's Box - 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.
- Posté le 24/03/2010 à 19:15 Membre depuis le 27/04/2006, 43576 messages
Oui voilà, flemme de retrouver le lien hehe
avatarZeroblog

« 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
- Posté le 24/03/2010 à 19:56 Membre depuis le 06/02/2003, 7215 messages
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.
- Posté le 24/03/2010 à 22:56 Membre depuis le 28/08/2003, 8213 messages
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. »
- Posté le 25/03/2010 à 01:19 Membre depuis le 10/06/2001, 34991 messages
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 (fr/en), MobiFiles (de)
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é
- Posté le 25/03/2010 à 02:19 Membre depuis le 10/06/2001, 33930 messages
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
- Posté le 25/03/2010 à 02:27 Membre depuis le 27/04/2006, 43576 messages
Ouais mais on ne vas pas réfléchir à sa place non plus, hein tongue
avatarZeroblog

« 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
- Posté le 25/03/2010 à 02:58 Membre depuis le 15/06/2001, 16446 messages
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!
- Posté le 25/03/2010 à 11:14 Membre depuis le 28/08/2003, 8213 messages
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. »
- Posté le 25/03/2010 à 14:33 Membre depuis le 11/11/2001, 109152 messages
!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) // http://www.yaronet.com/posts.php?s=6238
- Posté le 25/03/2010 à 19:19 Membre depuis le 10/06/2001, 34991 messages
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 (fr/en), MobiFiles (de)
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é
- Posté le 25/03/2010 à 19:29 Membre depuis le 28/08/2003, 8213 messages
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. »
- Posté le 26/03/2010 à 02:59 Membre depuis le 10/06/2001, 33930 messages
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