» »

Generatorji praštevil

Generatorji praštevil

Thomas ::

Boneman je v komentarju na novico omenil nek generator praštevil. Razlika zaporednih kubov.

To da štiri: 7, 19, 37, 61. Naprej niso več vedno praštevila.

Critticall pravi tkole:


top=99;
while (zero<top) {
j=j*one;
j=zero+j;
zero=1;
zero=i|zero;
primes[i]=j;
i=one;
one+=1;
j=one+zero;
}


Ta da tele:

3,7,13,31,43,71,89,127,151,199,229.

Enajst, naprej niso vedno praštevila.


Jasno je, da pravi generator smo izključili, ker je prepožrešen. Samo aproksimacije.

Trdim, da človek si ni zmožen zmisliti boljšega algoritma kot program.


:)
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Trinajst:

3,7,13,31,43,71,89,127,151,199,229,277,313



top=99;
while (i<top) {
two=one+i;
two=two*one;
i%=10;
i=i+two;
two=1;
primes[rem]=i;
i=rem|two;
rem=one;
one+=1;
}
Man muss immer generalisieren - Carl Jacobi

McHusch ::

Tale n2 - n + 42 je baje ena najboljših. Ali jo lahko Critticall še izboljša?

Thomas ::

Trideset:

top=99;
while (tmp<top) {
upto=-5;
upto=upto-composit;
j=composit-upto;
composit=tmp*tmp;
composit+=12;
primes[tmp]=j;
tmp+=1;
}


5,29,31,37,47,61,79,101,127,157,191,229,271,317,367,421,479,541,607,677,751,829,911,997,1087,1181,1279,1381,1487,1597

McHusch - po moje ga bo počasi premagal. ;)
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Namreč tegale:

x*x+x+41
Man muss immer generalisieren - Carl Jacobi

McHusch ::

Ja, ja, xx - x + 41 sem mislu, ne 42. Stupid me ne zna več prepisovat. :>

nicnevem ::

to je neverjetno....res...

a se niso eni zlo brihtni možje kar lep cajt matral da bi en pameten algoritem za generiranje praštevil pogruntal.....pol pa "kr en program" (ne zamert Thomas ;) ) neki dost boljšga skuha in to v kakšnem času, par dni, mogoče...

Zanima me kaj bi pogruntal v mal daljšem času....če nimaš kaj drugega za kuhat prosm da še mal pustiš da vidmo do kakšne mere je sposoben predelat algoritem...

kje so zdej tisti ki pravja da AI ni mogoč :D

iration ::

Bravo Thomas. Amazing work.
Tudi jaz bi imel kakšno pravico rad v življenju. Npr. pravico do tega, da delam
12 ur na dan in sem za to nagrajen s strani delujočega ekonomskega prostora, ne
pa kaznovan s strani Salmoneličevih gremlinov. - NavadniNimda

Thomas ::

Hvala obema za pripombe. Zvečer spet dam delat naprej, zdej sem moral zoptimizirat en del simplex linearnega programa za Casio calculator in mamo delo še do večera s tem . Pohitril ga je na 50% časa in na 50% linij, kar je kar OK.

Inteligenca je pač simulacija, ki je computing. Človek je pameten toliko, kolikor ima že akumuliranega computinga. To pa vse ni več samo v domeni ljudi (in živali), pač pa nekateri digitalni programčki vse bolj stopajo v ospredje.

Jasno, zdej bodo nekateri trdili, da pa "program sam ne bi pa nič znal", vendar tudi človek sam ne bi kaj dosti naredil.

Samo učinkovitost je pomembna. Nobena prestižnost mecha ali orga. :D
Man muss immer generalisieren - Carl Jacobi

Phil ::

vsota+=(8);
vsota-=(-18);
vsota-=(a);
vsota*=(a);
vsota*=(-16);
vsota*=(-17);
vsota%=(-14);
vsota-=(a);
vsota+=(2);
vsota*=(14);
vsota-=(a);
vsota%=(-14);
vsota/=(5);
vsota-=(a);
vsota*=(a);
vsota/=(-12);
vsota+=(a);
vsota+=(a);
vsota*=(a);
vsota+=(1);
vsota-=(a);
vsota/=(a);
ali
f(a)=(8)-(-18)-a*a*(-16)*(-17)%(-14)-a+(2)*(14)-a%(-14)/(5)-a*a/(-12)+a+a*a+(1)-a/a
Evo generator za prvih 15 praštevil. Par minut dela za mojega švohnega athlona. Ne verjamem da bi kdo "peš" prišel do prvih deset.
LP

