very large integers

C/C++

Sziasztok,

A problemam a kovetkezo lenne. Van egy c-ben irt alkalmazasom amely pillanatnyilag 64 bit-ig kepes integert kezelni es egy olyan C library erdekelne amivel kepes lenne _legalabb_ 4096 bites unsigned integerekkel dolgozni.

Ismer valaki ilyet LGPL vagy BSDL licensz alatt?

Koszi elore is :)

  • 2273 megtekintés

( rigidus | 2006. 03. 22., sze – 15:45 )

Hat, atragtam magamat rajta es mar az elejen gondok vannak vele. Lenyegeben annyit szerettem volna csinalni mielott beepitem elesbe, hogy beolvasok stdin-rol par byte-os (20-25) binaris adatot, azt beleteszi a "data" valtozoba, majd kiirja. Viszont segfaultal leall amikor megkapja az inputot. Probaltam az mpz_inp_str/mpz_out_str parossal is, az viszont csak karakteres bemenetet fogad ertheto modon, ez viszont nem jo.

A kezdetleges kod igy nez ki:

#include "stdio.h"
#include "stdlib.h"
//#include "stdint.h"
//#include "limits.h"
#include "gmp.h"
//#include "math.h"

size_t readSize;
mpz_t data;

void readStream()
{
mpz_init(data);
readSize = mpz_inp_raw(data, stdin);
// mpz_out_raw(stdout, data);
printf("\n%d\n", readSize);
mpz_clear(data);
}

int main(int argc, char *argv[])
{
readStream();
return EXIT_SUCCESS;
}

A segitseget koszi elore is. :)

---------------------
Ригидус а бетегадьбол

A GMP manual szerint:
size_t mpz_inp_raw (mpz_t rop, FILE *stream)
Input from stdio stream stream in the format written by mpz_out_raw, and put the result in rop.
Biztos ebben a formatumban olvasol be binary adatot?
Ha nem, akkor talan probald meg a gmp_scanf fuggvenyt - igaz az nem binary adatot olvas.

HTH:
Babszem

"Biztos ebben a formatumban olvasol be binary adatot?"

uhh, ez elkerulte a figyelmemet. Nem, sima random generalt binarist olvastam be vele. koszi amugy :)

"Ha nem, akkor talan probald meg a gmp_scanf fuggvenyt - igaz az nem binary adatot olvas."

Na pont ez a gondom, hogy nyers binarist kellene neki beolvasni, elvegezni egy szamitast, majd ujbol tovabbengedni a folyamban. Megnezem a gmp_scanf-t.

---------------------
Ригидус а бетегадьбол

( tr3w v | 2006. 03. 22., sze – 20:23 )

Mit akarsz számolni?
Mert ha valami nagyon speciálisat (pl titkosítás, ilyesmi) akkor jobban jársz ha megírod magadnak.

"Ha jól értem, úgy keresed a prímet, hogy faktorizálod, ha sikerül akkor nem prím. Jól látom?"

Igen es tetu lassu, ahogy az ilyenkor lenni szokott; :-)

"Azért erre vannak szofisztikáltabb (és legfőképp gyorsabb) eljárások."

Nem tudom pontosan, hogy mire gondolsz; Amirol en tudok az az Eratosthenes-szita, a fenti, vagy eloszurve a mersenne fele 2^n-1, de sajnos egyik sem az igazi. Az eratosthenes-szita nagyon gyors, de mindig 2-tol kell kezdeni, ez pedig baj. Teljesen random kezdoertekek erkeznek be es a legkozelebbi primmel kellene visszaternie, ill. sokkal fontosabb az, hogy hanyadik primet kaptam vissza a sorozatbol 2-vel kezdodoen. Termeszetesen ebbol kifolyolag a mersenne-fele algoritmus sem johet szoba;

"Le is írom"

Azt megkoszonnem. :-)

"ha megnyugtatsz, hogy nem beszélünk el megint egymás mellett. ;)"

lol

oke, megigerem ;-)
---------------------
Ригидус а бетегадьбол

