forumti.gif
@_ö
(12:59)  Bienvenue ! - Inscrivez vous pour poster ! -
Boo, Orion_, Wutch, chris15, SCPCD, BX 16V, flacon030, 46 inconnu(s), 18 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 » Forum informatique & développement :: Forum Ti 89, Titanium / 92+ / Voyage 200 et TI-Nspire » Algorithmie et optimisation (41r) » Euler #12
./Post de départ - Euler #12
28.08.2003 - 8284
18:07  Sasume - Posté : 24-03-2010  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
./1
27.04.2006 - 40039
18:14  @Zerosquare - Posté : 24-03-2010  @_ö
Sasume (./0) :
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
« Sur Atari tout le hardware tu trouvera, le driver toi même tu le codera » — GT Turbo
./2
16.06.2001 - 61448
18:16  squalyl - Posté : 24-03-2010  M
le crible, a générer d'avance par élimination des multiples successifs.
./3
27.04.2006 - 40039
18:20  @Zerosquare - Posté : 24-03-2010  @_ö
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
« Sur Atari tout le hardware tu trouvera, le driver toi même tu le codera » — GT Turbo
./4
28.08.2003 - 8284
18:21  Sasume - Posté : 24-03-2010  M
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 smile Mais je doute que ça réduise significativement les choses sad

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 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. »
./5
16.06.2001 - 61448
18:29  squalyl - Posté : 24-03-2010  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.
./6
28.08.2003 - 8284
18:31  Sasume - Posté : 24-03-2010  M
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 #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. »
./7
16.06.2001 - 61448
18:33  squalyl - Posté : 24-03-2010  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#
./8
28.08.2003 - 8284
18:38  Sasume - Posté : 24-03-2010  M
./7 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. »
./9
27.04.2006 - 40039
18:40  @Zerosquare - Posté : 24-03-2010  @_ö
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
« Sur Atari tout le hardware tu trouvera, le driver toi même tu le codera » — GT Turbo
./10
28.08.2003 - 8284
18:42  Sasume - Posté : 24-03-2010  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. »
./11
27.04.2006 - 40039
18:44  @Zerosquare - Posté : 24-03-2010  @_ö
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
« Sur Atari tout le hardware tu trouvera, le driver toi même tu le codera » — GT Turbo
./12
18.06.2001 - 27312
18:44  Folco - Posté : 24-03-2010  M
Alors il y a sûrement des algos d'approximation très raisonnables.

(cross, finalement ya encore mieux grin)
avatarFolco'sandbox : 2014-11-26
<<< Kernel Extremist©®™ >>> WIP : r14 - 2014-12-02

- xdef directive now updates the cursor
- include directive remove its file from the fileslist when parsed
- added dc directive, binary size verification, relocation table handling
./13
27.04.2006 - 40039
18:48  @Zerosquare - Posté : 24-03-2010  @_ö
(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
« Sur Atari tout le hardware tu trouvera, le driver toi même tu le codera » — GT Turbo
./14
28.08.2003 - 8284
18:51  Sasume - Posté : 24-03-2010  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. »
./15
16.06.2001 - 61448
18:55  squalyl - Posté : 24-03-2010  M
ah bah oui, là c'est win smile
./16
15.06.2003 - 7811
18:58  GoldenCrystal - Posté : 24-03-2010  @_ö
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
./17
30.06.2001 - 35982
19:08  @Ximoon - Posté : 24-03-2010  M
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/
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.
./18
27.04.2006 - 40039
19:15  @Zerosquare - Posté : 24-03-2010  @_ö
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
« Sur Atari tout le hardware tu trouvera, le driver toi même tu le codera » — GT Turbo
./19
06.02.2003 - 7268
19:56  geogeo - Posté : 24-03-2010  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.
./20
28.08.2003 - 8284
22:56  Sasume - Posté : 24-03-2010  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. »
./21
10.06.2001 - 33210
01:19  Kevin Kofler - Posté : 25-03-2010  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é
./22
10.06.2001 - 35353
02:19  damnvoid - Posté : 25-03-2010  M
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.. 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
./23
27.04.2006 - 40039
02:27  @Zerosquare - Posté : 25-03-2010  @_ö
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
« Sur Atari tout le hardware tu trouvera, le driver toi même tu le codera » — GT Turbo
./24
15.06.2001 - 16848
02:58  natto - Posté : 25-03-2010  F
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 #trioui#
avatar 納豆パワー!
I becamed a natto!!!1!one!
./25
28.08.2003 - 8284
11:14  Sasume - Posté : 25-03-2010  M
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 #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. »
./26
11.11.2001 - 114275
14:33  @vince - Posté : 25-03-2010  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
./27
10.06.2001 - 33210
19:19  Kevin Kofler - Posté : 25-03-2010  M
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.
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é
./28
28.08.2003 - 8284
19:29  Sasume - Posté : 25-03-2010  M
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é #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. »
./29
10.06.2001 - 35353
02:59  damnvoid - Posté : 26-03-2010  M
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!
avatarI'm on a boat motherfucker, don't you ever forget
./Publicité AdSense
 « - 1/2 - Suivant » :: Pages
 Index » Forum informatique & développement :: Forum Ti 89, Titanium / 92+ / Voyage 200 et TI-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
     Flood control (?) :    
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
69ms | Statistiques