Zgodovina sprememb…

  • spremenil: Phil ()

Sergio ::

Thomas: kaksne so zacetne vrednosti neinicializiranih spremenljivk?
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.

Thomas ::

0.
Man muss immer generalisieren - Carl Jacobi

Gandalfar ::

Thomas: zakaj ne optimiziras GIMPS algoritma?

Thomas ::

Sej to maš na moji strani nekje. Pod Next Mersenne.

Pokaže, kje se ga bolj splača iskat. Daš tisti C v Critticall in ugiba.

Morm še porevidirat stran na tanovo verzijo, se mi zdi.

Ful je kaning, hehe!
Man muss immer generalisieren - Carl Jacobi

Thomas ::

No, kaj se je zgodilo ponoči?


df=17;
critticall2=12;
while (true) {
critticall2=critticall2+critticall2;
niz[one]=df;
df=critticall2+df;
one+=1;
critticall2=one;
}


41 praštevil namesto, 40 kot znani McHuschev primer x*x+x+41. Zanimivo je, da je to "extended x*x+x+41", saj sproducira vse te in eno več.

Tko, jest zdej tega ne bom več dosti poganjal. Mogoče kdo drug, ki ima Critticall.

;)
Man muss immer generalisieren - Carl Jacobi

Sergio ::

Hja, posebnost 'prime generating _polynomiala_' je ravno v tem, da je polinom. http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.

Thomas ::

Tole je pa rekurzivni niz, ki niti množenja ne rabi, kaj šele kvadriranja ali česa podobnega.

Nikjer ni rečeno, da "smejo biti samo polinomi". Kakršenkoli algoritem pač. Heh ...
Man muss immer generalisieren - Carl Jacobi

SavoKovac ::

en preprost generator prastevil:
1.)
Najprej si ustvaris zacetno mnozico prastevil (postopek 1.1)

1.1.)
Pomikas se po lihih stevilih in trenutno stevilo n delis z vsemi dosedanjimi prastevili iz sproti grajenega polja, ki so manjsa od kvadratnega korena od n(ostanek pri deljenju mora biti vedno > 0 za prastevilo). Če so vsi ostanki večji od nič, število n dodamo na konec polja. Ta način je dober zato, ker izvrže vsa praštevila do poljubnega števila, če si ga tako nastavimo (For, while, repeat zanka). Postopek je glede na proprosto implementacijo tudi računsko ugoden, saj npr. pri preverjanju števila 10001 le-tega delimo s praštevili, manjšimi od 100.
Sam algoritem se da še optimizirati tako, da naprimer brez slabe vesti in dodatnega preverjanja izpustimo vse večkratnike manjših praštevil(3,5,...) ( če praštevila preverjamo po vrsti ).