Na először is prímellenőrzés:
Megnézzük, hogy kis számokkal osztható-e. Kb 13-ig minden számra ismert valami összefüggés, olyasmi, mint tizes számrendszerben ha a számjegyek összege osztható 3-mal akkor a szám is osztható.
Ez konkrétan igaz (ha jól számolom) 16-os számrendszerben a 3-ra és az 5-re is (9-re viszont nem).
Ezek marha gyors tesztek (gyorsabb mintha tényleg leosztanál), kiszórnak egy csomó számot.

Ezután jönnek a valószínüségi tesztek, mint pl a Fermat teszt:
1 < a < m, ekkor ha
a^(m-1) mod m <> 1, akkor m összetett.
Ez azért jó, mert minden prímre az eredmény 1, és bár van olyan összetett szám, amire szintén 1, de viszonylag kevés.
És ez relatív könnyen számítható (bár ez első pillantásra nem biztos, hogy látszik :) ).

Ezeknek a teszteknek az az értelme, hogy minden teszt amin átment a szám, egyre inkább növeli annak a valószínüségét, hogy prímszám, miközben sokkal gyorsabbak, mint egy teljes prímteszt.

RSA kódolásnál pl meg is elégednek ennyivel (sőt eleve nem random kulcsot, hanem konkrét alakú számokat vizsgálnak (mint a mersenne félék, de persze konkrétan nem azokat)). Mert még ha nem is prímeket generált, nagyon kicsi az esélye, hogy nem működik a titkosítás.

Ha neked biztos eredmény kell, ezekután még mindig jöhet valami teljes prímteszt, szerintem a faktorizációnál biztos van gyorsabb is.

Ilyen tesztekről olvashatsz itt http://compalg.inf.elte.hu/~ajarai/konyvek.html a "Számítógépes számelmélet" című könyvben. Nem állítom, hogy ebből meg fogod érteni, de legalább tudod, hogy mit kell keresned a neten.
Ami még kötelező az a D. E. Knut könyvének (The Art of Computer Programming) 2. része (Seminumerical algorithms). Ez megjelent már magyarul is.

"ill. sokkal fontosabb az, hogy hanyadik primet kaptam vissza a sorozatbol 2-vel kezdodoen."

Na erre nincs ötletem, bár erre a faktorizáció sem megoldás.
Erre egyébként a Nagy prímszámtétel ad egy elég jó becslést n/log n alakban. Konkrét (hatékony) algoritmusról még nem hallottam.

Szerk:
Legközelebb előbb keresek és aztán írok...
Kb. minden amiről eddig a számat téptem:
http://en.wikipedia.org/wiki/Primality_test
Kellemes olvasgatást...

Koszi szepen ez sokat fog segiteni. :)

A szamjegyek osszeget a harommal valo oszthatosagra figyelem, ill. eleve kettesevel leptetem a ciklust is, kivetel ha 5-re vegzodik. Egyenlore ezzel leptetem:

inline analyze_t inc(register analyze_t value)
{
swap_inc != swap_inc;
value += 2 + swap_inc + swap_inc;
if (!(value % 5) && (value != 5))
{
value += 2;
swap_inc = 0;
}
return value;
}

de ez rovidesen le lesz cserelve egy tombos algoritmusra ami beallitja az utolso helyierteket.

Fermat teszt az jo otlet, bele is teszem meg ma.

"Erre egyébként a Nagy prímszámtétel ad egy elég jó becslést n/log n alakban."

Ezt is kiprobalom.

"ill. sokkal fontosabb az, hogy hanyadik primet kaptam vissza a sorozatbol 2-vel kezdodoen."
Na erre nincs ötletem, bár erre a faktorizáció sem megoldás."

Igazabol a faktorizacio ad ra megoldast, ha 2-rol kezdem, vagy eltarolok kulcsertekeket, majd a kulcsertekektol elindulva megszamolom oket. (ez viszont meg igy is sokaig tart)

Lenyegeben eppen ez a legnagyobb problema a primszamokkal, hogy nem lehet ra definialni egy kepletet mint a szamtani/mertani sorozatokra, ahol n-re visszadobja Sn-t, bar ezt gondolom nem kell mondanom. :-)

---------------------
Ригидус а бетегадьбол

