Algoritmy pro zpracovani velkých čísel – Matematika – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
JK
~ Anonymní uživatel
20 příspěvků
15. 11. 2012   #1
-
0
-

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 :) 

Nahlásit jako SPAM
IP: 89.102.173.–
Reklama
Reklama
JoDiK
~ Anonymní uživatel
981 příspěvků
16. 11. 2012   #2
-
0
-

#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.

Nahlásit jako SPAM
IP: 88.103.233.–
Kalgys0
Návštěvník
16. 11. 2012   #3
-
0
-

#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)

Nahlásit jako SPAM
IP: 62.84.150.–
Kalgys0
Návštěvník
16. 11. 2012   #4
-
0
-

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

Nahlásit jako SPAM
IP: 62.84.150.–
Kalgys0
Návštěvník
16. 11. 2012   #5
-
0
-

#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

Nahlásit jako SPAM
IP: 62.84.150.–
JoDiK
~ Anonymní uživatel
981 příspěvků
16. 11. 2012   #6
-
0
-

#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.

Nahlásit jako SPAM
IP: 195.113.183.–
Kalgys0
Návštěvník
17. 11. 2012   #7
-
0
-

#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ě

Nahlásit jako SPAM
IP: 62.84.150.–
JoDiK
~ Anonymní uživatel
981 příspěvků
17. 11. 2012   #8
-
0
-

#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í.

Nahlásit jako SPAM
IP: 88.103.233.–
remmidemmi0
Super člen
17. 11. 2012   #9
-
0
-

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.

Nahlásit jako SPAM
IP: 194.228.20.–
Kalgys0
Návštěvník
18. 11. 2012   #10
-
0
-

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

Nahlásit jako SPAM
IP: 62.84.150.–
nergal+1
Návštěvník
19. 11. 2012   #11
-
0
-

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 :))

Nahlásit jako SPAM
IP: 85.135.170.–
viem že neviem čo viem
JoDiK
~ Anonymní uživatel
981 příspěvků
19. 11. 2012   #12
-
0
-

#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...

Nahlásit jako SPAM
IP: 88.103.233.–
JK
~ Anonymní uživatel
20 příspěvků
21. 11. 2012   #13
-
0
-

#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

Nahlásit jako SPAM
IP: 78.128.194.–
JK
~ Anonymní uživatel
20 příspěvků
21. 11. 2012   #14
-
0
-

#11 nergal
Dekuji za odkaz na velmi peknou knizku.

Nahlásit jako SPAM
IP: 78.128.194.–
Honzc0
Stálý člen
22. 11. 2012   #15
-
0
-

#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)

Nahlásit jako SPAM
IP: 93.181.78.–
Honzc0
Stálý člen
22. 11. 2012   #16
-
0
-

#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..

Nahlásit jako SPAM
IP: 93.181.78.–
sleepy0
Stálý člen
27. 11. 2012   #17
-
0
-

#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. 

Nahlásit jako SPAM
IP: 158.195.195.–
nergal+1
Návštěvník
30. 11. 2012   #18
-
0
-

#17 sleepy

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

Nahlásit jako SPAM
IP: 85.135.134.–
viem že neviem čo viem
vbvbvb
~ Anonymní uživatel
1 příspěvek
10. 1. 2014   #19
-
0
-

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í. 

Nahlásit jako SPAM
IP: 94.113.68.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 5 hostů

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý