| Autor | Zpráva | ||
|---|---|---|---|
| Sir Tom Profil |
#1 · Zasláno: 25. 10. 2011, 13:06:46 · Upravil/a: Sir Tom
Ahoj,
mám takový menší problém a nevím, jak jej vyřešit. Chci vytvořit funkci, která vrací pole, kde prvky jsou prvočísla od 2 do 'n' (n je argument funkce). Běžně se na tento problém používá Eratosthenovo síto. Jenomže bohužel tento algoritmus přestává být v JS účinný pro velká n (na konci je kód). Tento alg. funguje na principu, že se vytvoří pole přirozených čísel od 2 do n, vezme se první číslo (2) a uloží do pole prvočísel. Následně se odstraní všechny násobky tohoto čísla v původním poli. Vezme se opět první číslo, které zbylo v osekaném poli, toto číslo (v našem případě 3) se uloží do pole prvočísel a opět se odstraní jeho násobky - atd.. V tomto alg. je jeden vnořený cyklus for ve while. Navrhl jsem také alg. (mnou pojmenovaný Charybdy algoritmus), který má splňovat stejný cíl, ale jiným způsobem. Funguje tak, že do v poli prvočísla uložíme 2 a pak procházíme cyklem od i=3 do i=n, a zkoumáme jestli i je dělitelné nějakým prvkem v poli prvočísla. Pokud ano - zvýšíme i a následuje nový průchod cyklem. Pokud ne, dané i se uloží do pole prvočísla. I u tohoto alg. jsou vnořené cykly, což je docela blbé a alg. nefunguje pro velká n. Potřebuji algoritmus, který bude fungovat pro n = 10^10 nebo n=10^16 a bude vracet pole v rozumném čase. Nemusíte psát nějaké dlouhé algoritmy. Stačí, jestli mi poradíte (klidně i popisem), jak na to... Na internetu jsem žádný vhodný alg. nenašel. <script type="text/javascript" language="JavaScript">
//Eratostheono síto - funkce vrací pole prvočísel od 2 do n (n je argument funkce)
function eratosthenovoSito(n){
var cisla = new Array();
var prvocisla = new Array();
if(n<2) return prvocisla;
for(i=2; i<=n; i++){
cisla.push(i);
}
while(cisla.length!=0){
var prvocislo = cisla.shift();
prvocisla.push(prvocislo);
for(i=0;i<cisla.length;i++){
if(cisla[i]%prvocislo==0) cisla.splice(i,1);
}
}
return prvocisla;
}
//Charybdy algoritmus (vymyšlený název) - vrací pole prvočísel od 2 do n
function charybdyAlgoritmus(n){
var deli = true;
var prvocisla = new Array();
if(n<2) return prvocisla;
prvocisla.push(2);
for(i=3; i<=n; i=i+2){
for(j=0; j<prvocisla.length; j++){
if(i%prvocisla[j]==0){
deli = true;
break;
}
if(prvocisla[j]>Math.sqrt(i)){
deli = false;
break;
}
}
if(!deli){
prvocisla.push(i);
}else{
deli = false;
}
}
return prvocisla;
}
</script> |
||
| Witiko Profil |
#2 · Zasláno: 25. 10. 2011, 13:23:48 · Upravil/a: Witiko
Sir Tom:
Takhle jsem to řešil do školy já, pod scriptem je v komentáři popis fungování scriptu: function jePrvočíslo(n) {
if(n < 2) return false; var i = n;
while(--i !== 1) if(!(n%i)) return false;
return true;
}
function Síto(od, k) {
od = od < 2?2:od;
for(var pole = [], násobek,
index = 0, číslo = od,
wIndex = 0; číslo <= k; číslo++) {
if(pole[index++]) continue;
if(jePrvočíslo(číslo)) {
pole[wIndex++] = číslo;
for(var činitel = 2; (násobek = číslo * činitel) <= k;
činitel++) pole[násobek - od] = true;
}
} return pole.slice(0, wIndex);
}
/*
Jak to funguje:
Vytvoří se prázdné pole, jehož reference se uloží do proměnné 'pole'
V proměnných 'od' a 'k' (do je žel klíčové slovo cyklu do-while) máme rozsah sítě ve které hledáme prvočísla
V proměnné 'číslo' máme aktuálně zpracovávané číslo
V proměnné 'index' máme aktuální index pole, který koresponduje se zpracovávaným číslem
V proměnné 'wIndex' máme aktuální index pole, na kterém zapisujeme nalezená prvočísla
-> 'wIndex' je vždy menší než 'index', což umožňuje takovéto dvouproudé zpracovávání pole
if(pole[index++]) continue;
-> pole[index++] může obsahovat buď undefined nebo true, pakliže obsahuje true, jedná se o násobek dříve nalezeného prvočísla a přeskočíme tuto periodu cyklu
if(jePrvočíslo(číslo)) { ... }
-> Pakliže je aktuálně zpracovávané 'číslo' prvočíslem, najdeme jeho násobky a zapíšeme na korespondující indexy hodnotu true
pole[wIndex++] = číslo; -> Nalezené číslo zapíšeme dospod pole
for(...) {...} -> vyhledáme veškeré násobky menší než argument 'k' a zapíšeme na korespondující pozici v poli (násobek - od) hodnotu true
return pole.slice(0, wIndex) -> ořízneme vršek 'pole' a zbydou nám pouze vypsaná prvočísla vespod.
*/ |
||
| _es Profil |
#3 · Zasláno: 25. 10. 2011, 13:47:11
Sir Tom:
„Potřebuji algoritmus, který bude fungovat pro n = 10^10 nebo n=10^16 a bude vracet pole v rozumném čase.“ Na tom, že prvočísla nie až tak ľahké zistiť, sú založené aj niektoré súčasné šifrovania. Okrem toho, 10^16 je už za hranicou presného zápisu celých čísel v JS - skús si dať v prehliadači zobraziť „odkaz“ javascript:Math.pow(10,16)+1.
Takže to asi „v rozumnom čase“ v JS nepôjde. |
||
| Sir Tom Profil |
#4 · Zasláno: 25. 10. 2011, 14:26:14
Witiko:
Děkuji - vyzkouším... _es: Ano - vím, že 10^16 je hranice JS, proto jsem to také zvolil jako horní mez. Zajímavý je ale tento skript: // Funkce vrátí pole s prvočinitely k danému číslu (n) // Kód převzat z http://laman.webz.cz/rozklad.php, upraveno function prvociselnyRozklad(n){ var cislo = n; var prvocinitele = new Array(); // Pro n == 1 (jedná se o výjimku) if(cislo==1) prvocinitele.push(1); // Pro libovolné n var i = 2; var max = Math.floor(Math.sqrt(cislo))+1; for(i=2; i<max; i++){ if(cislo%i==0){ prvocinitele.push(i); cislo = cislo/i; max = Math.floor(Math.sqrt(cislo))+1; i--; } } if(cislo>1) prvocinitele.push(cislo); return prvocinitele; } Tato fce vrací pole prvočinitelů daného čísla (n) a ač je n=10^16, tak jej opravdu v rozumném čase vrací. Myslím si, že pokud lze zjistit prvočinitele pro 10^16, tak i lze zjistit všechna prvočísla menší. Jenom nevím, jak ten algoritmus sestavit. (Nemusí být nutně pro n=10^16, ale třeba pro 10^10). |
||
| _es Profil |
#5 · Zasláno: 25. 10. 2011, 14:47:06
Sir Tom:
„Myslím si, že pokud lze zjistit prvočinitele pro 10^16“ Tie ti zistím aj z hlavy. Horšie je, že nezistíš prvočinitele pre 10^16+1 alebo pre 10^16-1, lebo tie nejde v JS použiť ako číslo.
„Tato fce vrací pole prvočinitelů daného čísla (n)“ ...daného jedného čísla, čo je dosť odlišné ako to zistiť pre všetky prirodzené čísla menšie alebo rovné n. |
||
| Sir Tom Profil |
#6 · Zasláno: 25. 10. 2011, 15:04:12
Tak jsem projel všechny 3 algoritmy a porovnal, jak dlouho jim trvá splnit svůj cíl. Použil jsem metodiku kdy jsem do proměnné uložil aktuální počet milisekund od 1.1.1970, pak spustil skript a pak do další proměnné uložil počet milisekund od 1.1.1970 a obě proměnné jsem od sebe odečetl - každý skript jsem testoval 3x. Výsledky:
n = 10^5 (u větších čísel prohlížeč začíná oponovat :) charybdyAlgoritmus - 3654ms, 3671ms, 3628ms eratosthenovoSito - 9495ms, 8047ms, 7874ms Síto - 11967ms, 12056ms, 11929ms _es: Samozřejmě, že máš pravdu. To souhlasím. Jenom jsem myslel, že podobnou myšlenku, která je použita u prvociselnyRozklad() lze modifikovat a aplikovat na můj požadavek. Nevím ale jak. Třeba nějak použít tu odmocninu? Udělat cyklus od n po 2 a do pole ukládat prvočísla nějak na přeskáčku? Fakt nevím... Jestli to nepůjde nijak jinak, tak mi asi nezbude nic jiného než si najít na internetu všechna prvočísla od 2 do 10^16 a uložit je přímo do pole a nepočítat je... |
||
| _es Profil |
#7 · Zasláno: 25. 10. 2011, 15:14:24 · Upravil/a: _es
Sir Tom:
„všechna prvočísla od 2 do 10^16 a uložit je přímo do pole“ Všetky si do poľa neuložíš, lebo čísla okolo 10^16 už nejdú vo formáte, ktorý pre čísla používa JS, presne uložiť. Horná hranica pre presný zápis čísla je 2^53, to je približne 9*10^15. Okrem toho, neviem, či by sa zmestili do pamäte.
|
||
| Joker Profil |
#8 · Zasláno: 25. 10. 2011, 15:39:55
Sir Tom:
„Potřebuji algoritmus, který bude fungovat pro n = 10^10 nebo n=10^16 a bude vracet pole v rozumném čase.“ Asi jediný způsob jak tohle udělat by byl, kdyby ta funkce měla seznam všech prvočísel až do maximálního čísla a vždycky vrátila jeho odpovídající část. A to jste se ještě vůbec nezabývali jiným problémem: Prvočísel menších než 10^16 je zhruba 280 bilionů. Tím za prvé padá i ta varianta se seznamem, protože by měl velikost řádově v petabajtech. Za druhé běžný počítač na takový výpočet nemá dost paměti ani místa na disku, vůbec nemluvě o limitech samotného JS. Pokud vím, maximální velikost JS pole je 2^32 prvků, takže teoreticky je v JS možné vrátit všechna prvočísla v poli pro číslo řádově maximálně 10^11. Kterých je ovšem pořád přes 4 miliardy, takže takové pole by sice teoreticky šlo vrátit, ale otázka je, jak s ním pak půjde pracovat (zejména „v rozumném čase“). „Tato fce vrací pole prvočinitelů daného čísla (n) a ač je n=10^16, tak jej opravdu v rozumném čase vrací.“ Rozložit 10^16 na prvočinitele v rozumném čase zvládnu i já (je to 16 dvojek a 16 pětek). Tak teď už zbývá jen v rozumném čase prozkoumat těch zbývajících 999 999 999 999 999 čísel. „Nemusí být nutně pro n=10^16, ale třeba pro 10^10“ No, tam už těch prvočísel je „jen“ asi 455 milionů. Sice seznam všech by pořád měl několik gigabajtů, ale alespoň teoreticky by to JS zvládl. Podle mého názoru praktická hranice je tak 10 milionů, pak těch prvočísel je zhruba 660 tisíc a jejich seznam by sice měl pár megabajtů, ale už jsme alespoň na únosných hodnotách. |
||
| Sir Tom Profil |
#9 · Zasláno: 25. 10. 2011, 16:11:55 · Upravil/a: Sir Tom
Joker:
Díky za obsáhlé objasnění. Těch 10 milionu asi bude nejlepší jako volba pro horní mez. BTW - 10^16 je horní mez parametru. To téměř každý rozloží z hlavy, ale třeba takové 7141415893421 je už těžší. BTW2 - 10^6 ten můj Charybdy alg. zvládne... (sice mu to docela dlouho trvá - ale jde to...) |
||
| Witiko Profil |
#10 · Zasláno: 26. 10. 2011, 10:49:36 · Upravil/a: Witiko
Sir Tom:
> charybdyAlgoritmus - 3654ms, 3671ms, 3628ms > eratosthenovoSito - 9495ms, 8047ms, 7874ms > Síto - 11967ms, 12056ms, 11929ms Ten test je ale neprůkazný, jelikož moje funkce pojímá argumenty od a do, zatímco dvě výše zmíněné funkce pracují vždy od čísla 2. Pakliže se pracuje od čísla 2, je možné zcela odebrat 13. řádek jePrvočíslo(číslo), jelikož veškerá čísla zbývající v sítu budou prvočísly. Mnou zaslaný algoritmus poté vede: http://jsperf.com/vypocet-prvocisel Tzn. pokud chceš hledat vždy od spodu, tak ti postačí tato funkce:
function Síto(k) {
for(var pole = [], násobek,
index = 0, číslo = 2,
wIndex = 0; číslo <= k; číslo++) {
if(pole[index++]) continue;
pole[wIndex++] = číslo;
for(var činitel = 2; (násobek = číslo * činitel) <= k;
činitel++) pole[násobek - 2] = true;
} return pole.slice(0, wIndex);
}for cyklu na řádcích 7 a 8, kdy můj cyklus projde skutečně pouze násobky čísla, zatímco eratosthenovoSito prochází po jednom všemi čísly.
|
||
|
Časová prodleva: 12 let
|
|||
0