2.)
Dodatna (velika) praštevila dobimo tako, po vrsti množimo vsa praštevila, ki smo jih dobili in produktu prištejemo 1.
( npr. 2*3*5*7 + 1 = 221 - praštevilo)
Teoretično lahko tudi kakšno praštevilo izpustimo (npr, 2*5*7 + 1 = 71, vendar moramo potem preveriti, da ni rezultat morebiti deljiv z izpuščenim praštevilom (preverimo deljivost 71 s 3).

Thomas ::

Jasno, vsi vemo, kako se praštevila zgenerirajo. NI to point.

Poanta je v tem, da z KAR NAJBOLJ ENOSTAVNIM algoritmom zgeneriraš čimveč praštevil. Ne pa s tako kompleksnim, kot je tapravi.
Man muss immer generalisieren - Carl Jacobi

Thomas ::

To add 1.

Add 2 pa ta algoritem ne da prav dosti praštevil zaporedoma. Samo 5.

Že 2*3*5*7*11*13+1 ni več praštevilo.
Man muss immer generalisieren - Carl Jacobi

SavoKovac ::

Mea culpa. Sem se malo prenaglil glede spodnjega algoritma. Preveriti je potrebno še deljivost z vsemi praštevili, večjimi od zadnjega v produktu in manjšimi od korena produkta.
Postopek 1.1 pa je vseeno vreden omembe, saj za postopek 2. potrebuješ množico praštevil.:D

Thomas ::

Man muss immer generalisieren - Carl Jacobi

Thomas ::

Proces prevajanja razmišljanja v computing se je pravzaprav pričel že vsaj s prvimi abaki. Sicer so se potem ljudje tolažili, da naj bi šlo za nekakšne "nižje funkcije mišljenja", ampak to pač človek dela take neumne razlage zato, da bi se sam sebi zdel "nekaj več". Čista politika , propaganda in marketing. Se pravi področja, kjer (si) je lagati in (se) slepiti nekako dovoljeno.

Je pa zdaj že dosti težje. Čeprav bodo mnogi uvrstili tudi izum tega algoritma v "nižje funkcije".

Kaj sploh še ostane za "višje funkcije"?

;)
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Sem ga pozabu izklopit, pa je naredil algoritem že za 45 praštevil ... 8-) ;)
Man muss immer generalisieren - Carl Jacobi

Vesoljc ::

shit happez :D
Abnormal behavior of abnormal brain makes me normal...

_marko ::

The saddest aspect of life right now is that science
gathers knowledge faster than society gathers wisdom.

snow ::

Link do ene zadeve, ko en trdi da naj bi Riemanov teorem dokazal. Vreden miljon dolarjev ;)
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

Thomas ::

Ja, ampak za kakršnokoli nagrado bo treba najti praštevilo, ki se ga lahko zapiše z ne manj kot 10 milijoni cifer. Torej dobra dva milijona cifer več!
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Pojma nimam, če je ta (Riemanov) problem s tem rešen, ali ni.

Vem pa, da odkar so nagrade po milijon dolarjev za crack sedmih slavnih problemov, ti hitro poklekajo.

Pa tudi za prvega iz te verige, slavnega Fermajevega (prej neresenega 300 let), se je najprej izkazalo, da dokaz ni bil dober. Avtor jo je (rešitev) potem popravil v nekaj letih.
Man muss immer generalisieren - Carl Jacobi

Zgodovina sprememb…

  • spremenil: Thomas ()

Double_J ::

Koliko pa jih je že rešenih od teh sedmih?

A Critticall bi znal kej takega. Napisat dokaze za take zajebane hipoteze?
Dve šivanki...

Zgodovina sprememb…

  • spremenil: Double_J ()

Thomas ::

Tole bi bil tretji rešen od sedmih. Pa NI, baje. Ne samo da ima kakšne napake, ampak je čisto mimo.
Man muss immer generalisieren - Carl Jacobi

jype ::

REKORDNO PRAŠTEVILO JE ...

Praštevilo je dolgo kar 25 kilometrov in ima kar 7.235.733 številk


Kako pa je lahko stevilo dolgo 25 kilometrov? :)


Pa se bolj zanimiv problem: a zna kdo ocenit interval med sosednjima prasteviloma pri 10^(10^7) in iz te ocene ugotovit, koliko casa bi trajalo poiskat eno tako stevilo?

Thomas ::

Kako daleč sta Mersennovi praštevili? To nas zanima!

Praktično kaže, da na vsakih nekaj milijonov eksponentov, je tam 2^exponent-1, praštevilo.

Ugotavljati za tako velika Mersennova števila, če so praštevila ali ne, je mačji kašelj, proti ugotavljanju nesestavljenosti splošnih števil tam okoli. Traja le kakšno leto dela PCja za vsakega Mersennovega kandidata. V splošnem bi za tako veliko praštevilo, z metodami ki jih imamo, trajalo mnogo gugol let, pa če bi vse Vesolje predelali v stroj za reševanje tega problema po znanih metodah. Kdo ve, če so kakšne boljše.

Zdej se pa začne zanimiv del:

Direkcija podjetja GIMPS dodeljuje prostovoljcem po eno ali več števil v testiranje. Šansa posameznika, da pokolekta nagrado je enaka šansi loto tekmovalca, da zadane sedmico.

