Basic i zabawa z liczbami pierwszymi
: 01 sty 2020, 22:23
Taki temat na dziś. Zainspirowany przygodą z C++:
https://eduinf.waw.pl/inf/utils/010_2010/0209.php
zechciałem napisać w BASIC na C64 programik do generowania liczb pierwszych.
W powyższym artykule autor pokazuje, jak taki programik można fajnie zoptymalizować, i to rzeczywiście działa. W C++.
Natomiast gdy napisałem to w BASIC, to ku mojemu zdziwieniu, ostatnie ulepszenie zamiast jeszcze bardziej przyspieszyć generowanie, to zwolniło. Uwaga: programiki odpalam nie na C64, tylko na emulatorze CCS64 na laptopie, nie wiem czy to może mieć jakieś znaczenie, ale dla porządku podaję.
Najpierw wstawię wersję programu, która powinna działać nieco wolniej, a potem tę, która powinna działać szybciej. Każdy z nich ma za zadanie wygenerować jak najwięcej liczb pierwszych w 10 sekund:
1:
2:
Ta druga powinna działać szybciej, bo nie sprawdza wszystkich podzielników po kolei, tylko omija te podzielne przez 2 i 3.
Być może coś zrobiłem źle.
A być może zbyt wiele czasu zajmuje generowanie podzielników.
Tyle że w C++ działało pięknie.
Ktoś z Was ma może jakiś pomysł?
Uprzedzając pytanie: sprawdzałem także dla 60 sekund. Nie widzę zysku na szybkości dla większych liczb. Chyba że dla jeszcze większych zacznie być widać...
https://eduinf.waw.pl/inf/utils/010_2010/0209.php
zechciałem napisać w BASIC na C64 programik do generowania liczb pierwszych.
W powyższym artykule autor pokazuje, jak taki programik można fajnie zoptymalizować, i to rzeczywiście działa. W C++.
Natomiast gdy napisałem to w BASIC, to ku mojemu zdziwieniu, ostatnie ulepszenie zamiast jeszcze bardziej przyspieszyć generowanie, to zwolniło. Uwaga: programiki odpalam nie na C64, tylko na emulatorze CCS64 na laptopie, nie wiem czy to może mieć jakieś znaczenie, ale dla porządku podaję.
Najpierw wstawię wersję programu, która powinna działać nieco wolniej, a potem tę, która powinna działać szybciej. Każdy z nich ma za zadanie wygenerować jak najwięcej liczb pierwszych w 10 sekund:
1:
Kod: Zaznacz cały
10 print "p=6k+-1"
20 cz=time/60
30 print 2; 3; 5;
40 l=0
50 l=l+1
60 d=-1
70 p=(6*l)+d
110 for dz=5 to sqr(p)
120 w=p/dz
130 if w=int(w) goto 180
140 next dz
150 print p;
160 sr=time/60
170 if sr-cz >=10 goto 200
180 if d=-1 then d=1 : goto 70
190 goto 50
200 print "minelo 10 sekund" : stopKod: Zaznacz cały
10 print "dz=6k+-1"
20 cz=time/60
30 print 2; 3;
40 l=0
50 l=l+1
60 d=-1
70 p=(6*l)+d
80 ldz=0
90 ldz=ldz+1
100 dp=-1
110 dz=(6*ldz)+dp
120 if dz > sqr(p) goto 170
130 w=p/dz
140 if w=int(w) goto 200
150 if dp=-1 then dp=1 : goto 110
160 goto 90
170 print p;
180 sr=time/60
190 if sr-cz >=10 goto 220
200 if d=-1 then d=1 : goto 70
210 goto 50
220 print "minelo 10 sekund" : stopByć może coś zrobiłem źle.
A być może zbyt wiele czasu zajmuje generowanie podzielników.
Tyle że w C++ działało pięknie.
Ktoś z Was ma może jakiś pomysł?
Uprzedzając pytanie: sprawdzałem także dla 60 sekund. Nie widzę zysku na szybkości dla większych liczb. Chyba że dla jeszcze większych zacznie być widać...
