Mersenne Prím

[Attila Válinth]

Valaki beszáll? Csinálunk egy csoportot? :))

https://www.mersenne.org

[ZilogR]

Ma lomoltam a régi cuccaim között és mit nem találtam?! Az egyik legelső 15C programom. A dátum érdekes, mert úgy emlékeztem, hogy az első gépész évemben vettem, az pedig '99 őszén indult, szóval hamarabb vettem, hmm... Már kihagynak a neuronok.

Nem fejtettem vissza, de nem tűnik olyan nagyon rafináltnak, szerintem a klasszikus favágó módszer van leprogramozva: egy kettessével lépkedő végtelen ciklusba ágyazott oszthatóság vizsgálat: ahogy tanultam még BASIC-ben 11 éves koromban :P Önmagában a visszaszorzások eléggé megkérdőjelezik a használhatóságát, de ha végtelenül pontos lenne, ez jól működne, kár hogy vérlázítóan lassú, mivel ez egy brute-force próbálgatós lényegében.

Viszont adja is a kérdést: hogyan kell prímeket keresni, mondjuk 1-től 1000-ig érdemes is kipróbálni, az bármin lefut véges idő alatt.

[Attila Válinth]

Elvileg DM42-re is ua...

[gyapo]

2020 December 11, Friday 20:43 ZilogR, you wrote:
Z> Viszont adja is a kérdést: hogyan kell prímeket keresni, mondjuk 1-től
Z> 1000-ig érdemes is kipróbálni, az bármin lefut véges idő alatt.

Beírtam a calculatormatik programba az 1000-et, és 0.2 másodperc múlva
kaptam egy listát 1-től 1000-ig, amiben mindegyik számhoz oda van
írva, hogy prím vagy nem. :)

Üdv.: gyapo

[ZilogR]

:D te nyertél és milyen igaz, csökkentsük az energiabevitelt, ha lehet. Ezért sem értem pl., miért nem használhatnak az egyetemisták mindenféle földi jóval felszerelt számológépeket, azon kívül, hogy csalnának velük a vizsgán.

[Attila Válinth]

Szívesen beírnám a DM42-be de komolyan meghaladja a képességeimet. Sajnos már a 004 programsornál elakadtam.

Persze ez nem csoda :D

ZilogR a következőt írta (2020. december 11., péntek, 20:43:58 UTC+1):

[ZilogR]

Sok út vezet az igazsághoz, először is a kézikönyvet szerezd be. Mindjárt feldobom a 42S kézikönyvet színesben, az jobb lesz, mint a SwissMicros fekete-fehér kézikönyve, mert ott nem látszanak a menü funkciók (túl sötét a scan).

Az INTEGER függvény itt IP (Integer Part) és az eredeti 42S-en itt található:

Az "add", "sub", "mul" és "div" az az én fejlövésem volt, az az "add", "substract", "multiple" és "divide" rövidítése volt, azaz magyarosítve: "add hozzá", "vond ki", "szorozd be" és "oszd el", mert sokszor kihagyhatja valaki pl. a kivonásjelet egy ilyenben: "STO-0", jobb e helyett azt írni, hogy "STO add 0", szóval ez:  "add", "sub", "mul" és "div" ugyanaz, mint "+", "-", "×" és "÷".

Aztán visszatérve a 42S-hez, a kézikönyv itt: HP42S (színes kézikönyv)

Ebben kötelező olvasmány az egész :D, de legalább az 1., 2., 3., 4., 5. fejezetek, amiben az alapok meglesznek. Ha a mostani kérdést akarjuk előszedni, akkor a 4. fejezetet érdemes elolvasni, abban megtalálható, hogy hogyan lehet (3 módon) hozzáférni az egyes funkciókhoz:

Az XEQ lesz valószínűleg az, amit sokat fogsz használni, de persze ehhez kell tudi a függvény nevét, vagy inkább a CUSTOM menü, a HP41-en ez volt a billentyűhöz rendelés (ASSIGN parancs), ha már kialakult, miket használsz sűrűn. A HP41-en is így működik, érdemes ezeket kipróbálni, főleg ha befigyel a 41-es is... :) 