Podjetje GIMPS ima pa dobre šanse, da kakšna slepa kura najde zrno. Takrat ji dajo nagrado, če ima KOT PRVI več mest od 10 milijonov, 50 milijonov ... milijardo. Sicer nič.
Man muss immer generalisieren - Carl Jacobi

Zgodovina sprememb…

  • spremenil: Thomas ()

lambda ::

No eno OT vprašanje:
Kako hiter algoritem vam uspe naredit, ki poišče vsa praštevila izmed prvih 1000, prvih 10000 in prvih 50000 naravnih števil? Pod "kako hiter" mislim koliko časa porabi procesor, da jih selektira - to pomeni, da k času pripišeš tip in hitrost proca, da se da vsaj približno primerjat.

edit.
sicer je pa tale GIMPS res ena smešna zadeva ... rajši grem vplačat tistih ~65 kombinacij na loto, pa je verjetnost za zadetek večja, precej več dobim, pa še proca ne mučim dva meseca 8-) No ja ... itak pa ne maram iger na sreču

Zgodovina sprememb…

  • spremenil: lambda ()

Thomas ::

> Kako hiter algoritem vam uspe naredit, ki poišče vsa praštevila izmed prvih 1000, prvih 10000 in prvih 50000 naravnih števil?

Jah, najhitrejšega na svetu, ane. 8-)
Man muss immer generalisieren - Carl Jacobi

lambda ::

Ma ne ... resno sem mislil. Daj Thomas sestavi enega, ti si itak genij, nekaj minut dela zate. Res me zanima, kako hitro ti tole preišče. Jaz sem ugotovil, da sploh ne vem če sem dobrega sestavil. Izmed prvih 50000 naravnih števil najde 5133 praštevil - nekam preveč se mi jih zdi. In za to porabi moj proc (barton 2400 MHz) 13,3s - čisto preveč, res pa je da jaz tole kar v actionscriptu (Flash) zmažem skupaj, ker drugje še ne znam kaj prida programirat. Pa ne se smejat, ko bo nekomu tole naredilo nekajkrat hitreje kot meni :)

Thomas ::

> Ma ne ... resno sem mislil.

Jest tudi. Samo rabim par dni. Jih bom že dobil.
Man muss immer generalisieren - Carl Jacobi

lambda ::

:| Ma ja ... tale moj generator je šodr - sicer je korekten, ampak počasen ko polž ... se moram navadit še kje drugje programirat, ker v AS tegale ne znam speljat veliko boljše.

bosstjann ::

java rabi približno eno sekundo
http://zaversnik.fmf.uni-lj.si/vaje/RP-...

import java.io.*;

public class Prastevila
{
   public static void main(String[] args) throws IOException
   {
      BufferedReader vhod = new BufferedReader(new InputStreamReader(System.in));

      System.out.print("Vnesi zgornjo mejo: ");
      int n = Integer.parseInt(vhod.readLine());
      System.out.println();

      System.out.print("2");
      for (int i = 3; i <= n; i += 2) {
         int j;
         for (j = 2; j <= Math.sqrt(i); ++j) {
            if (i % j == 0) break;
         }
         if (j > Math.sqrt(i)) System.out.print(" " + i);
      }
   }
}

Roadkill ::

5132 prastevil na intervalu od 0 do 50000.
Elapsed CPU time test: 0.170000 sec
Source je pa praktično enak kot tistle v javi. Ene 5× hitrejš je že takoj, če ne izpisuješ na zaslon nič...
Aja pa tole bi prašal... kakšen način merjenja časa, ki ga program porabi priporočate?

zdele sm mel tak cource:
double c0, c1;
double cputime;
c0 = clock();
//for....
c1= clock();
cputime = (c1 - c0)/(CLOCKS_PER_SEC );

Je to kul?

Zgodovina sprememb…

  • spremenil: Roadkill ()

Vesoljc ::

v c-ju na win platofrmi uporabi QueryPerfomance* funkcijo. go google!
Abnormal behavior of abnormal brain makes me normal...

mile ::

lahko tudi v delphiju ;)

lambda ::

:8) Shame on me :)