Most, hogy láttam az algoritmust, hagy jegyezzem meg, hogy ez teljesen használhatatlan lesz ha áttérsz a tömbökre. (Legalábbis a "if (!(value % 5) && (value != 5))" rész biztosan)
Mivel az osztás a leglassabb művelet, (főleg, ha kézzel kell megírnod 4000 bit-re) nem árt elkerülni.
Viszont a már említett 16-os számrendszer beli összeadás gyors (egypár maszkolás, eltolás, összeadás), és máris megvan a 3-mal, és 5-tel való oszthatóság.
De mint mondtam volt, úgy tudom, kb 13-ig vannak hasonló módszerek. Látatlanban azt mondom, hogy Knut könyvében biztos le vannak írva, mint ahogy az is, hogyan lehet gyorsan hatványozni "mod m" felett.
(Fermat teszt)

A nagy prímszámtétel meg teljesen használhatatlan számodra, ha pontos sorszámot akarsz, mivel csak aszimptotikus kapcsolatot bizonyít.

Hmmm nem kis fába vágtad a fejszédet, lehet mégis inkább keress egy lib-et.

Koszi szepen ismet. Amugy a fenti fuggveny _helyett_ lesz a tombos megoldas. Ket tombot kepzeltem el helyette. Az egyik paratlanul leptet es atugorja az 5-ot, majd ismetlodik: {2,4,2,2} a masik pedig harmasaval. Egymassal logikai OR kapcsolatban lesznek es ha barmelyik leptetesnel inrelevans ertekhez er, akkor ignoralja. Ez joval gyorsabb lesz mint az osztasos. amugy meg lehetne csinalni ugy is, hogy megirom neki a maszkot 2*3*5-re az harminc ertek, majd loopolom. Ami nehez lehet eloszor, hogy szinkronizalni kell a beerkezo szammal, a tobbi azutan veszett gyors lesz. Egyebkent a legjobb osztok azok maguk az elozoleg megtalalt primszamok lennenek es egyben kapnank egy eratosthenesi szitat. ;-)

"A nagy prímszámtétel meg teljesen használhatatlan számodra, ha pontos sorszámot akarsz, mivel csak aszimptotikus kapcsolatot bizonyít.

Bizony. Ez lenne a leglenyegesebb informacio. En arra gondoltam, hogy ki kellene jelolnom egy tartomanyt amin belul dolgozom, pl: 2-tol 2^256 es csinalnek nehany kulcserteket es azoktol lepegetnek minusz ill. pozitiv iranyba. Ezekrol a kulcsertekekrol tudnam azt is, hogy hanyadikak, mivel elore eltarolom. Igy amikor beerkezik a kovetkezo szam, megnezi, hogy melyik tartomanyba esik, megkeresi a legkozelebbi kisebb kulcserteket (primszamot) amirol tudja azt is, hogy hanyadik, majd beallitja a megfelelo iteraciot hozza a szamlaloban es elinditja a faktorizaciot. Ezzel sok idot meg lehetne takaritani es IMHO viszonylag keves (kb 100.000) primszam elegendo lenne kulcskent.

Amugy a gmp tud szamrendszereket valtani 2-tol 36-ig es gyanitom, hogy erre optimalizalhattak is, hogy hatvanyozasnal talan szamrendszert valthat. Egyenlore megelegszem a GMP-vel de nagyon nem epitkezek ra, ha nem muszaj, talan kesobb modositanom kell rajta.

Mas. A fermat tesztnel ami nem tiszta nekem, hogy az a erteket elvileg randomokkal kellene valtogatnom. Hany kulonbozo a ertekkel erdemes elvegezni a tesztet?

Koszi :)
---------------------
Ригидус а бетегадьбол

A Fermat-teszt helyett mindenképp a másik két teszt valamelyikét használd szerintem. (Főleg ha fontos számodra, hogy melyik (hanyadik) prímről van szó.)
Mikor elég ,,biztos'', hogy prím egy szám? Engem meggyőzne, ha 2^{-300}-nál kisebb valószínűséggel összetett egy szám. :)
Érdemes lehet megnézni, hogy milyen számrendszert használ belül a GMP és arra optimalizálni. (Úgy rémlik, hogy valamilyen (ezer és millió közti) (2-hatvány +/- 1) prím alapú. Ez persze csak régi emlékeim felidézése.)

