Algoritmy pro zpracovani velkých čísel – Matematika – Fórum – Programujte.com

Ahoj,

neznate nahodou někdo nějakou pěknou stránku, kde by byli popsány algoritmy pro práci s velmi velkými přirozenými čísly (rozuměj "ty které se nevejdou do žádného datového typu").

Jedná se mi hlavně o násobení, dělení, sčítání.

Děkuji moc :) 

#1 JK
Takovou stránku neznám, zřejmě proto, že tyto algoritmy se probírají na prvním stupni základní školy a nikdo nepředpokládá, že člověl, který se učí programovat, by neuměl sčítat, odčítat a násobit...

Je sice fakt, že na ZŠ se počítá s malými čísly, ale algoritmus je pořád stejný ať má číslo 3 cifry, nebo 300.

#1 JK
tak velká čísla by se dala zpracovávat jako součet mnohočlenů x=x1+x2+...+xn a pak jsou ty operace jednoduché

x1 atd. bych zvolil jako 1.) násobek 10 (co největší) nebo 2.) maximální hodnotu největšího datového typu (v mém případě 9223372036854775807 pro integer a 1,7*10^308 v real)

#2 JoDiK
tady jde o taková čísla, která se nedají uložit, protože by přetekla paměť

#3 Kalgys
tak ještě jiná úvaha; kvůli násobení bych použil ještě menší "úseky" tj. menší než Sqrt výše uvedeného maxima

#4 Kalgys
Do počítače lze přece uložit cokoliv, když má číslo 2000 cifer tak si ho buď uložíš jako posloupnost cifer=znaků desítkové soustavy což je jednoduché, nebo si uděláš svoje rutiny na uložení a zpracování třeba 100 bitových čísel...

V počítači dnes už přece nejsi omezen téměř ničím, jen sám sebou...

Já zažil doby, kdy počítače měly 64Kb operační paměti a jako úložiště byly kazety nebo RAM disk 2MB.

Vlezl se tam operační systém, programy, data i hry.

#6 JoDiK
No já nejsem žádný expert, spíše jenom nadšenec, ale co vím je to, že číselné typy v prakticky všech programovacích jazycích mají svou maximální velikost, ale máš pravdu dá se to obejít, ať už jen blbým jednorozměrným polem ve kterém si vytvoříš "svoji" číselnou soustavu (třeba milionovou :D ) nebo uložením čísla jako řetězce znaků (operace by se prováděli trochu jinak, ale ve své podstatě je tak my jako lidé vnímáme (sčítání "pod sebe" atd.).

PS: já si pamatuju maximálně takové ty obrovské diskety, které se vkládali do hlavního počítače v učebně a na všech jemu podřízených počítačích běželo to samé :D, to jsem byl v 2. třídě

#7 Kalgys
No a přesně takhle to musíš "obejít"

Procesory jsou zatím jen 64-bitové, větší přirozená čísla přímo násobit neumí (pokud vím) a pro běžné programy a výpočty ani nemusí.

kdysi jsem dostal svoji první programovatelnou kalkulačku. Byla to HP-33C (mám jí dosud). Ta kalkulačka má jen několik málo kroků, prakticky žádnou paměť. Ale napsal jsem si různé programy, například program, který dělí dvě čísla na nekonečně mnoho desetinných míst. Prostě tak dlouho dokud zbytek je roven nule, anebo dokud mi baví zapisovat ta desetinná čísla. Takže ono to napsat jde. Jsou to skutečně algoritmy z druhé třídy obecní školy.

Tak možná bych si dovolil (i když nejsem autorem) toto vlákno označit za vyřešené

dovolim si nesuhlasit scitovanie a odcitovanie su algorimy zo zakladnej skoly. ale skuste vynasobit dve stomegove cisla a skuste to spravit v case do jednej hodiny :) to uz nieje matematika druhej triedy. Pouzivaju sa dost advanced algoritmy Karatsuba, Toom Cook alebo Schönhage–Strassen.

Je o tom napisanych vela peknych kniziek napriklad Donald Knuth - The Art of Computer Programming (kapitola 4.3.3 :))

#11 nergal
Ano, to už je ale vyšší dívčí a tazatel se tu už neukázal, tak nevíme na jaké úrovni to mělo být řešeno...

#12 JoDiK
Tazatel sledujo pozorne diskusi :D

Na jediny problem na ktery jsem narazil jsou zlomky s nekonecnym deetinym rozvojem. Podarilo se mi ale odvodit vztah, podle ktereho muzu najit periodu takovehoto cisla

10^m = 1 + CelaDolniCast(10^m/B)*B

Kde B je prvocislo ci jeho nasobek. Napred si zvolim m = 1, pak m = 2 a jeddu tak dlouho, dokud se leva strana nerovna strane prave

#11 nergal
Dekuji za odkaz na velmi peknou knizku.

#13 JK
Tvůj vztah je sice pěkný, (dal by se napsat i jednodušeji 10^m=1 (mod B)), ovšem:

1. před periodu musíš ještě napsat tolik nul, kolik je "délka" B (tedy např. pro B=47 jednu 0)

2. co je ovšem podstatnější je to, že i pro malá prvočísla ti výpočet dle tvého vztahu bude dělat obrovský problém

3. až takto najdeš periodu převráceného čísla k relativně malému prrvočíslu 983, tak dej vědět.

4. to už můžeš rovnou dělit postupně 1 tím prvočíslem a sledovat, kdy se perioda začne opakovat (stačí aby se opakovala 2x)

#14 JK
V mém předchozím příspěvku má být místo ..."délka" B.. správně ..."délka" B zmenšená o 1..

#11 nergal
Dovolim si nesuhlasit s dovolenim si nesuhlasit, ale iba pre Karatsubu, podla mna tento algoritmus je schopny pochopit zakladoskolak, ktory vie roznasobit (a+b)(c+d), lebo na tom je zalozeny. 

#17 sleepy

Kazdy algoritmus je lahky ked ho pochopis ;) ostatne algoritmy co som spominal su zalozene na tom istom v podstate ;)

Asi jsme vyseděli každý trochu jinou ZŠ a násobení rozhodně není triviální úloha.
Základní postup je sice principiálně stejný jako ve škole, avšak formalismus postupu je (nej?)názorněji popsán zde:
http://marusic.blog.sme.sk/…kulacka.html
Pro čísla po n platných číslicích potřebuje n exp 2 operecí násobení a (n exp 2)-2 operací sčítání.
Součin bude mít nejvýše 2n číslic. Např. (99 999).(99 999)=(9 999 800 001).
Odčítat lze sčítáním konst. doplňků 8-6=[8+(10-6)]mod10 =(8+4)mod10=12mod10=2,
pro odečet větší číslice od menší s výpůjčkou od vyššího řádu menšence, např pro číslice 6-8:
16-8=10+6-8=10+(6-8)=10-(8-6)=10-[8+(10-6)]mod10=10-(8+4)mod10=10-12mod10=10-2=8
Dělí se postupným odčítáním, rac. mocnění lze nahradit opakovaným násobením, druhá odm. např.
http://mfweb.wz.cz/…matika/2.htm
vyšší obecné rac. odmocniny zpr. iterácí.