Popis řešení hlavolamu z č. 32

Jako obvykle šlo o to udělat program, který by počítal co nejrychleji.

Protože výsledek obsahuje mnoho cifer, bylo nutné jej "uskladnit" do řetězce a napsat rutinu, která by co nejefektivněji násobila třeba stociferné číslo.

Nejefektivnější bude zřejmě způsob, kdy toho co nejvíce vynásobí přímo BASIC tak, aby násobil zároveň co nejméněkrát.

Za tímto účelem jsem použil něco jako "desetitisícovkovou" číselnou soustavu. Jde vlastně o to, že jsem bral čtyřciferné číslo jako jedinou "číslici". Tato soustava je jakýmsi vyšším systémem pro běžnou desítkovou soustavu, stejně jako soustava šestnáctková (hexadecimální) pro soustavu dvojkovou (binární).

Pokud násobím dvě čtyřciferná čísla, výsledek je vždy maximálně osmiciferný (dvojciferný v 10000-soustavě). Tento výsledek se ještě do BCD kódu vejde celý. Takže kýžený postup je takový, že běžně násobím 1*2*3*4... dokud je výsledek ještě čtyřciferný. Potom jej vynásobím s třeba 40-ticiferným řetězcem jako bych násobil 10-ticiferné číslo jednociferným. V tomto případě vystačím s deseti násobeními a devíti připočteními přenosů oproti jinak potřebným 4*40 nasobením + 4*39 přenosy a následným sečtením čtyř více než 40-ticiferných mezivýsledků. Navíc celou násobící rutinu volám méně často!

Pokud nebyl výklad příliš jasný snad pomůže popis programu:

10-80 Hlavička

90 Dimenzace řetězce pro výsledek a pomocného řetězce

100-110 Nastavení řetězce na "000...001" a nastavení pomocných proměnných

130-180 Zadání čísla N(1-100)190 Vynulování TIME$ a začátek hlavního cyklu

200-240 Postupné násobení čísel I. Výsledek se ukládá do M. Pokud je M>10000, vezme se předchozí hodnota v Q a pustí se násobící rutina. Pokud je I=N (poslední číslo), pustí se násobící rutina naposledy s ním

250-390 Násobící rutina

250 Do W je pomocí logaritmu uložen počet cifer výsledku. Spustí se cyklus J popisující odzadu po 4 aktuální pozici v řetězci výsledku až kam je třeba vzhledem k jeho délce.

260 Do POM$ je uložena vyříznutá část mezivýsledku vynásobená číslem Q plus ještě přenos (v prvním kroku nulový, viz dále) z předchozího kroku.

290 Pokud je výsledek právě čtyřciferný, je nalepen do VYSL$

310-320 Je-li kratší, je předtím zepředu doplněn nulami.

340 A přenos P je nastaven na 0

360-370 Je-li POM$ naopak delší, uloží se jeho dolní 4 cifry a horní 1 až 4 cifry slouží jako přenos pro násobení další čtveřice.

390 Konec cyklu J. Teď budeme násobit další (vyšší) čtyřcifernou část mezivýsledku.

400 Konec cyklu I. Předchozí číslo Q je již vynásobeno s řetězcem VYSL$, postupujeme tedy dále, dokud I=N.

420-490 Výpis konečného výsledku (bez nevýznamných nul na začátku.

500 Výpis potřebného času.

Násobící rutinu by šlo asi ještě více optimalizovat. Zrychlení by ale nebylo příliš výrazné a bylo by to na úkor její srozumitelnosti, která je už i tak asi malá. Snad se Vám bude někdy hodit, až budete potřebovat vynásobit např. dva velmi dlouhé řetězce...

Jan Walla