Převod římských čísel na arabská a naopak - tuning

Nejspíš by bylo korektní, aby tento text začal obvyklým sypáním si popela na hlavu. Vyjádřen by tím byl nejen opakující se pocit lítosti nad odklonem od ústředního tématu - RPN, ale také sebekritické přiznání neschopnosti zapudit potřebu převádět arabská čísla na římská a zpět použitím kalkulátoru HP-50g. Ne, nic takového, žádná sebereflexe! Kdo ví, jestli by to někdo nepokládal za slabost... Pojďme se raději věnovat všemi oblíbenému konverznímu tématu.


Námět

↑  ↓

Při pohledu na jednotlivá předchozí řešení je nápadný kvalitativní rozdíl zejména mezi variantou UserRPL a provedením v assembleru pro procesor Saturn. Aby ne! Bez nadsázky - střetávají se zde dva zcela odlišné světy. Nemá smyslu zabývat se srovnáváním pracností vytváření programu assembler vs. UserRPL. Zajímavější bude věnovat se otázce, zda by program v UserRPL nemohl obsahovat některé finesy použité ve výrazně výkonnější verzi psané v jazyku symbolických adres. Odpověď lze intuitivně vytušit: jasně, že by mohl.

A→R

Snadnost přístupu k jednotlivým cifrám zadání v případě převodu A→R je v assembleru tak nestoudně okatá, že nějaké dělení s odřezáváním desetinné části mu za žádných okolností nemůže konkurovat. Rozhodně důvod k důkladnému přepracování.

R→A

Převod opačným směrem je také vhodné zrevidovat. Pro ilustraci bude užitečné oživit si obsah modulu v jazyku C roman.c. Na první pohled je vidět, že funkce r2a() obsahuje ve formě lokální proměnné tabulku svalt[] s hodnotami odpovídajícími jednotlivým římským cifrám. Také je zde volána funkce r2a_prevlessnum() pro zjištění počtu předchozích číslic s menší hodnotou. Rozhodně ne na první pohled, ale po důkladném zkoumání modulu roman.a, je vidět, že zde není ekvivalent ani tabulky ani pomocné funkce (absence vysvětlena v modulu r2a2.c, ale o tom až později). Je to zjednodušení, které rozhodně stojí za zvážení.


Řešení

↑  ↓

A→R

Úprava vedoucí ke snazšímu přístupu k cifrám zadání je velmi jednoduchá. Číslo je převedeno na textový řetězec sekvencí R→I →STR. Ten je dále "obráběn" příkazy HEAD a TAIL. Výsledný kód se tím zkrátí, zjednoduší a zpřehlední - no, učiněná nádhera. Ale co to? Doba provádění programu po těchto úpravách povážlivě vzrůstá! Takže zpátky na stromy - dělení s odřezáváním desetinné části je dost dobré. K tomu všemu přistupuje logaritmus a exponenciální funkce (viz LOG a ALOG), ale pořád to běží rychleji, než původní verze. Mein Gott, das ist unglaublich!

Je to trochu divné, ale pro kalkulátor je evidentně snazší jakýkoliv výpočet s operandy typu 0, tedy Real number. Ani operand typu 28, což je Real integer, není žádnou výhrou. I jeho použitím se běh programu citelně zpomalí. A ostatní typy (List, String, ...) znamenají ještě větší spotřebu výpočetního výkonu. Daleko větší úlevu přineslo odstranění lokálních proměnných → divisor sidx result a také provádění všech operací pouze s položkami RPL stacku.

R→A

Převod R→A je složitější, řešení bez použití lokálních proměnných z praktických důvodů nepřipadá v úvahu. Hlavní změnou je přiblížení se k postupu, který je obsažen v modulu r2a2.c. Podle jeho vzoru se nové řešení obejde bez dvou lokálních proměnných: tabulku hodnot římských cifer a výsledek rozdělený podle desítkových řádů do seznamu, tedy → svalt result. Také následující lokální proměnná → cval s aktuální položkou z tabulky hodnot chybí. To sice vypadá skvěle, ale jak říká úvodní věta, bez lokálních proměnných to nejde. Jejich jména → ←pidx addt subt →ord (poslední v pořadí odpovídá makru THIS_ORD) včetně označení hodnot RPL stacku v komentářích zdrojového textu odpovídají symbolům použitým v r2a2.c.

