abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
eParkomat, startup z ČR, postoupil mezi finalisty evropského akcelerátoru ChallengeUp!
Robot na pivo mu otevřel dveře k opravdovému byznysu
Internet věcí: Propojený svět? Už se to blíží...
dnes 13:42 | Pozvánky

V Praze probíhá konference Internet a Technologie 16.2, volné pokračování jarní konference sdružení CZ.NIC. Konferenci lze sledovat online na YouTube. K dispozici je také archiv předchozích konferencí.

Ladislav Hagara | Komentářů: 0
včera 22:44 | Komunita

Joinup informuje, že Mnichov používá open source groupware Kolab. V srpnu byl dokončen dvouletý přechod na toto řešení. V provozu je asi 60 000 poštovních schránek. Nejenom Kolabu se věnoval Georg Greve ve své přednášce Open Source: the future for the European institutions (SlideShare) na konferenci DIGITEC 2016, jež proběhla v úterý 29. listopadu v Bruselu. Videozáznam přednášek z hlavního sálu je ke zhlédnutí na Livestreamu.

Ladislav Hagara | Komentářů: 6
včera 15:30 | Zajímavý projekt

Společnost Jolla oznámila v příspěvku Case study: Sailfish Watch na svém blogu, že naportovala Sailfish OS na chytré hodinky. Využila a inspirovala se otevřeným operačním systémem pro chytré hodinky AsteroidOS. Použita je knihovna libhybris. Ukázka ovládání hodinek na YouTube.

Ladislav Hagara | Komentářů: 7
včera 14:15 | Nová verze

Byla vydána verze 7.1.0 skriptovacího jazyka PHP používaného zejména k vývoji dynamických webových stránek. Jedná se o první stabilní verzi nejnovější větvě 7.1. Přehled novinek v dokumentaci. Podrobnosti v ChangeLogu. K dispozici je také příručka pro přechod z PHP 7.0.x na PHP 7.1.x.

Ladislav Hagara | Komentářů: 1
včera 12:55 | Nová verze

Google Chrome 55 byl prohlášen za stabilní. Nejnovější stabilní verze 55.0.2883.75 tohoto webového prohlížeče přináší řadu oprav a vylepšení (YouTube). Opraveno bylo také 36 bezpečnostních chyb. Mariusz Mlynski si například vydělal 22 500 dolarů za 3 nahlášené chyby (Universal XSS in Blink).

Ladislav Hagara | Komentářů: 4
včera 11:55 | Pozvánky

Máte rádi svobodný software a hardware nebo se o nich chcete něco dozvědět? Přijďte na 135. sraz spolku OpenAlt, který se bude konat ve čtvrtek 8. prosince od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Sraz bude tentokrát tématický. Bude retro! K vidění budou přístroje jako Psion 5mx nebo Palm Z22. Ze svobodného hardwaru pak Openmoko nebo čtečka WikiReader. Přijďte se i vy pochlubit svými legendami, nebo alespoň na pivo. Moderní hardware má vstup samozřejmě také povolen.

xkucf03 | Komentářů: 0
včera 00:10 | Nová verze

Byla vydána verze 3.2 svobodného systému pro detekci a prevenci průniků a monitorování bezpečnosti počítačových sítí Suricata. Z novinek lze zmínit například podporu protokolů DNP3 a CIP/ENIP, vylepšenou podporu TLS a samozřejmě také aktualizovanou dokumentaci.

Ladislav Hagara | Komentářů: 0
1.12. 21:00 | Nová verze

Byla vydána beta verze Linux Mintu 18.1 s kódovým jménem Serena. Na blogu Linux Mintu jsou hned dvě oznámení. První o vydání Linux Mintu s prostředím MATE a druhé o vydání Linux Mintu s prostředím Cinnamon. Stejným způsobem jsou rozděleny také poznámky k vydání (MATE, Cinnamon) a přehled novinek s náhledy (MATE, Cinnamon). Linux Mint 18.1 bude podporován až do roku 2021.

Ladislav Hagara | Komentářů: 0
1.12. 16:42 | Nová verze

Byl vydán Devuan Jessie 1.0 Beta 2. Jedná se o druhou beta verzi forku Debianu bez systemd představeného v listopadu 2014 (zprávička). První beta verze byla vydána v dubnu letošního roku (zprávička). Jedna z posledních přednášek věnovaných Devuanu proběhla v listopadu na konferenci FSCONS 2016 (YouTube, pdf).

Ladislav Hagara | Komentářů: 0
1.12. 15:16 | Komunita

