Optimalisert kode for å finne primtall

[Nebuchadnezzar]

Merkelig nok, virker det ikke som den innebydge funksjonen i matlab for å finne primtall er spesielt optimalisert. Når jeg kjørte den mot min kode, var min som oftest raskere. Om enn ikke med så mye.

Spørsmålet mitt blir da like mye matematisk som basert på programmering.

Hva er den mest effektive metoden en kan benytte seg av for å teste om et tilfeldig tall er primtall i matlab?

Selv tenkte jeg med en gang "Sieve of Eratosthene" men den var litt vanskelig å implementere.

Hadde vært artig om noen skrev noen koder, og sammenlignet for å teste hastighet, og kanskje også nøyaktighet ^^

------------------------------------------

Code: Select all

function Y = Primtall(a)
n=1;
if a<2
    Y=0;
    return
else
    for i=2:n:(floor(sqrt(a)))
        if a/i==round(a/i)
            Y=0;
             return
        end
        n=n+1;
    end
end
Y = 1;
end

----------------------------------------------

Litt usikker på om denne funker, men testet den for et par tall. Og den gir meg i det minste rett svar, for de få tallene jeg prøvde.

edit: virker ikke helt optimalt, for defleste verdier er den lavere. Mens for ndre går dn i taket.

[Thales]

artig at du nevner dette Nebu, da jeg har sett litt på det samme i det siste. Her er en funksjon som jeg fant på nettet som skal være ganske så optimalisert så vidt jeg vet:

(javascript code)

Code: Select all

function Eratosthenes(limit) {
    var all = [];
    var primes = [2];
    var prime = 3;
    var idx = 0;
    var x, j;

    while (prime <= limit) {
        flag = true;
        for (x = 0; x < all.length; x++) {
            if (all[x] == prime) {
                flag = false;
                break;
            }
        }
        if (flag) {
            primes.push(prime);
            j = prime;
            while (j <= (limit / prime)) {
                all[idx++] = prime * j;
                j++;
            }

        }
        prime += 2;
    }
    return primes;
}

[drgz]

Merkelig nok, virker det ikke som den innebydge funksjonen i matlab for å finne primtall er spesielt optimalisert. Når jeg kjørte den mot min kode, var min som oftest raskere. Om enn ikke med så mye.

Code: Select all

p = 961748941;
N = 1000;

tic
for k = 1:N
    isp = Primtall(p);
end
avgT1 = toc/N

tic
for k = 1:N
    isp = isprime(p);
end
avgT2 = toc/N

avgT1 (din kode) = 0.0133
avgT2 (innebygd) = 5.9488e-4

Med andre ord er den innebygde over 20 ganger raskere enn din kode for dette eksempelet. I tillegg fungerer den innebygde på vektorer som input. Det er mulig din er raskere for små primtall, men det er mest sannsynlig pga den innebygde har mer omfattende sjekker på input.

[drgz]

artig at du nevner dette Nebu, da jeg har sett litt på det samme i det siste. Her er en funksjon som jeg fant på nettet som skal være ganske så optimalisert så vidt jeg vet:

Eratosthenes er vel kun bra hvis man skal finne alle primtall mellom 2 og n, og ikke for å sjekke om n er et primtall eller ei. For store verdier av n så har man andre mer avanserte metoder (er nevnt haugevis av tester under primtall på engelsk wikipedia, noen greie å implementere, andre ikke:p).

[Nebuchadnezzar]

Nå aner jeg ikke om jeg gjør noe galt:p Men jeg tok og laget en funksjon, som kjørte disse to kodene 5000 ganger, for primtall mellom 2^10 og 2^32.
2^32 er maksen i matlab, en liten del av resultatet er under

Code: Select all

Elapsed time is 0.000065 seconds.
Elapsed time is 0.001943 seconds.

Elapsed time is 0.000050 seconds.
Elapsed time is 0.001561 seconds.

Elapsed time is 0.000027 seconds.
Elapsed time is 0.003012 seconds.

Elapsed time is 0.000037 seconds.
Elapsed time is 0.002501 seconds.

Elapsed time is 0.000027 seconds.
Elapsed time is 0.003563 seconds.

Elapsed time is 0.000031 seconds.
Elapsed time is 0.002437 seconds.

Elapsed time is 0.000036 seconds.
Elapsed time is 0.001746 seconds.

Elapsed time is 0.000117 seconds.
Elapsed time is 0.002616 seconds.

Elapsed time is 0.001234 seconds.
Elapsed time is 0.003054 seconds.

Elapsed time is 0.064312 seconds.
Elapsed time is 0.002207 seconds.

Min kode er øverst, den innebygde er nederst.
Totalt ble resultatet

Code: Select all

ans =

   0.002993142481808


ans =

   0.002219492700723

Der min er øverst. Virker ikke så galt. Men kanskje jeg tester på feil metode :p Virker som min er raskere for de fleste tall, men har noen tall den bruker evigheter på.

Koden jeg kjørte, for å teste hvilken som er raskest :p

Code: Select all

function Tidtall(n,h,k)
q=0;
p=0;

for i=1:n

y = 2^(h) + round( 2^(h) + ((2^(k)-2^(h))*rand ));

fprintf('\n');

tic;

Primtall2(y);

toc;

q=toc+q;

tic;

isprime(y);

toc;

p=toc+p;

i=i+1;

end

q/n

p/n

end

[drgz]

Det du heller må gjøre er å kjøre koden din N ganger for samme input, og deretter dele total kjøretid på N. Da vil du finne ut hvilken kode som er raskest.

Men som sagt tidligere så er nok ikke den innebygde algoritmen optimalisert for å sjekke primtall da det finnes haugevis av andre mye raskere algoritmer.

Du kan jo også teste den koden jeg gav til deg i den andre tråden din, den er nok også en god del raskere enn din egen kode.

[espen180]

Jeg skrev denne koden som ennå er tregere enn den innebygde isprime men kommer veldig nær.

Code: Select all

function result = isprime2(n)
    ps=primes(floor(sqrt(n)));
    rems=rem(n,ps);
    result = all(rems);
end

[drgz]

Jeg skrev denne koden som ennå er tregere enn den innebygde isprime men kommer veldig nær.

Code: Select all

function result = isprime2(n)
    ps=primes(floor(sqrt(n)));
    rems=rem(n,ps);
    result = all(rems);
end

Rart den går saktere, for den er helt identisk med den innebygde isprime-funksjonen

Code: Select all

.
.
.
p = primes(ceil(sqrt(n)));
for k = 1:numel(isp)
   isp(k) = all(rem(X(k), p(p<X(k))));
end

Dropper man alle sjekkene den innebygde gjør så bør de være "identisk" i kjøretid.