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