Reprise du message précédent :

 
Ben ouai

Sinon, y a le truc qui dit que les carrés de tous les nombres premiers(sauf 2 et 3) peuvent s'écrire comme un multiple de 24 augmenté de 1.
5²=1*24+1 ; 7²=2*24+1 ; 11²=5*24+1 ; 13²=7*24+1 ; 17²=12*24+1....
Mais bon, ça doit pas servir à grand-chose

Tiens je connaissais pas ca! Tu saurais pas comment ca se démontre par hasard?
 
edit : non en fait c'est évident

Evident mais surprenant au premier abord

oui en fait quand je dis évident ca veut dire "evident si on cherche un peu" . Donc pas évident, en fait

Je découvre cette nuit cette partie là de HFR. Et là mdr.
Je regarde la date du topic pour voir s'il s'agirait pas du 1er avril et même pas.
 
Bon, je pense que Doc'Maboule est honnète, que la formule mathématique dont il  
dispose peut lui paraitre en temps constant mais il a certainement dû zappé complétement les contraintes d'architecture matérielle (comme souvent chez les matheux).
 
Donc petit cours de rattrapage en architecture des ordinateurs et d'arithmétique  des ordinateurs:
 
Lorsque je fais X * Y, le calcul est en temps constant si chacune des 2 opérandes est représentable dans un mot mémoire (32 bits pour un PC ou un MAC, 128 bits pour certains gros serveurs/calculateurs,il y a surement mieux mais de toute manière il y a toujours des nombres plus grands dans |N...) car ce calcul est "câblé" en machine. Il existe de nombreuses implémentations matérielles qui permettent d'obtenir également du temps constant pour des opérandes représentables dans un double-mot (64 bits pour le PC par exemple).  
 
Lorsque l'une des 2 opérandes n'est plus représentables dans un mot (voir un double mot) mémoire, il faut avoir recours à des solutions logicielles pour effectuer la multiplication.
Soit n le nombre de chiffres nécessaires nécessaires pour représenter le nombre dans une base donnée (sur PC c'est la base 2).
L'algo naïf, la multiplication du primaire est en O(n²)
L'algo de Karatsuba de 1962(un très con diviser pour régner) est en O(n^(log2(3))) (lisez log à base 2 de 3).  
Toom&Cook(1963-1966) ont généralisé l'approche de Karatsuba et ont donné un algo en O(n^(logk(2k-1)) (lisez log à base k de 2k-1) où k est la base de réprésentation.
L'algo de Schonhage-Strassen en 1971 basé sur les transformées de Fourrier Discrètes et les produits de convolution est en O(n log n log log n) (où log = log à base 2) et était encore le meilleur algo de multiplication il y a un mois.  
Dans la pratique Karatsuba reste très bon, et il faut vraiment des nombres immenses pour être gagnant avec un Schonhage-Strassen. Il faut noter aussi que
la difficulté (compréhension & implémentation) de l'algo de Schonhage-Strassen  
a fait qu'il n'y a eu que très peu d'implémentations réelles.
 
On ne peut donc pas multiplier deux nombres QUELCONQUES de |N en temps constant. Quant à multiplier des matrices en temps constant ...
 
Donc, Doc'Maboule, je serais  très heureux de connaitre le 2^4096 ème nombre premier en temps constant. A moins bien sûr que tu n'utilises un ordinateur quantique....

Sauf qu'il ne parle pas de temps constant mais de complexité algorithmique, qui est indépendante de l'architecture et de l'implémentation de l'opération élémentaire qui sert de référence. Ce qui ne change rien au fait que ce topic est un pur délire, je suis bien d'accord
 

De toute façon, y'a un truc très simple pour faire du temps constants, surtout pour ce système.
 
Tu prends un super calculateur, afin de te donner les n premiers nombres premiers.
 
36 mois après, quand t'as le résultat, du fout tout ça dans un tableau en dur dans ton programme, et tu récupères le nombre premier à la position x en un temps constant, à condition que x <= n et que x soit codable sur 32 bits.
 
Franchement, je vois pas pourquoi les algos d'encryoptage en chient autant pour générer des nombres aléatoires à partir de nombres premiers. C'est pas très compliqué à faire, et sur un super calculateur, préparer la matrice sera relativement "rapide" à condition de rester réaliste pour ce qui est de la valeur de n évidement. Mais ce nombre n est de toute façon limité, parceque sur un PC "normal", je vois pas trop comment générer un nombre premier à l'indice 10^2000 par exemple en mois de quelques sciècles, donc les algos en questions n'utilisent pas de telles valeurs de n.
 
Moi je suis pour le pragmatisme, les belles mathématiques, c'est très joli sur un super calculteur de laboratoire, mais ça n'a rien à foutre dans un programme quand on peut s'en passer, ce qui est la cas ici.

 
Si si je t'assure, quand on donne une complexité algorithmique cela
tient compte de l'architecture des machines, c'est-à-dire que l'on considère que l'algo est exécuté sur une machine de type RAM (l'architecture des ordinateurs d'aujourd'hui et d'hier). Sinon tu fais des algos que pour des machines de Türing et là les problèmes NP_Complet deviennent polynomiaux.

moi j'ai celle pour transformer un hash md5 vers une string
 
on echange ?
MP si tu veux

4

Bon, il est temps de pisser à la raie de certains, pardon, de donner une solution parmi d'autres à ce problème. Celle-ci a été inventée il y a plus de 2000 et se nomme le crible d'Erathostène (j'entends déjà les nerdzs.prout.prout beugler que ce n'est pas constant). L'idée est qu'il faut utiliser un générateur d'algo pour obtenir un ensemble de formules de transformation permettant d'associer un nombre premier à son rang, cela afin de réaliser le crible. Il suffit ensuite de pousser le générateur jusqu'à avoir suffisamment de suites pour le nombre premier voulu au départ et on obtient un algo permettant de calculer ce nombre premier ainsi que ceux qui le précèdent avec une complexité constante (modulo les histoires de hardware). C'est la première solution que j'ai trouvé en me penchant sur ce problème et c'est de là que vient la formule que j'ai donnée plus haut (x=2*E((n+1)/2) + 2*n + 1).
 
En version "dépliée", :

 
Cette méthode permet effectivement de trouver un algo avec une complexité constante pour le nombre premier voulu et la même complexité pour ceux qui le précedent.
 
Après, c'est une solution à chier parce que si la complexité de l'algo généré est constante, c'est tout simplement parce que le boulot a été déplacé dans le générateur (on oubliera au passage que le nombre de terme des suites croît de manière exponentielle ). Il existe, à ma connaissance, au moins deux solutions bien meilleures (mais qui n'ont rien à voir quant à la complexité mise en oeuvre ne serait-ce que pour leur explication). Je vous fais confiance pour ne pas les chercher et encore moins les trouver.