Azért jó ám az, hogy ilyen csemegéket hozol nekünk, legalább lesz egy kis rálátás, mi is van manapság kalkulátor fronton. Én erőltettem Steinmann-nál, hogy hagyja meg a billentyűzetet és áruljon csak updated alaplapokat kit-ben, mert akkor megvan a tok, megvannak a szuper billentyűk, de nem akarta. Ő komplett gépet akart és a vége ez lett.

Attila, nyomkodd sokat ezeket az újraálmodott csodákat, én is leszedem a 42S emulátort és előszedem a 41-emet, ideje megismerkednem velük.

[ZilogR]

Persze az összes kép hiányzik belőle. Igazából megpróbálhatná a Google nem elb@szni azt, ami működött... Engem nem keresett meg két szilicium-völgyi k..ög bekopogva az ajtómon, hogy akarok-e új felületet, de cserébe nem fog működni, itt írjam alá...

[Attila Válinth]

Hajjjjjj köszönöm! Megint van feladat a munkáim mellé :))) Én akartam Uram.

Megjött a 41 is csak az irodában maradt :)

Kezdem azt hinni, hogy a HP az egyik legbonyolultabb sz.gép:)))

ZilogR a következőt írta (2020. december 12., szombat, 17:52:49 UTC+1):

[ZilogR]

Akkor megismétlem, mert még mindig nem látszanak nálam:

Sok út vezet az igazsághoz, először is a kézikönyvet szerezd be. Mindjárt feldobom a 42S kézikönyvet színesben, az jobb lesz, mint a SwissMicros fekete-fehér kézikönyve, mert ott nem látszanak a menü funkciók (túl sötét a scan).

Az INTEGER függvény itt IP (Integer Part) és az eredeti 42S-en itt található:

Az "add", "sub", "mul" és "div" az az én fejlövésem volt, az az "add", "substract", "multiple" és "divide" rövidítése volt, azaz magyarosítve: "add hozzá", "vond ki", "szorozd be" és "oszd el", mert sokszor kihagyhatja valaki pl. a kivonásjelet egy ilyenben: "STO-0", jobb e helyett azt írni, hogy "STO add 0", szóval ez:  "add", "sub", "mul" és "div" ugyanaz, mint "+", "-", "×" és "÷".

Aztán visszatérve a 42S-hez, a kézikönyv itt: HP42S (színes kézikönyv)

Ebben kötelező olvasmány az egész :D, de legalább az 1., 2., 3., 4., 5. fejezetek, amiben az alapok meglesznek. Ha a mostani kérdést akarjuk előszedni, akkor a 4. fejezetet érdemes elolvasni, abban megtalálható, hogy hogyan lehet (3 módon) hozzáférni az egyes funkciókhoz:

Az XEQ lesz valószínűleg az, amit sokat fogsz használni, de persze ehhez kell tudi a függvény nevét, vagy inkább a CUSTOM menü, a HP41-en ez volt a billentyűhöz rendelés (ASSIGN parancs), ha már kialakult, miket használsz sűrűn. A HP41-en is így működik, érdemes ezeket kipróbálni, főleg ha befigyel a 41-es is... :) 

Azért jó ám az, hogy ilyen csemegéket hozol nekünk, legalább lesz egy kis rálátás, mi is van manapság kalkulátor fronton. Én erőltettem Steinmann-nál, hogy hagyja meg a billentyűzetet és áruljon csak updated alaplapokat kit-ben, mert akkor megvan a tok, megvannak a szuper billentyűk, de nem akarta. Ő komplett gépet akart és a vége ez lett.

Attila, nyomkodd sokat ezeket az újraálmodott csodákat, én is leszedem a 42S emulátort és előszedem a 41-emet, ideje megismerkednem velük.

[Tolosa]

Mekkora a fizikai HP-42S maximális számábrázolási képessége?

Az emulátort próbálgattam Mersenne -prím ügyben és a 2^9941-nél még nem akad ki, kiszámolja. Ugye ez nem lehetséges a fizikai gépnél?

Még a PRIME gépem se tud ekkora értékkel számolni.

[Attila Válinth]

Tolosa, file-ként nincs meg neked a program. Rá lehetne tölteni a DM42-re. :))

[Attila Válinth]

ZilogR, A 011 INT utasítást már nem engedi. Nem adja be az utasítás készletet és pityeg.. :)))

