forumti.gif
@_ö
(21:57)  Bienvenue ! - Inscrivez vous pour poster ! -
Boo, Gerard1146, very, dc103chaos, Cmatic, xCeLfr, Nalfus, wonderpanzer, 65 inconnu(s), 28 bot(s)

Login :  Mot de passe :      Se souvenir de moi.  Mot de passe perdu ?
/!\:: Cliquez ici pour vous inscrire et poster, créer des sujets ou des forums ! ::/!\
 « - 1/2 - Suivant » :: Pages
 Index » Vince//Nymphodusse//piwi :: Forum Ti89, 92+, Voyage 200 et Nspire » Algorithmie et optimisation (41r) » Euler #12
./1
28.08.2003 - 8213
18:07  Sasume - Posté : 24-03-2010  Infos M
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. »
./Publicité AdSense
./2
27.04.2006 - 42719
18:14  @Zerosquare - Posté : 24-03-2010  Infos @_ö
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.
Edité par Zerosquare le 24-03-2010 à 18:17:44.
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
16.06.2001 - 59441
18:16  squalyl - Posté : 24-03-2010  Infos M
le crible, a générer d'avance par élimination des multiples successifs.
./4
27.04.2006 - 42719
18:20  @Zerosquare - Posté : 24-03-2010  Infos @_ö
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)
Edité par Zerosquare le 24-03-2010 à 18:21:42.
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
28.08.2003 - 8213
18:21  Sasume - Posté : 24-03-2010  Infos M
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
16.06.2001 - 59441
18:29  squalyl - Posté : 24-03-2010  Infos M
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)
Edité par squalyl le 24-03-2010 à 18:32:15.
./7
28.08.2003 - 8213
18:31  Sasume - Posté : 24-03-2010  Infos M
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
16.06.2001 - 59441
18:33  squalyl - Posté : 24-03-2010  Infos M
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
28.08.2003 - 8213
18:38  Sasume - Posté : 24-03-2010  Infos M
./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
27.04.2006 - 42719
18:40  @Zerosquare - Posté : 24-03-2010  Infos @_ö
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
./11
28.08.2003 - 8213
18:42  Sasume - Posté : 24-03-2010  Infos M
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
27.04.2006 - 42719
18:44  @Zerosquare - Posté : 24-03-2010  Infos @_ö
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
./13
18.06.2001 - 29273
18:44  Folco - Posté : 24-03-2010  Infos M
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.
./14
27.04.2006 - 42719
18:48  @Zerosquare - Posté : 24-03-2010  Infos @_ö
(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
./15
28.08.2003 - 8213
18:51  Sasume - Posté : 24-03-2010  Infos M
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
16.06.2001 - 59441
18:55  squalyl - Posté : 24-03-2010  Infos M
ah bah oui, là c'est win smile
./17
15.06.2003 - 7827
18:58  GoldenCrystal - Posté : 24-03-2010  Infos @_ö
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)
avatarLe 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
30.06.2001 - 35298
19:08  Ximoon - Posté : 24-03-2010  Infos M
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/
avatarQue 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.
./19
27.04.2006 - 42719
19:15  @Zerosquare - Posté : 24-03-2010  Infos @_ö
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
./20
06.02.2003 - 7215
19:56  geogeo - Posté : 24-03-2010  Infos M
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
avatarla 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
28.08.2003 - 8213
22:56  Sasume - Posté : 24-03-2010  Infos M
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
10.06.2001 - 34647
01:19  Kevin Kofler - Posté : 25-03-2010  Infos M
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
avatarMes 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é
./23
10.06.2001 - 33930
02:19  damnvoid - Posté : 25-03-2010  Infos M
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?
avatarI'm on a boat motherfucker, don't you ever forget
./24
27.04.2006 - 42719
02:27  @Zerosquare - Posté : 25-03-2010  Infos @_ö
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
./25
15.06.2001 - 16446
02:58  natto - Posté : 25-03-2010  Infos F
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
28.08.2003 - 8213
11:14  Sasume - Posté : 25-03-2010  Infos M
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
11.11.2001 - 108855
14:33  @vince - Posté : 25-03-2010  Infos M
!call Flanker
--- Call : Flanker appelé(e) sur ce topic ...
avatarWebmaster 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
./28
10.06.2001 - 34647
19:19  Kevin Kofler - Posté : 25-03-2010  Infos M
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.
avatarMes 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é
./29
28.08.2003 - 8213
19:29  Sasume - Posté : 25-03-2010  Infos M
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
10.06.2001 - 33930
02:59  damnvoid - Posté : 26-03-2010  Infos M
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!
avatarI'm on a boat motherfucker, don't you ever forget
./Publicité AdSense
 « - 1/2 - Suivant » :: Pages
 Index » Vince//Nymphodusse//piwi :: Forum Ti89, 92+, Voyage 200 et Nspire » Algorithmie et optimisation (41r) » Euler #12

./Poster un nouveau message. - Ouvrir dans une nouvelle fenêtre
Login : Mot de passe :

url - image - media  
spoiler - pre - fixed
quote - box - hr
poll - code





Smileys
Smileys perso
Pièce jointe
   
Les messages postés sont la propriété de leurs auteurs. Nous ne sommes pas responsables de leurs contenus.

» yN ©1624 - Aide / Charte / Crédits
85ms | Statistiques