t'es vraiment le roi des *******, le crible d'Eratosthène, c'est une méthode précalculée et donc la complexité n'est pas certainement pas constante. on attend toujours le 2^4096 ème nombre premier.

 
Et toi, tu es bien le roi des benêts. Je n'ai jamais dis que la méthode était de complexité constante. Je disais que les nerdzs@benêts.com allaient faire cette remarque stupide et tu as voulu me donner raison? Franchement, tu es mignon tout plein
 
Ensuite, ce n'est pas du "précalculé" parce que l'algo généré, même dans un état intermédiaire, sert à produire les suites suivantes qui vont le composer.

c'est toi qui nous a tous pris de haut avec tes histoires de complexité constante alors que t'as fait la preuve que tu ne sais pas ce qu'est la complexité.
 
Je comprends pas trop l'intérêt pour toi de remonter ce sujet, si j'étais toi, j'aurais plutôt essayé de le laisser tomber, histoire de pas être encore plus ridicule ...
 
Je sais pas à la raie de qui tu crois pisser, tout le monde connais le crible d'érathostène, c'est du genre un exercice de première année.
 
Quand t'en auras assez de prendre les gens pour des cons / de te croire intelligent ...

 
Non, j'ai fait la preuve que ça fait longtemps que je n'ai pas fait de maths (presque vingt ans).
 

 
Ha ha ha
 

 
Tu veux dire de première?
 

 
Je ne me crois pas "intelligent" (terme creux) mais c'est vrai que certains sont bien niaiseux par ici.

Faut reconnaitre que le coup de la complexité constante, c'est nous qui nous le sommes inventés...

 
Bon, je ré-explique.
 
Il y a d'un côté un générateur d'algo qui n'est pas en complexité constante mais qui n'était l'objet du problème.
 
Il y a de l'autre côté les algos qu'il génère qui, eux, sont en complexité constante (bien que leurs complexités respectives ne soient pas égales entre elles).
 
C'est plus clair?