Počet lokálních proměnných je sice vyšší než u původní verze, ale i tak to stálo za to. Dvě nová pole addt[] resp. subt[] spolu s hodnotou less umožní dokonalejší kontrolu správnosti zadání. Ale co hlavně: i tenhle druh převodu běží rychleji, než původní verze. Wunderschön!

Pozn.: Provedená repase vyřešila i jednu zanedbanou chybu v původní verzi: vstupní hodnota typu Real number je v ní vyhodnocena jako chybné zadání. Scheiße, das ist schrecklich!

Rychlost běhu programu

Pro změření rychlosti postačí krátká sekvence 'ROMAN' 3888 OVER TEVAL UNROT SWAP TEVAL NIP. V tabulce jsou naměřené výsledky:

Převod Doba [s] pro řešení Úspora [%]
původní nové
A→R 0.3492 0.2863 18
R→A 1.6614 0.9603 42

Výsledek je to moc pěkný i přesto, že nový kód je o 106 bajtů delší. Pro HP-50g to je zcela zanedbatelné množství paměti a ani poměrný nárůst zvíci necelých deseti procent není nijak hrozný.


Zdrojový text

↑  ↓
ROMAN
«
  IF { 0. 28. } OVER TYPE POS	@	pos	value
  THEN				@ je to cislo
    DUP I→R IP DUP			@	ipval	ipval	value
    1. < SWAP 3999. > OR	@	0./.1	value
    SWAP 0. ROT			@	0./.1	type	value
  ELSE
    DUP TYPE			@	type	value
    CASE
      DUP 2. ==			@ je to retezec
      THEN
      END
      DUP 6. ==			@ je to algebraicky vyraz
      THEN			@ bude preveden na retezec
        SWAP →STR DUP SIZE 1. - 2. SWAP SUB SWAP
      END
      DROP			@	value
      →STR "Bad Argument: " SWAP + DOERR
    END
    OVER SIZE DUP		@	size	size	type	value
    1. < SWAP 15. > OR		@	0./.1	type	value
  END
  IF
  THEN
    DROP			@	value
    "Bad Range: " SWAP →STR + DOERR
  END
  "IVXLCDM"			@	sromt	type	value
  → sromt
  «
    IF				@	type	value
    THEN			@	value
      0.			@	less	value
      sromt SIZE		@	pidx	less	value
      {0. 0. 0. 0.} DUP		@	subt	addt	pidx	less	value
      « ←pidx 1. - 2. / IP 1. + »
      → ←pidx addt subt →ord
      «
        DO			@	less	value
          OVER HEAD sromt SWAP	@	digit	sromt	less	value
          POS			@	aidx	less	value
          IF DUP NOT
          THEN			@	aidx	less	value
            DROP2 "Unknown Digit: " SWAP + DOERR
          END
          SWAP OVER ←pidx	@	pidx	aidx	less	aidx	value
          IF <
          THEN			@ if(aidx < pid)
            DROP 0.		@   less = 0;
          ELSE			@ else
            1. +		@   ++less;
          END
          CASE			@	less	aidx	value
            DUP 3. >
            THEN
              DROP2		@	value
            END
            OVER ←pidx ≤
            THEN
            END			@	less	aidx	value
            DUP 1. ≤
            THEN
              'addt'		@	'addt'	less	aidx	value
              →ord EVAL 	@	_ORD()	'addt'	less	aidx	value
              DUP2		@	_ORD()	'addt'	_ORD()	'addt'	less	aidx	value
              GET		@	addt[]	_ORD()	'addt'	less	aidx	value
              OVER		@	_ORD()	addt[]	_ORD()	'addt'	less	aidx	value
              'subt' SWAP ROT 	@	addt[]	_ORD()	'subt'	_ORD()	'addt'	less	aidx	value
              PUT		@	_ORD()	'addt'	less	aidx	value
              0.		@	0.	_ORD()	'addt'	less	aidx	value
              PUT		@	less	aidx	value
            END
            DROP2		@	value
          END
          IF DUP TYPE		@ typ neni Real ale String
          THEN
            "Unexpected Digit: " SWAP + DOERR
          END
          SWAP '←pidx'		@	'pidx'	aidx	less	value
          STO			@ pidx = aidx;
          'addt' →ord EVAL	@	_ORD()	'addt'	less	value
          DUP2			@	_ORD()	'addt'	_ORD()	'addt'	less	value
          GET			@	addt[]	_ORD()	'addt'	less	value
 ←pidx 1. - 2. / FP 8. * 1. +	@	_INC()	addt[]	_ORD()	'addt'	less	value
          +			@	addt[]	_ORD()	'addt'	less	value
          DUP 4. ROLLD		@	addt[]	_ORD()	'addt'	addt[]	less	value
          PUT			@	addt[]	less	value
          IF 9. >
          THEN
            DROP
            "Too much Digits: " SWAP + DOERR
          END
        UNTIL
          SWAP TAIL SWAP	@	less	value
          OVER SIZE		@	size	less	value
          NOT
        END
        DROP2 addt subt		@	subt	addt
      »
      -				@	{ }
      1.			@	1.	{ }
      « NSUB 1. - ALOG * »	@	« »	1.	{ }
      DOSUBS			@	{ }
      ∑LIST R→I		@	result
    ELSE
      I→R IP			@	value
      ""			@	result	value
      DO
        SWAP DUP LOG IP		@ order: dekadicky rad aktualni cifry
        DUP			@	order	order	value	result
        ALOG			@ divisor: delitel pro ziskani nejvyssi cifry
        ROT			@	value	divisor	order	result
        DUP PICK3		@	divisor	value	value	divisor	order	result
        / IP			@ digit: aktualni cifra
        ROT			@	divisor	digit	value	order	result
        OVER *			@ aktualni cifra na puvodnim radu
        NEG			@	-d000	digit	value	order	result
        ROT			@	value	-d000	digit	order	result
        +			@	value	digit	order	result
        4. ROLLD SWAP		@	order	digit	result	value
        2. * 1. +		@ sidx:  index do sromt
        { 4. 9. }		@	{4 9}	sidx	digit	result	value
        PICK3			@	digit	{4 9}	sidx	digit	result	value
        IF POS			@	0./1.	sidx	digit	result	value
        THEN			@ je to 4 nebo 9
          sromt			@	sromt	sidx	digit	result	value
          OVER DUP		@	sidx	sidx	sromt	sidx	digit	result	value
          SUB			@	sromt[]	sidx	digit	result	value
          UNROT 1. +		@	sidx	digit	sromt[]	result	value
          SWAP			@	digit	sidx	sromt[]	result	value
          9. ==			@	0./1.	sidx	sromt[]	result	value
          +			@	sidx	sromt[]	result	value
          UNROT			@	sromt[]	result	sidx	value
          +			@	result	sidx	value
          sromt			@	sromt	result	sidx	value
          ROT DUP		@	sidx	sidx	sromt	result	value
          SUB			@	sromt[]	result	value
          +			@	result	value
        ELSE			@ neco jineho nez 4 nebo 9
          UNROT			@	digit	result	sidx	value
          WHILE DUP
          REPEAT
            PICK3		@	idx	digit	result	sidx	value
            IF OVER 5. ≥
            THEN
              1. + SWAP		@	digit	idx+1	result	sidx	value
              4. - SWAP		@	idx+1	digit-4	result	sidx	value
            END
            sromt OVER ROT	@	idx	idx	sromt	digit	result	sidx	value
            SUB			@	sromt[]	digit	result	sidx	value
            ROT SWAP		@	sromt[]	result	digit	sidx	value
            + SWAP 1. -		@	digit-1	result	sidx	value
          END
          ROT			@	sidx	digit-1	result	value
          DROP2			@	result	value
        END
      UNTIL
        OVER NOT		@	0./1.	result	value
      END
      NIP			@	result
    END
  »
»
TROMAN
«
  IF DEPTH NOT
  THEN 1. 3999.
  END { } UNROT
  FOR y y DUP ROMAN ROMAN
    IF DUP ROT ≠
    THEN y SWAP R→C +
    ELSE DROP
    END
  NEXT ZVONEK
»
ZVONEK
« 0. 19. .05 → period
  «
    START 1046.5 period BEEP 1318.51 period BEEP
    NEXT
  »
»

Zjevně došlo k formální chybě: kapitola má nadpis "Zdrojový text" a ono jich je tam víc! Bystřejší z nás snadno určí, že počet zdrojových textů je zcela přesně roven číslu tři. Ano, došlo k pochybení, leč vylhat se z něj bude jistě efektnější, něž se k němu chlapsky přiznat. Nuže, provozní program je jenom jeden („...to je přece každýmu jasný, nééé?“) a jmenuje se ROMAN. Další je zkušební modul TROMAN pro ověření funkčnosti pro celý rozsah vstupních hodnot. Poslední v pořadí se jmenuje ZVONEK a slouží výhradně ku zvonění :-)


Download

↑  ↓

Textový tvar Binární forma
ROMAN ROMAN.hp