100 000 szám azért elég ritkásan van 2^256-ig... Úgyhogy rettentő sokat kell majd számolnod annak meghatározásához, hogy megtudd melyik prímet találtad meg. (Ha jól számoltam, akkor kb. 2^253 prím van addig. Ahhoz képest jókora lyukak lesznek a számok között.)

(Az algoritmusodról nem mondanék véleményt... Most túl fáradt vagyok, de lehet, hogy holnap alaposabban elemzem.)

A 100.000-et tenyleg nem gondoltam vegig, ugyhogy igazad van. :-) IMHO a paritasbitet akar le is vehetnem a vegerol.

A gmp kepes valtani szamrendszerek kozott. 2-36

Az algoritmusom igazabol nem jelent semmit, mivel le lesz cserelve egy az egyben. Ez meg egy lepteto, egy regi algoritmusombol szarmazik, amivel tesztelni szoktam egy-egy szamot. Egy tomb lesz helyette, beleteszem az inkrementalo ertekeket a fenti algoritmus helyett.

Valaki viszont ajanlotta nekem a calc-ot itt a topic vegen neki koszonom ezuton, nagyon jo szolgalatot tesz fejlesztes kozben.

---------------------
Ригидус а бетегадьбол

meg egy kerdes:
Egyszer valakivel beszelgettem es emlitette, hogy volt egy Arkhimedesz fele koncentrikus spiral amire ha bejelolted oket egy bizonyos modszerrel akkor lehetett talalni helyenkent ismetlodo reszeket. Kesobb utananeztem: http://www.numberspiral.com
---------------------
Ригидус а бетегадьбол

Na de mi a kérdés?
Egyébként nincsenek semmiféle ismétlődő részek, csupán csak olyan képletek, melyekből előálló számok között nagyobb a prímek valószínüsége. Ezzel a spirálos felírással egy bizonyos képletű számok nagyon látványosan megjelennek.

De ma még nem ismert olyan képlet mely segítségével biztosan prímet állíthatunk elő. Sőt valószínüleg nem is lesz ilyen képlet soha...

Ha esetleg a prímek teszteléséhez kapcsolódóan szeretnétek hasonló oszthatósági teszteket, akkor íme egy tétel, amit még gimiben ,,fedeztem fel'' (őszintén szólva mindig is lusta voltam utána nézni, hogy ki volt az a ,,szemtelen'', aki megelőzött ha valaki ismeri a tétel szerzőjét, kérem írja le:) ):
Tetszőleges számrendszerben, ha az alapszám mondjuk n, akkor az n-1 tetszöleges u osztójára: Ha u osztja x számjegyeinek összegét, akkor u osztja x-et is.
Hasonlóan:
Tetszőleges számrendszerben, ha az alapszám mondjuk n, akkor az n-1 tetszöleges u osztójára: Ha u osztja x számjegyeinek alternáló előjellel vett összegét, akkor u osztja x-et is.
Mivel az n^k alapú számrendszerre viszonylag egyszerű "áttérni" n alapúról, így természetesen könnyedén kaphatóak arra is hasonló számolási szabályok.
Pl.: 256-ösben: 3-mal, 5-tel, 17-tel, 257-tel könnyű ellenőrizni az oszthatóságot. (Nem meglepő módon mind 2-hatvány +/-1.:))
Az prímteszteléssel kapcsolatban... A polinomiális algoritmust mikor legutóbb láttam, akkor még nem ajánlották prímség teszteléséhez, mivel a véletlent használó algoritmusok sokkal gyorsabbak voltak. (A Fermat-tesztet azonban - hasonlóan a wiki oldalhoz - nem ajánlom.) Köszi a linket, jó kis összefoglaló. :)

Koszi, most igy hirtelen nem emesztettem meg, de holnap megirom hozza a kepletet a leirasod alapjan.

A fermat teszttel csak szukiteni akarom a keresesi tartomanyt, hogy minnel kevesebb kompozit szamra eressze ra feleslegesen a faktorizaciot. Nem ez lesz a mervado, hanem az ellenorzes ami utana jon. Ez rengeteg idot elvesz.

Most igy hirtelen meg az jutott eszembe az alapjan amit irtal, hogy felesleges lenne nekem kettesevel leptetni, ha egyszeruen csak elforgatom kettes szamrendszerben n-et es a paritasbitet ignoralom, majd alapbol n+1 -kent kezelem mivel csak paratlan szamokkal kell foglalkozni. Kivetel 2, de ez ugy sem dominans, a vegso S sorozatban potolhato szamitas nelkul is :)