Oui, oui, j'avais compris; Mais je voulais souligner que  
O(n) = O(n-1) = .... = O(1) ca veut pas, en toute rigueur, dire complexité constante... C'est la domination de l'ordre de grandeur qui ne change pas ( mais bon, c'est une histoire de vocabulaire )

 
Oui, taz me l'avais fait remarquer et je reconnais sans peine que je me suis trompé dans le formalisme. Il me semblait avoir rectifié ce que j'entendais par là un peu plus loin.
 
Sur ce, je voulais vous remercier ainsi que d'autres pour s'être penché sur le problème autrement qu'en beuglant:
"ban!
résolution d'exercice!
multi!
c'est pas possible!
et ta soeur?"

Mais bon je me demande pourquoi aller chercher si loin une solution qui ne résout pas le probleme : apres tout, je peux tres bien décider aussi de remplir une mémoire infinie ( en tant que "programmeur fou" ) avec des nombres premiers aussi loin que je veux ( générateur d'algo ) et mon algo ce serait simplement d'aller chercher ce qui se trouve dans la bonne case... ( complexité constante )

 
Bah, j'ai donné une *mauvaise* solution parce que bon, se faire traiter de mytho, ça va deux minutes, mais il y en a d'autres plus efficaces. Pour le tableau, il me semblait aussi avoir interdit ce cas.

Mais de rien
A priori c'est la moindre des choses ... meme si certains forumeurs ont parfois du mal a admettre qu'ils ne possedent pas la connaissance absolue  

Oui, c'est exact, mais cette contrainte est-elle arbitraire ou elle empeche certains problemes de survenir?

Bonjour l'ambience dans la cat programmation !  

Faut pas croire, on est une grande famille avec ses coups de gueule

Oui, on avait remarqué, mais ce que tu risques en disant ca c'est de relancer la bataille alors que ca c'était calmé

 
Disons que c'était un poil trop simple

 
je pense qu'a l'ecole ton prof a dit 3 mots que tu as mélangés
 
complexité, constant, algorithme
   ensuite la cloche a sonné, et tu t'es assoupi en disant demain tout le monde croira que je suis intelligent  
 
apres dans ton science et vie junior tu as trouvé eratostene (euh)
tu t'es dit les gros naza d'HFR y connaisse pas les mathematiciens egyptiens    
 
 
et puis maintenant tu t'enfonces
 
dommage  
re-cré un pseudo  
@+
 

 
 
Ouahh! Comment que vous avez fait pour tout comprendre que j'ai pas encore quinze ans? Z'êtes trop trop fort.
 
Pis vous savez qui c'était Eratosthène. Et mince! moi qui croyais pouvoir vous faire la nique sur les mathématiciens qu'on étudie en troisième et dans science et vie junior, les mathématiciens égyptiens...
 
Surtout qu'Eratosthène est né dans une colonie grecque se nommant Cyrène, que Cyrène se trouve en pleine Libye et à peine 900 Km à l'ouest de l'Egypte... Mais bon, je dois confondre avoir étudié à Alexandrie et être Egyptien

Je suis déçu, je pensais que tu avais une solution (fausse)plus élaborée que ça.  Nous ressortir le bon vieux crible, c'est affligeant.  

C'est bien le problème la complexité algorithmique tient compte de l'architecture machine RAM (voir post plus haut). On ne peut l'ignorer.
Ouvre au moins un livre d'algorithmique avant de te lancer dans ce genre de topic, ça t'aurait évité tout ce déchainement.

AMen

 
 
J'ai moi aussi lu le merveilleux sujet que tu nous as pondu.
Laisse moi te dire que tu en sors grandi. la prochaine fois que tu as une idee lumineuse, envoie moi un MP d'abord, j'aimerais profiter de ta vivacite d'esprit. Tiens, non, en fait j'aimerais carrement collaborer avec toi. Cela impliquera probablement que tu quittes Barbes et les fabuleuses tables a bonneteau ou tu dois surement evoluer. Mais je suis sur que l'on pourrait trouver un terrain d'entente.
 
PS:
 

mais lol quoi ! C'est quoi tous ces informaticiens aigris?!

 
Il ne s'agit pas d'implémenter un vieux crible à trois francs six sous mais ce n'est pas grave. D'ailleurs, vous en avez vu beaucoup des cribles sous la forme de suites vous?
 

 
Comme c'est borné, il suffit de prendre la complexité maximale pour les opérations utilisées et basta.

 
Des pauvres mecs qui se font sucer tous les 29 février.

Ouais, c'est clair! Ils ont trouvé quelqu'un sur qui taper, ils ne se genent plus!

ou qui sortent des trucs du genre o(n) == o(n-1) == ... == o(1) et après nous prennent pour des imbéciles.
 
Si ton seul argument c'est ma frustration sexuel, c'est que vraiment tu as peu de choses à dire.

 
Ha ha ha
 
Question paysage, je pense qu'il n'y en a pas beaucoup par ici qui ont cette vue là depuis leur terrasse...
 

 
Mais bon, je m'avoue vaincu. U(n) = n, c'est d'une complexité exponentielle, Eratosthène était Egyptien - Platon aussi d'ailleurs - et il n'y avait pas un seul gros naze frustré de banlieue sur ce fil à par moi.

 
Tu sais, je préfère me tromper dans un formalisme mathématique que je n'ai pas utilisé depuis vingt ans que fabuler le comportement de new. Tu veux que je te ressorte les conneries que tu m'as sorti sur le new placement qu'on rigole?