Na GOG.com začal zimní výprodej. Řada zlevněných her běží oficiálně také na Linuxu. Hru Neverwinter Nights Diamond lze dva dny získat zdarma. Hra dle stránek GOG.com na Linuxu neběží. Pomocí návodu ji lze ale rozběhnout také na Linuxu [Gaming On Linux].

Ladislav Hagara | Komentářů: 1
Kolik máte dat ve svém domovském adresáři na svém primárním osobním počítači?
 (32%)
 (24%)
 (29%)
 (7%)
 (5%)
 (3%)
Celkem 763 hlasů
 Komentářů: 50, poslední 29.11. 15:50
Rozcestník
Reklama

Dotaz: Faktorizace 196b cisel v C/C++

25.3.2012 10:35 Martin Sury
Faktorizace 196b cisel v C/C++
Přečteno: 1337×
Dobry den, v ramci sveho programu bych potreboval provadet faktorizaci 196b cisel vzniklych vynasobenim dvou prvocisel. Exisuje pro tento ucel nejaka knihovna v C/C++? Nasel jsem neco napriklad tady:

http://www.frenchfries.net/paul/factoring/source.html

http://www.codeproject.com/Articles/310513/Application-of-Goldbach-Conjecture

Ale nic co jsem zkousel takova cisla nezvladalo, potrebuji aby ten algoritmus byl rozumne rychly, abych na vysledek nemusel cekat hodinu. Predem dekuji za rady.

Odpovědi

stativ avatar 25.3.2012 10:45 stativ | skóre: 54 | blog: SlaNé roury
Rozbalit Rozbalit vše Re: Faktorizace 196b cisel v C/C++
Ale nic co jsem zkousel takova cisla nezvladalo, potrebuji aby ten algoritmus byl rozumne rychly, abych na vysledek nemusel cekat hodinu.
Hodinu? Řekl bych, že kdybys zvládl faktorizaci za hodinu, byl bys king.
Ať sežeru elfa i s chlupama!!! ljirkovsky.wordpress.com stativ.tk
25.3.2012 10:56 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Faktorizace 196b cisel v C/C++
No, aspoň že nechce rovnou 2048 bitů. :-)
stativ avatar 25.3.2012 11:25 stativ | skóre: 54 | blog: SlaNé roury
Rozbalit Rozbalit vše Re: Faktorizace 196b cisel v C/C++
No, pokud uvažuji GNFS, nejrychlejší mě známý algoritmus, i tak mi vychází sakra dlouhý čas (prosím o kontrolu):

196b číslo má asi 59 míst. Složitost GNFS je exp(((64/9)*n)^(1/3) * (log(n)^2/3)), kde n je počet desetinných míst. Pokud budu počítat, že čas operace je 2.5E-10 s (střeleno od boku), tak mi to dává 72 490 hodin.
Ať sežeru elfa i s chlupama!!! ljirkovsky.wordpress.com stativ.tk
pavlix avatar 25.3.2012 16:52 pavlix | skóre: 53 | blog: pavlix
Rozbalit Rozbalit vše Re: Faktorizace 196b cisel v C/C++
Ono se to počítá s desítkovým logaritmem, že hraje roli počet desetinných míst?
GentooFedoraSCRAM – Jsem open source vývojář, nikoli markeťák ⇒ názory zde uvedené jsou jen mé vlastní.
stativ avatar 25.3.2012 19:19 stativ | skóre: 54 | blog: SlaNé roury
Rozbalit Rozbalit vše Re: Faktorizace 196b cisel v C/C++
Neříkal jsem, že vím jak ten algoritmus funguje, ale jen, že o něm vím (=> vím, že existuje). Složitost jsem si našel tady. Jinak samotný algoritmus je popsaný třeba tady.
Ať sežeru elfa i s chlupama!!! ljirkovsky.wordpress.com stativ.tk
stativ avatar 25.3.2012 19:22 stativ | skóre: 54 | blog: SlaNé roury
Rozbalit Rozbalit vše Re: Faktorizace 196b cisel v C/C++
Každopádně předchozí výpočet je samozřejmě hrubý odhad, složitost bude jiná (protože n se neblíží nekonečnu), nebude to jedna instrukce, a i čas běhu instrukce bude jiný. Pro představu, že to poběží dlouho (pokud jsem se někde při opisu složitosti nesekl) to IMHO stačí.
Ať sežeru elfa i s chlupama!!! ljirkovsky.wordpress.com stativ.tk
pavlix avatar 25.3.2012 19:29 pavlix | skóre: 53 | blog: pavlix
Rozbalit Rozbalit vše Re: Faktorizace 196b cisel v C/C++
Já si říkal, že tam ten přepočet na desítkový řád nemá co dělat. Krásná ukázka umění věci zkomplikovat.
GentooFedoraSCRAM – Jsem open source vývojář, nikoli markeťák ⇒ názory zde uvedené jsou jen mé vlastní.
stativ avatar 25.3.2012 19:29 stativ | skóre: 54 | blog: SlaNé roury
Rozbalit Rozbalit vše Re: Faktorizace 196b cisel v C/C++
Proč to dělat jednoduše, když to jde složitě…
Ať sežeru elfa i s chlupama!!! ljirkovsky.wordpress.com stativ.tk
25.3.2012 20:39 lertimir | skóre: 58 | blog: Par_slov
Rozbalit Rozbalit vše Re: Faktorizace 196b cisel v C/C++
Myslím, že ten vzorec je chybně. Správný vzorec výpočetní složitosti je \exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\log n)^{\frac{1}{3}}(\log \log n)^{\frac{2}{3}}\right) =L_n\left[\frac{1}{3},\sqrt[3]{\frac{64}{9}}\right] (v TeXovém zápisu) nebo převedeno jako obrázek a jinak zdroj je WolframMathWorld Je tam trochu více logaritmů.
25.3.2012 20:53 lertimir | skóre: 58 | blog: Par_slov
Rozbalit Rozbalit vše Re: Faktorizace 196b cisel v C/C++
Tedy jsem slepý, nebo spíše čtu hlavně vzorce, texty okolo už méně. V obvykle uváděném vzorci je n přímo číslo, které je třeba faktorizovat. U vzorce stativa je n počet desetinných cifer tohoto čísla, což udělá první logaritmování.