[Attila Válinth]

Most Ok :)

[ZilogR]

Akkor alakul... :) mondom, az INT az IP a 42S-en.

Tolosa: a fizikai gép számábrázolási határ 1E500 (alatt egy kicsivel).

[Tolosa]

Gondoltam, hogy nem lehet valós érték az a 3.46e2992 érték, amit az emulátor kiszámol!:-)

Valahol sejtettem is, hogy ennyi a max. amit írtál, mert a HP35S gépem is ennyit tud.

[Attila Válinth]

Beírtam ZilogR. Hogyan futtatom? Nem tudom működik e...?

[Tolosa]

Attila, EZEN AZ OLDALON találhatsz egy csomó HP-42S programot, tudsz velük gyakorolni.

Ha már volt, akkor bocs.

[ZilogR]

Kell neki egy páratlan kezdőérték a stack-be, pl. 3 ENTER és utána XEQ és ha minden igaz, akkor a soft-menüben (kijelző alján) ott kell lennie annak a prgram névnek, amit te adtál neki (gondolom LBL E -vel kezdted, így egy E -nek kell ott lennie) - de ezt csak a kézikönyv alapján mondom, mert soha nem programoztam 42S -t. :)

[Tolosa]

Az alábbi oldalon pedig szintén vannak HP-42S programok. A "raw" kiterjesztésű linkek működnek.

[Attila Válinth]

Hát nem fut. Az utolsó sora jelenik meg ami .END. :)

[ZilogR]

Háát, akkor elő a kézikönyvet és a szerint megtanulni :)

[Tolosa]

HP-35S kisgépen egészen szépen fut a programod ZilogR /egy kis módosítással a helyi adottságok miatt/.

ZilogR a következőt írta (2020. december 11., péntek, 20:43:58 UTC+1):

[Attila Válinth]

Ügyes vagy Tolosa! :)

[Tolosa]

Hát ehhez nem kellett ügyesség Attila, csak bemásoltam a gépbe. Ügyes ZilogR volt, aki megcsinálta a programot.

[Tolosa]

Most beírtam a HP-42S emulátorba is és rendesen fut a program. Szóval nálad is működnie kell, Attila.

[Tolosa]

Ott így néz ki:

00 { 43-Byte Prgm }
01▸LBL E
02 RCL 00
03 SQRT
04 IP
05 1
06 +
07 RCL+ 03
08 STO 02
09▸LBL 00
10 RCL 02
11 IP
12 STO 01
13 RCL 00
14 RCL÷ 01
15 IP
16 RCL× 01
17 RND
18 RCL 00
19 X=Y?
20 GTO 01
21 DSE 02
22 GTO 00
23 RCL 00
24 STOP
25▸LBL 01
26 2
27 STO+ 00
28 GTO E
29 END

[Tolosa]

Az az INT a HP-42S esetében IP. A Catalog FCN utasításai között találod meg.

[Tolosa]

Szóval ahogy ezt már /most látom/ ZilogR is mondotta volt.:-)

[Attila Válinth]

:) akkor bepötyögöm ismét

[Attila Válinth]

Beírtam. És még mindig nem tudom futtatni :)

[Attila Válinth]

Nem írja be a programsorba valamiért

[Tolosa]

Mit nem ír be?

[Tolosa]

XEQ "E"-vel indítod? Futtatás előtt beírtad, hogy 3 STO 00 és 0.00101 STO 003 ?

geov...@gmail.com a következőt írta (2020. december 13., vasárnap, 14:45:03 UTC+1):

[Attila Válinth]

Most ok :) dolgozik

[Attila Válinth]

Ezzel játszani kell Tolosa. Most, hogy beírtam előtte amit mondtál, most megint nem fut. Csak a r/s gombbal 

[Tolosa]

Az jogos, mert -ahogy ZilogR írja is az ismertetőben-, minden kijelzett érték után R/S-el indul a következő prímszám keresése.

[Tolosa]

Ezt írja ZilogR:

"A program, ha    prímszámot talál megáll, kijelzi a talált számot, majd tovább
futtathatjuk a R/S billentyűvel." 

Lehetne automatizálni, de akkor egyrészt módosítani kell a programot, másrészt meg folyamatos futásnál hogyan olvasod ki az eredményeket?

