home *** CD-ROM | disk | FTP | other *** search
/ Chip 1997 October / Chip_1997-10_cd.bin / ctenari / cisloe / popis.txt < prev    next >
Text File  |  1997-09-02  |  5KB  |  101 lines
  1.  
  2.      P²i matematick∞ch v∞poƒtech se obƒas vyskytne pot²eba
  3. provést v∞poƒet s velkou p²esností na velk∞ poƒet míst, a£ jiº
  4. desetinn∞ch nebo celkov╪ platn∞ch. Ve v╪tτin╪ p²ípadà se vystaƒí
  5. s typy prom╪nn∞ch, které b╪ºn╪ nabízejí programovací jazyky.
  6. N╪kdy se vτak màºe stát, ºe ani kapacita t╪chto prom╪nn∞ch
  7. nestaƒí. Pak je t²eba bu╘ sáhnout po speciálních programov∞ch
  8. prost²edcích, a pokud nejsou zrovna po ruce (resp. jsou p²íliτ
  9. drahé), pokusit se vypomoci vlastními silami.
  10.  
  11.      Zpàsobà jak to uƒinit je samoz²ejm╪ nep²ebern╪ mnoho
  12. a záleºí na mnoha faktorech jak∞ postup zvolit. Namátkou màºeme
  13. vyjmenovat: pot²ebná rychlost v∞poƒtu, poºadovaná p²esnost,
  14. pouºit∞ programovací jazyk, programátorské schopnosti
  15. a matematické schopnosti programátora a.t.d. Velmi ƒasto pak lze
  16. p²i ²eτení konkrétní úlohy vyuºít i ràzn∞ch heuristik,
  17. urychlujících ƒasto mnohonásobn╪ v∞poƒty.
  18.  
  19.      Jedním z moºn∞ch zpàsobà v∞poƒtu na velk∞ poƒet míst je
  20. simulace "ruƒního" poƒítání (násobení, d╪lení a.t.d.). Pouºití
  21. kalkulaƒky je dnes pro v╪tτinu lidí samoz²ejmostí i p²i
  22. nejb╪ºn╪jτích banálních v∞poƒtech. V╪²ím tomu, ºe bych ²adu lidí
  23. vyvedl alespoσ na chvilku z míry, kdybych po nich cht╪l, aby
  24. vyd╪lili na papí²e τestimístné ƒíslo t²ímístn∞m na ƒty²i
  25. desetinná místa.
  26.  
  27.      P²edstavme si, ºe jsme v situaci, kdy pot²ebujeme provád╪t
  28. v∞poƒty t²eba na 1000 platn∞ch míst. V praxi je pot²eba takto
  29. p²esn∞ch v∞poƒtà samoz²ejm╪ minimální, nicmén╪ màºe se vyskytnout
  30. a£ jiº jako skuteƒn╪ praktická pot²eba nebo jako p²edm╪t v∞zkumu.
  31.  
  32.      Ukaºme si p²íklad podobného v∞poƒtu, kde pouºijeme simulaci
  33. "ruƒního" d╪lení a sƒítání k v∞poƒtu ƒísla "e" (Eulerova
  34. konstanta, která je základem p²irozen∞ch logaritmà. Jedná se
  35. o transcendentní ƒíslo, ƒili ƒíslo s nekoneƒn∞m desetinn∞m
  36. rozvojem, jehoº p²ibliºná hodnota je 2,71828182459...). V praxi
  37. se k jeho v∞poƒtu màºe pouºít nekoneƒná ²ada:
  38.  
  39.         ∩
  40.   ex =  ¬ (Xk/k!)
  41.        k=0
  42.  
  43. Zdánliv╪ sloºit∞ tvar màºeme rozepsat trochu pochopiteln╪ji:
  44.  
  45.        X0   X1   X2   X3   X4
  46.   ex = ─- + ── + ── + ── + ──  ...
  47.        0!   1!   2!   3!   4!
  48.  
  49. Budeme-li poƒítat hodnotu e, bude mít ²ada tvar
  50.  
  51.        1    1    1    1    1
  52.   e  = ─- + ── + ── + ── + ──  ...
  53.        0!   1!   2!   3!   4!
  54.  
  55.      Pro v∞poƒet si definujeme dv╪ pole (nap². typu Byte)
  56. o rozsahu, podle poƒtu míst, na která chceme ƒíslo e urƒit. Kaºd∞
  57. prvek pole bude pro nás reprezentovat jednu cifru Do prvního
  58. z nich - oznaƒme jej A - uloºíme hodnotu 1.0000... , ƒili do
  59. prvního prvku dáme 1 a do dalτích uloºíme nuly. Toto pole bude
  60. pro nás reprezentovat p²i v∞poƒtu aktuální hodnotu prvku ²ady. Do
  61. druhého pole - oznaƒíme jej B - vloºíme hodnotu 2.0000... . Toto
  62. pole pro nás bude reprezentovat souƒet spoƒten∞ch ƒlenà ²ady.
  63. Pokud budeme poƒítat na v╪tτí poƒet míst, narazili bychom jeτt╪
  64. na dalτí problém. Hodnoty n! rostou velmi rychle. K v∞poƒtu
  65. nap²íklad jen na 1000 míst je pot²eba spoƒítat p²es 200 ƒlenà
  66. ²ady. Pokud bychom poƒítali skuteƒn╪ kaºd∞ ƒlen samostatn╪,
  67. museli bychom vypoƒítávat p²ísluτn∞ faktoriál a d╪lit jím
  68. jedniƒku.
  69.  
  70.    Tento postup je vτak moºno podstatn╪ zjednoduτit. Staƒí si
  71. uv╪domit, ºe v poli A máme uloºenou zpoƒátku hodnotu 1. Pro
  72. v∞poƒet t²etího ƒlenu (první dva samoz²ejm╪ není t²eba poƒítat)
  73. staƒí vyd╪lit hodnotu v tomto poli ƒíslem 2. Hodnotu tohoto pole
  74. p²iƒteme k poli B. Pro získání hodnoty ƒtvrtého ƒlenu staƒí kdyº
  75. hodnotu v poli A vyd╪líme ƒíslem 3. Op╪t p²iƒteme hodnotu v poli
  76. A do pole B a pokraƒujeme d╪lením pole A ƒíslem 4 atd. Tím jsme
  77. uτet²eni poƒítání vysok∞ch faktoriálà a problémà s d╪litelem
  78. velk∞ch rozm╪rà. V∞poƒet màºeme skonƒit v okamºiku, kdy obsah
  79. pole A je cel∞ nulov∞.
  80.  
  81.    Vlastní d╪lení ƒísla v poli A (viz p²iloºen∞ program) vychází
  82. z klasického schéma, které se pouºívá p²i d╪lení na papíru tak,
  83. jak jsme se uƒili ve τkole.
  84.  
  85.    Co se t∞ká chyby ve v∞sledku, dá se její hranice urƒit z poƒtu
  86. poƒítan∞ch ƒlenà ²ady. V∞poƒet kaºdého ƒlenu ²ady je p²esn∞,
  87. s v∞jimkou hodnoty posledního místa. Horní hranice chyby je tedy
  88. omezena ƒíslem 9*n, kde n je poƒet poƒítan∞ch ƒlenà ²ady. Chyba
  89. tedy màºe b∞t maximáln╪ na posledních log10(9*n)ti místech.
  90.  
  91.    P²iloºen∞ program slouºí jako ilustrativní p²íklad. Jist╪
  92. sami najdete ²adu moºností jak program vylepτit a urychlit.
  93. Nap²íklad bajt màºe obsahovat ne jednu, ale dv╪ cifry. Pak màºe
  94. b∞t v n-místném poli bajtà màºe b∞t uloºen dvojnásobn∞ poƒet
  95. pozic poƒítaného ƒísla a v∞poƒet prob╪hne za stejnou dobu,
  96. zajímavé màºe b∞t dopln╪ní tisku o pràb╪ºném stavu v∞poƒtu,
  97. o ƒasov∞ch relacích v závislosti na poƒtu poƒítan∞ch míst,
  98. a.t.d.).
  99.  
  100. Ji²í Ventluka
  101.