Mea culpa.
25.3.2012 21:02 rastos | skóre: 60 | blog: rastos
Rozbalit Rozbalit vše Re: Faktorizace 196b cisel v C/C++
Trocha googlenia mi prinieslo odkaz na diskusiu v ktorej sa hovorí
256 bits is a little over 80 digits. Msieve can do factorizations that size in about 20-25 minutes
A čo je msieve? Projekt na sourceforge
Msieve is a C library implementing a suite of algorithms to factor large integers. It contains an implementation of the SIQS and GNFS algorithms
5.4.2012 13:04 Martin Sury
Rozbalit Rozbalit vše Re: Faktorizace 196b cisel v C/C++
Dekuji, msieve vypada dobre, na onech strankach je ke stazeni demo, ktere opravdu zvlada faktorizaci 196b cisel behem okamziku. Ja bych tuto funcionalitu potreboval vyuzit v ramci sveho programu, avsak nikde tam nevidim moznost stahnout si tu knihovnu, pouze ukazkovou aplikaci a jeji zdrojaky. Jsem jenom slepy, nebo tam tu knihovnu opravdu nemaji i kdyz tam maji vyslovne napsane "Msieve is a C library ..."?

5.4.2012 14:08 chochi | skóre: 29 | Praha
Rozbalit Rozbalit vše Re: Faktorizace 196b cisel v C/C++
Soucasti zdrojaku (dokonce hlavni hlavni soucast) je i knihovna