[Tolosa]

Ha folyamatos futásra akarod állítani, akkor iktass be az R/S utasítás helyére  PSE utasítást kétszer egymás után. Így sorban kényelmesen leolvashatod a kijelzett értékeket.

[Tolosa]

Helyesebben a STOP utasítás helyére.

[Attila Válinth]

Nem könnyű egy masina :D

Vajon a Cy,x valószínűség számítás melyik bugyrában lapulhat? :)))

[Attila Válinth]

PROB 

[ZilogR]

Ahogy nézem a fentieket, alakulgatnak a dolgok! :) hajrá!

[Attila Válinth]

Alakul. A tehetségeit kutatom fel :D

[ZilogR]

Akkor írd át úgy, hogy 1000-ig fusson csak és ne legyen benne STOP. Kíváncsi vagyok, mennyire gyors.

[Tolosa]

Utána meg úgy, hogy a talált prímszámok közül válogassa ki a Mersenne-prímeket!:-)

Ha csak 1000-ig számoltatsz, nem kell sokat dolgoznia a gépnek ez ügyben.:-)

[ZilogR]

Végülis 10 számjegyig bármilyen számológépen el lehet menni, azaz 10^11-ig is futhat :) de akkor csak a Mersenne-prímeket kell tesztelni abból már több van, összesen 8 és elmondhatjuk, hogy annyit tudunk, mint Euler tudott 1772-ben.

Ezzel 687 jegyű primszámokat is teszteltek: https://en.wikipedia.org/wiki/SWAC_(computer) és még csak 1952-ben vagyunk (nincs tranzisztoros számítógép sem még).

Azt nem tudom, hogy a DM42S milyen számábrázolással van megáldva. Ha több, mint a 15 jegy, akkor lehet próbálkozni megdönteni Euler-t.

[Attila Válinth]

Kedves ZilogR. Megtennéd ha nem teher, hogy elmagyarázod nekem ezt a kis programot?

Lehet, csak én nem értem ám... Ezért bocs!
:)))

[ZilogR]

Hogyne, hogyne ;) de éppen melóban, bár HomeOffice, na de akkor is :) - én éjjel aktiválódom, de már nem tart sokáig, Ünnepek alatt szabi, hamarosan.

[Attila Válinth]

:))) nagyon várom ám.

[ZilogR]

:) szokás szerint kérek egy kis haladékot, mondjuk péntek estig, kb akkortól már vége a melónak. Az év vége hajtós szokott volt lenni :)

A fenti programban kapásból találtam egy hibát, ami a 11-es sorban levő egészrész utasítás minek van betéve a ciklusba (LBL 00), mert így mindig veszi az egész részét az R02-ben levő számnak, pedig a cikluson kívül is el lehet bele tenni, ez jelentősen is gyorsíthat a programon, másrészt a szövegben szerepel az R03 változó, mint ciklusváltozó, aminek az értéke 0.00101, tehát egy 0-tól 1-ig futó számláló, ami 1-essével nő. DE a programban SEHOL nem nyúlunk az értékéhez! Szóval ez a program kb. csinálja a dolgát, de vannak benne homályos részek, átnézem és újra megszülöm, szóval Tolosa, még véletlenül se voltam se ügyes, se túl pengeagyú ebben, de beszélgetés indításhoz épp jó volt ide :)

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

Egy kicsit azért lehet magyarázni már most is, mondjuk kezdjük azzal, hogy hogyan működik egy primszám kereső.

A legegyszerűbb primszám kereső módszer az az, hogy veszünk egy (kettőnél nagyobb) egész számot, vesszük a INT(négyzetgyökét)+1 és megnézzük, eddig a számig találunk-e egész osztóját az eredeti számnak kettőtől indulva. Pl.:

A 35-ről kell eldönteni, hogy primszám-e: Vesszük a négyzetgyökét, az kb. 5,9 az INT(5,9)+1 = 6, eddig kell elmenni és megnézni, hogy a 35 osztható-e bármelyik egész számmal 6-ig:

35/2 = 17,5, ez nem egész, tehát a 2 nem osztója,  
35/3 = 11,66..., ez nem egész, tehát a 3 nem osztója,
35/4 = 8,75, ez nem egész, tehát a 4 nem osztója,
35/5 = 7 ez egész, tehát az 5 osztója, azaz a 35 nem prím, ezért a 6-ra már meg sem kell vizsgálni.