Phil ::

Da malo tole temo potegnem iz zgodovine. :))
12h evolucije, 55k generacij, 1 algoritem za prvih 30 praštevil.

cout<<"Vnesi cifro: ";
cin>>vh0;

spr11=vh0>>spr10-vh0<<(-10);
spr7=15+spr11;
spr8=spr7<<spr7%vh0;
spr2=vh0+spr8&spr14+vh0<<spr8+(-10)-vh0+5;
spr5=9-(-3)>>6-vh0|vh0>>18;
spr0=vh0*19%12|vh0<<spr2%(-6)|6-vh0&6;
spr6=(-7)-vh0&vh0<<(-5)/(-5);
spr1=(-10)%vh0/4>>vh0|17%vh0|(-2)<<(-33);
spr2=spr1*vh0+spr1-spr5;
spr1=vh0+(-4)%vh0>>spr5|vh0+spr0>>spr2|8*spr0%7;
spr0=(-7)*15+spr2<<spr2-(-19);
spr0=4+vh0%19>>spr0;
spr2=(-5)<<(-4)*spr0&2;
spr12=1>>vh0+7;
spr0=vh0|vh0>>spr1|vh0>>spr6;
spr0=spr0+spr12+vh0-spr2+spr1+vh0+spr12-11;

cout<<"prastevilo: "<<spr0<<endl;

Vse spremenljivke so tipa long in imajo ob začetku vrednost 0. (Upam da sem pravilno prekopiral kodo (<>...)
LP

snow ::

Čedno.

Sam 30 ifov izvede mal manj operacij po moje.



Nekaj me pa glede tvojega programa zanima.
A tele cifre, ki jih uporablja.. to maš par spremenljivk, pa potem random cifre notri mečeš, pa če so je kul fitness se zadeva ohrani. To maš verjetno kr v genomu zakodirano al kako?
Pa na kakem intervalu ti tele cifre generira?
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

Thomas ::

Kmalu bodo vsi problemi rešljivi na EA način. Tudi tisti, ki so pretrdi orehi za "inteligent design".

Tole igračkanje je eksplozivnejše od kateregakoli doslej. :)
Man muss immer generalisieren - Carl Jacobi

Phil ::

@snow
Vrstica programa je predstavljena z tabelo števil (eh z seznami so same muje) poljubne dolžine. Element tabele je lahko bodisi vhod (številka predstavlja indeks vhoda), spremenljivka (št. predstavlja indeks spremenljivke programa) ali konstanta (cifra na nekem intervalu). Indeks spremenljivk in konstante so na začetku random zgenerirani. Konstante v tem primeru na intervalu (-20,20). Seveda se ob mutacijah oboji lahko spreminjajo, konstante naenkrat za največ polovico začetnega intervala (10).
Zaradi logičnih operacij hitro pride do overflowa (ergo program se prepiše) zato je cifre bolje imeti čim manjše.

If stavki so pa za praštevila itak (naj)hitrejši, ker kot kaže nekega enostavnega algoritma za generiranje le teh ni.
LP

Phil ::

Se popravljam. Za generator do 10 recimo je mogoče tole:
spr0=10>>vh0;
spr0=(-8)+vh0>>spr0|1>>spr0;
spr0=vh0+vh0+spr0;
hitreje kot pa:
if (vh0==1) return 1;
...
if (vh0==10) return 23;
Bi moral videti prevedeno kodo. Za generator do večjih praštevil pa if varianta hitrejša.
LP

Zgodovina sprememb…

  • spremenil: Phil ()


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Digitalna evolucija (strani: 1 2 3 426 27 28 29 )

Oddelek: Znanost in tehnologija
141669748 (19917) pietro
»

Najhitrejši programski jezik? (strani: 1 2 )

Oddelek: Programiranje
756829 (4649) Senitel
»

O praštevilih (strani: 1 2 )

Oddelek: Novice / Znanost in tehnologija
525881 (5881) ovdje kokoš
»

Odkrivanje matematičnih funkcij z evolucijo

Oddelek: Znanost in tehnologija
141463 (985) Thomas
»

kako definirtati prastevilo

Oddelek: Programiranje
143503 (3308) ooux

Več podobnih tem