make x86_64
⋮
ar r libmsieve.a common/filter/clique.o common/filter/filter.o common/filter/merge.o common/filter/merge_post.o common/filter/merge_pre.o common/filter/merge_util.o common/filter/singleton.o common/lanczos/lanczos.o common/lanczos/lanczos_io.o common/lanczos/lanczos_matmul0.o common/lanczos/lanczos_matmul1.o common/lanczos/lanczos_matmul2.o common/lanczos/lanczos_pre.o common/lanczos/lanczos_vv.o common/lanczos/matmul_util.o common/smallfact/gmp_ecm.o common/smallfact/smallfact.o common/smallfact/squfof.o common/smallfact/tinyqs.o common/batch_factor.o common/cuda_xface.o common/dickman.o common/driver.o common/expr_eval.o common/hashtable.o common/integrate.o common/minimize.o common/minimize_global.o common/mp.o common/polyroot.o common/prime_delta.o common/prime_sieve.o common/savefile.o common/strtoll.o common/util.o mpqs/gf2.qo mpqs/mpqs.qo mpqs/poly.qo mpqs/relation.qo mpqs/sieve.qo mpqs/sqrt.qo \
        mpqs/sieve_core_generic_32k.qo mpqs/sieve_core_generic_64k.qo mpqs/sieve_core_p4_64_64k.qo mpqs/sieve_core_core_64_32k.qo mpqs/sieve_core_k8_64_64k.qo \
        gnfs/poly/poly.no gnfs/poly/poly_skew.no gnfs/poly/polyutil.no gnfs/poly/root_score.no gnfs/poly/size_score.no gnfs/poly/stage1/stage1.no gnfs/poly/stage1/stage1_roots.no gnfs/poly/stage2/optimize.no gnfs/poly/stage2/optimize_deg6.no gnfs/poly/stage2/root_sieve.no gnfs/poly/stage2/root_sieve_deg45_x.no gnfs/poly/stage2/root_sieve_deg5_xy.no gnfs/poly/stage2/root_sieve_deg6_x.no gnfs/poly/stage2/root_sieve_deg6_xy.no gnfs/poly/stage2/root_sieve_deg6_xyz.no gnfs/poly/stage2/root_sieve_line.no gnfs/poly/stage2/root_sieve_util.no gnfs/poly/stage2/stage2.no gnfs/filter/duplicate.no gnfs/filter/filter.no gnfs/filter/singleton.no gnfs/sieve/sieve_line.no gnfs/sieve/sieve_util.no gnfs/sqrt/sqrt.no gnfs/sqrt/sqrt_a.no gnfs/fb.no gnfs/ffpoly.no gnfs/gf2.no gnfs/gnfs.no gnfs/relation.no gnfs/poly/stage1/stage1_sieve_cpu.no gnfs/poly/stage1/stage1_sieve_cpu.no
ranlib libmsieve.a
⋮
Takze po buildu z toho vyleze staticka knihonva libmsieve.a, kterou staci prilinkovat (se spravne nastavenymi cestami k hlavickovym souborum). Viz napriklad build toho dema:

gcc -D_FILE_OFFSET_BITS=64 -O3 -fomit-frame-pointer -march=k8 -DNDEBUG -D_LARGEFILE64_SOURCE  -Wall -W -DMSIEVE_SVN_VERSION="\"exported\"" -I. -Iinclude -Ignfs -Ignfs/poly -Ignfs/poly/stage1 demo.c -o msieve  \
        libmsieve.a -lz -lgmp -lm -lpthread
5.4.2012 14:51 Martin Sury
Rozbalit Rozbalit vše Re: Faktorizace 196b cisel v C/C++
Aha, toho jsem si nevsiml, dekuju. Nepritomnost knihovny jsem usuzoval i z toho, ze jsem k ni mezi readme soubory ani na webu nenasel zadnou dokumentaci. Doufam, ze me i v tomto vyvedete z omylu a nejaka dokumentace existuje:)
5.4.2012 15:31 chochi | skóre: 29 | Praha
Rozbalit Rozbalit vše Re: Faktorizace 196b cisel v C/C++
Nejlepsi dokumentace jsou zdrojove kody :-)
Ted vazne - v Readme:

Using Msieve
------------

Just to be confusing, there are two things that I call 'Msieve' interchangeably.
The source distribution builds a self-contained static library 'libmsieve.a',
that actually performs factorizations, and also builds a 'msieve' demo
application that uses the library. The library has a very lightweight inter-
face defined in msieve.h, and can be used in other applications. While the
demo application is (slightly) multithreaded, most the library is single-
threaded and all of its state is passed in. The linear algebra code used
in the quadratic- and number field sieve is multithread aware, and the
entire library is supposed to be multithread-safe.
Takze bych to videl, ze je asi nejlepsi se podivat na demo.c a inspirovat se (se 600 radky kodu by to nemusel byt problem).
25.3.2012 10:51 Filip Jirsák | skóre: 66 | blog: Fa & Bi
Rozbalit Rozbalit vše Re: Faktorizace 196b cisel v C/C++
1, 2, 3 To je zase nějaký domácí úkol? Nechcete to raději řešit v jedné diskusi místo ve třech?
26.3.2012 17:57 Franta Gajdůšek | skóre: 15 | blog: co_me_prave_napadne
Rozbalit Rozbalit vše Re: Faktorizace 196b cisel v C/C++
Ano, je, ale myslim ze ty zbyle vlakna s nim nesouvisi. Mozna jedno(1), ale to druhe pochybuju (knihovna ktere se dotycny chce vyhnout je podle zadani explicitne povolena).

Založit nové vláknoNahoru

Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

ISSN 1214-1267   www.czech-server.cz
© 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.