Ha a 37-ről kell eldönteni, hogy primszám-e: Vesszük a négyzetgyökét, az kb. 6,1 az INT(6,1)+1 = 7, eddig kell elmenni és megnézni, hogy a 37 osztható-e bármelyik egész számmal 7-ig:

37/2 = 18,5, ez nem egész, tehát a 2 nem osztója,  
37/3 = 12,33..., ez nem egész, tehát a 3 nem osztója,
37/4 = 9,25, ez nem egész, tehát a 4 nem osztója,
37/5 = 7,4 ez nem egész, tehát az 5 nem osztója,
37/6 = 6,16... ez nem egész, tehát a 6 nem osztója,  
37/7 = 5,28... ez nem egész, tehát a 7 nem osztója,
ÉS elértük a ciklus végét is és nem találtunk osztót,
tehát a 37 prím.

Namost ezen lehet gyorsítani, pl úgy, hogy az addig talált prímeket eltesszük egy tömbben és utána már csak azokkal kell az osztást elvégezni, de ez azt is jelenti, hogy mindig a 3-tól kell kezdeni a prímek keresését. 

A másik gyorsító módszer az az, hogy csak a páratlan számokat kell tesztelni, mind mint olyan szám, amiről el kell dönteni, hogy prím-e, másrészt, amivel teszteljük magát a számot, hogy osztható-e. Ez utóbbi azért fontos, mert egy páratlan számnak biztosan nem lesz páros osztója (mert akkor a 2 is osztója lenne, azaz saját maga is páros lenne, márpedig csak páratlanokat tesztelünk).

Ennyi ma, akkor van egy hibás program, ami mégiscsak fut. Ki kell deríteni, hogy miért!?

[ZilogR]

:D :D :D Nem akkor, hanem tegnap este nem voltam már pengeagyú, de lehet erre már rá is jöttetek, szóval a magyarázat az R03-ra és a cikluson belüli R02 INT-re:

Ez volt az esti fáradt állapotos magyarázat, ami hibás:

"A fenti programban kapásból találtam egy hibát, ami a 11-es sorban levő egészrész utasítás minek van betéve a ciklusba (LBL 00), mert így mindig veszi az egész részét az R02-ben levő számnak, pedig a cikluson kívül is el lehet bele tenni, ez jelentősen is gyorsíthat a programon, másrészt a szövegben szerepel az R03 változó, mint ciklusváltozó, aminek az értéke 0.00101, tehát egy 0-tól 1-ig futó számláló, ami 1-essével nő. DE a programban SEHOL nem nyúlunk az értékéhez! Szóval ez a program kb. csinálja a dolgát, de vannak benne homályos részek, átnézem és újra megszülöm, szóval Tolosa, még véletlenül se voltam se ügyes, se túl pengeagyú ebben, de beszélgetés indításhoz épp jó volt ide :)"

És a valódi ok:

A ciklusnak tehát el kell futnia 2-től INT(SQRT(szám))+1 -ig, hogy megvizsgáljuk, ezekkel az egészekkel osztható-e a vizsgált szám, ezért kell a 0.00101 -et tárolni az R03-ban.
A ciklus utasítások a HP számológépeken két utasítással vannak megvalósítva, az egyik az ISG, a másik a DSE. Az ISG az "Increment and Skip if Greater than" (növeld és ugord át (hagyd ki), ha nagyobb), míg a DSE a "Decremet and Skip if less than or Equal to" (csökkentsd és ugord át (hagyd ki) ha kisebb vagy egyenlő) rövidítése. Azaz a ciklus szervező utasítások egy-egy feltételvizsgálatot jelentenek. Minden feltételvizsgálat minden HP gépen úgy hajtódik végre, ha az eredménye IGAZ, akkor átugorja (kihagyja) a közvetlenül utána következő utasítást (csak azt az egyet).

Az ISG és DSE után egy változót (ciklusváltozó) kell megadni, azaz meg kell mondani, melyik változó értékét akarjuk növelni (ISG) vagy csökkenteni (DSE), pl. a programban a 021 DSE 2 utasítás csinálja a csökkentését és vizsgálatát az R02 regiszternek.