---------------------
Ригидус а бетегадьбол

Kozben van fejlemeny a dologban, ugyanis a karakteres input hatasara szokott a memoriahasznalat az egekbe es amikor utanaszamoltam, kereken olyan ertekek jottek ki amibol egyertelmuen arra lehetett kovetkeztetni, hogy karakter alapokon dolgozik. Kesobb viszont, sikerult binarist bejuttatnom mindenfele ideiglenes sufni modszerekkel, ott viszont mar kiderult, hogy korabban nem a gmp core ette a memoriat hanem a gmp azon algoritmusa ami karakteres adatokkal inputolt es csak a muvelet teljes lezarasakor szabaditotta fel az input tarteruletet.

Keresgeltem a levlistan is es talaltam egy feligmeddig hasznalhato treadet, abbol is olloztam, de nem volt az sem teljes megoldas.

Meg nem fejeztem be, de ha kesz lesz, beirom ide a megfejtest, hogy masnak ne kelljen mar vegigszivni vele. :-)
---------------------
Ригидус а бетегадьбол

( rigidus | 2006. 03. 22., sze – 21:18 )

Jut eszembe: nem tudtok veletlenul egy ilyen vagy hasonlo API-t a kernelben? Egyenlore azzal is beernem.

Koszi :)
---------------------
Ригидус а бетегадьбол

( Zahy v | 2006. 03. 22., sze – 22:40 )

Mivel a dc/bc 99 tizedesjegy pontosságig, viszont egészben tetszőlegesen nagy számokat tud kezelni, mi lenne ha abban az irányban kezdenél el keresgélni, hogy azok mit használnak. Linuxokon felteszem a GPL-es van, ha esetleg más is érdekel, esetleg nézd meg mi van pl. a Minix-ben (már ha van neki). FreeBSD alatt gnu dc/bc 1.06 -os elérhető jelenleg.

man bc


...
   LIMITS
       The  following are the limits currently in place for this bc processor.
       Some of them may have been changed by an installation.  Use the  limits
       statement to see the actual values.

...

       BC_SCALE_MAX
              The  number  of  digits  after  the  decimal point is limited to
              INT_MAX digits.  Also, the number of digits before  the  decimal
              point is limited to INT_MAX digits.

Hmm.. Nalad csak 99 az INT_MAX, vagy magadnak direkt olyat forditasz ;-)??

Zsiraf

p.s. (persze, lehet, hogy a 99 szamjegytol mar pontatlan... :-):
bc
scale = 506
4*a(1)
3.141592653589793238462643383279502884197169399375105820974944592307\
81640628620899862803482534211706798214808651328230664709384460955058\
22317253594081284811174502841027019385211055596446229489549303819644\
28810975665933446128475648233786783165271201909145648566923460348610\
45432664821339360726024914127372458700660631558817488152092096282925\
40917153643678925903600113305305488204665213841469519415116094330572\
70365759591953092186117381932611793105118548074462379962749567351885\
75272489122793818301194912983364

( rigidus | 2006. 03. 30., cs – 23:54 )

Kozbe eszembejutott, hogy en igertem korabban egy megoldast a GMP binaris feltoltesere ami aztan feledesbe merult.

Ime:

void readBinStream()
{
readIntSize = 0;
int16_t c, *ptr = malloc(readIntSize);
size_t unitSize = sizeof(*ptr);
while ((c = getchar()) != EOF)
{
++readIntSize;
ptr = realloc(ptr, readIntSize * unitSize + 1);
ptr[readIntSize] = c;
}
mpz_import (readInt, readIntSize, 1, unitSize, 0, 0, ptr);
free(ptr);
}

Termeszetesen a readInt a program kezdetekor deklaralva es inicializalva van a szokasos modon, majd meghivodik a fenti fuggveny ami felolvassa az stdin-t, vegul a readInt kiolvasasa/feldolgozasa utan kilepeskor inicializalva van.

Remelem egyszer valakinek majd segitsegere lesz. ;-)

---------------------
Ригидус а бетегадьбол