A ciklus kezdő és végértékét és lépésközét szintén meg kell adni, ennek a formája: nnnnn.xxxyy, ahol nnnnn egy előjeles (+/-) érték, a ciklusváltozó aktuális értéke, xxx a végérték és yy a lépésköz. Fontos, hogy ezek valóban ennyi jegyet is jelentenek, tehát az egész rész +/-99999 tartományon, a végérték 0...999 tartományon, a lépésköz 1...99 tartományon állítható be.

Általánosan egy ciklus szerkezete áll:
a.) egy inicializálásból, ahol a ciklusváltozót beállítjuk,
b.) egy cimkéből, ami a ciklus kezdetét jelöli,
c.) egy ciklusmagból, ahol csinálunk valamit és
d.) egy ciklust lezáró ciklusváltozót módosító majd az értékét megvizsgáló utasításból,
e.) amit az ugró utasítás a ciklus elejére, majd
f.) a ciklus után lefutó utasítások zárnak:

Egy számláló, ami kiírja a páros számokat 2-től 10-ig az 1-el indul és 5-ig fut és így valósítható meg:

1.00501 STO 1  a.) Inicializálás

LBL 0          b.) Cimke

RCL 1          c.) Ciklusmag

INT            c.) Ciklusmag

2              c.) Ciklusmag

×              c.) Ciklusmag

PSE            c.) Ciklusmag  

ISG 1          d.) Ciklusváltozót növelő utasítás és feltételvizsgálat

GTO 0          e.) Ha még nem értük el a végértéket, akkor vissza a ciklus elejére

RTN            f.) Ha elértük, vége a ciklusnak és jöhetnek az az utáni utasítások (itt vége a programnak)

Ennek ismeretében már érthető R03 szerepe és az, miért kellett az IP -t a cikluson belül elhelyezni.

Tessék kérdezni, ha a fenti nem világos ;)

[ZilogR]

... és hogyan valósítható meg a számláló, ha kettessével számlálunk? És ha visszafelé számlálnánk 10-től 2-ig? Lehet továbbgondolni!

[ZilogR]

Na, ezt még elárulom, de csak az első felét, a másikat már várom ide postolni!

Egy számláló, ami kiírja a páros számokat 2-től 10-ig, 2-vel indul és 10-ig fut, a lépésköz pedig 2:

2.01002 STO 1  a.) Inicializálás

LBL 0          b.) Cimke

RCL 1          c.) Ciklusmag

INT            c.) Ciklusmag  

PSE            c.) Ciklusmag  

ISG 1          d.) Ciklusváltozót növelő utasítás és feltételvizsgálat

GTO 0          e.) Ha még nem értük el a végértéket, akkor vissza a ciklus elejére

RTN            f.) Ha elértük, vége a ciklusnak és jöhetnek az az utáni utasítások (itt vége a programnak)

Ugye figyelitek a színeket fent a szövegben és a programlistában?!? Nem véletlen!!! :)

[Attila Válinth]

ZilogR, mi haszna van a szürke hétköznapokban? RAN

:)

[ZilogR]

Háát, mondjuk az, hogy tudsz ciklust csinálni :)

Volt valahol egy jópofa dolog a ciklusok minimális számának lefutásáról, asszem' FORTRAN-ban... Meg is van (Wikipedia): "Amikor a bizottság azt kezdte el vitatni, hogy a DO ciklus minimális végrehajtási száma 0 (elöltesztelő) vagy 1 (hátultesztelő) legyen, Loren Meissner azzal az ötlettel állt elő, hogy a minimális végrehajtási szám 2 legyen. Ezt azzal indokolta, hogy ha valamit egyszer akarunk megcsinálni, akkor oda nem kell ciklus." :)

[Attila Válinth]

Akkor csak ezért szerepel a programozható számológépeken? :)

[ZilogR]

Nem igazán :). A ciklusszervezés a programozási módszerek három alapelemének egyike. Itt találsz több infót: https://dtk.tankonyvtar.hu/hu/tartalom/tamop425/0008_simon/Simon_A_progr_alapjai.pdf#page=33 (ha letölti a mocsok böngésző, akkor a 33. oldal a pdf-ben).

Az a "RAN" az miaz?!?