PŘEVOD ČÍSLA

1. Zadání

Vytvořte program, který načte číslo ze standardního vstupu v soustavě se základem Z1 a převede jej do soustavy se základem Z2.

2. Technická specifikace

Vytvořte platformě nezávislou aplikaci, která načte vstupní výraz ve formátu [XXX]Z1=Z2, Kde XXX je libovolná (libovolné dlouhá, i několik gigabajtů) posloupnost znaků 0-9 případně A-Z přípustných pro číselnou soustavu se základem Z1. Z2 je soustava, do níž má být načtené číslo převedeno a vypsáno na standardní výstup. Základy soustav Z1 a Z2 mohou byt od 2 až po 36 (znak reprezentující hodnotu 35 bude Z)

Příklad vstupního souboru:

[1012222121310101]4 = 32

Takové číslo uvedené mezi [] reprezentuje hodnotu ve čtyřkové soustavě (soustavě se základem 4) a má se převést do soustavy se základem 32.

Program si nemůže vytvářet žádný dočasný soubor a nemůže se v souboru pohybovat jinak než sekvenčním načtením tohoto souboru pomocí funkce read.

Program musí být vytvořen v jazyce ANSI C (ne C++). Ze systémových volání nebo knihovních funkcí může používat pouze funkce read, write, malloc, free. Žádné jiné funkce nejsou povolené (žádné fread, fwrite, getchar, realloc ...).

3. Vstup

Vstupem je soubor s výrazem [číslo] z1 = z2, který bude přesměrován na standardní vstup.

4. Výstup

Výstupem je číslo v soustavě se základem z2 ve formátu [číslo] z2.

5. Hodnocení

Hodnotit se bude funkčnost, efektivnost (rychlost běhu i paměťové nároky), přehlednost kódu a dokumentace.

6. Referenční implementace

Pro ty, co si myslí, že úloha je snadná, přikládáme testovací soubory i s časem, který dosáhla referenční implementace vytvořená společností ESET. Zájemce, kteří realizují převod pomocí nejznámějšího způsobu, postupným dělením převáděného čísla základem soustavy do níž se číslo převádí, bychom chtěli upozornit, že tento algoritmus má složitost n^2. Což znamená, že již převod čísla s počtem číslic 100.000 (sto tisíc) bude pro ně výkonově velmi náročný. Referenční implementace dosáhla při převodu tohoto čísla čas 0,026 s. Což je 26 tisícin sekundy.

Referenční implementace využívala jen jedno jádro procesoru. Vzhledem k povolenému API ani není možne využít paralelizace. Tato referenční implementace nebude figurovat ve výsledném žebříčku. Uvítáme i řešitele, jejichž řešení dokáže v rozumném čase (do hodiny) převést číslo s 100.000 číslicemi. Zájemce o tablet však bude muset poslat řešení, které dokáže převést i číslo s jednou miliardou číslic.

Parametry testovacího prostředí:

• CPU: Intel Core i5 2,67 GHz
• RAM: 4GB
• OS: Linux x86_64

Tabulka s časy, kterých dosáhla referenční implementace s:

file	time
10.000 digits (4.29KB)	0,005s	Result (4.22KB)
100.000 digits (42.1KB)	0,026s	Result (41.47KB)
1.000.000 digits (420KB)	0,274s	Result (414KB)
10.000.000 digits (4.1MB)	4,526s	Result (4.04MB)
100.000.000 digits (41.0MB)	73,527s	Result (40.44MB)
1.000.000.000 digits (410MB)	1078,013s	Result (405MB)

 

PS: Referenční implementaci lze překonat i při použití známých algoritmů, nechali jsme vám rezervu;).

Nápověda:
google: modern computer Arithmetic
Kapitola o převodu mezi soustavami není ta nejpodstatnější v případě, že chcete být nejrychlejší.

Vaše postřehy /analýzy/ řešení zasílejte na následující adresu: numbertransfer@eset.sk

Výsledky

Vítěz: Matej Fajnor

Pro určení pořadí v tabulce se nepoužívají zveřejněné soubory ale jiné. Provádí se ze soustavy, jejímž základem je prvočíslo a převod je také do soustavy, jejímž základem je prvočíslo. Z toho důvodu uvádíme i rychlost referenční implementace. Referenční implementace ale nezasahuje do výsledného pořadí. Do tabulky nebyly zařazeny řešení, které nedodržují specifikaci (používají i jiné systémové volání/ knihovní funkce než povolené read, write, malloc a free, využívají knihovny třetích stran, připadne, nerespektují formát vstupu a výstupu.

Jméno	Verze	1.000	10.000	100.000	1.000.000	10.000.000	100.000.000	1.000.000.000
Referenční implementace	1	0.004	0.026	0.033	0.262	3.741	62.686	898.383
Matej Fajnor	1	0.002	0.024	0.118	1.425	17.795	246.963	5374.21
Jan Katrenic	5	0.005	0.031	0.242	3.104	37.631	598.068	13222.586
Timotej Stanek	2	0.023	0.051	0.721	7.694	94.078	1031.204	SF
Jan Katrenic	3	0.006	0.047	0.341	4.229	61.803	1160.743
Jan Kacer	2	0.002	0.015	0.216	5.147	156.589	3611.415
Jan Sugarek	5	0.004	0.036	0.247	5.288	150.808	4361.096
Jan Sugarek	4	0.004	0.019	0.0291	8.636	317.908	11874.927
Martin Durkac	5	0.052	0.062	0.32	11.044	936.653
Marian Repasan	3	0.004	0.024	0.628	34.704	1675.387
Viliam Simovic	2	0.012	0.166	4.967	127.028	4256.086
Dusan Durech	2	0.003	0.034	1.361	133.687	13300.918
Lukas Slebodnik	1	0.023	0.052	1.77	174.333
Peter Ertl	2	0.003	0.047	3.409	338.441
Martin Durkac	3	0.012	0.218	18.784	1883.973
Martin Durkac	4	0.042	0.067	0.49	SF
Ondra Gersl	1	0.014	0.549	53.754	5352.113
Peter Laszlo	1	0.015	0.67	65.693	6637.302
Zsitva Tibor	1	0.026	1.267	126.419
Juraj Kavka	1	0.033	2.423	242.694
Jaroslav Tobik	1	0.046	3.64	745.527
Lukas Bejda	1	3.713	>1800
Martin Durkac	1	>600
Martin Durkac	2	>600

 

Druhá tabulka obsahuje řešení, jejichž časy byly změřeny, avšak vyžadovaly úpravu ze strany ESET-u z důvodů uvedených v posledním sloupci. Řešení jsou seřazeny sestupně podle jména řešitele.

Jméno	Verze	1.000	10.000	100.000	1.000.000	10.000.000	100.000.000	1.000.000.000	Problém
Cseke Gabriel	1	0.014	0.144	13.02	SF				Špatný parsing + segmentation fault
Jan Niznansky	1	0.04	1.804	180.314	SF				Špatný parsing + segmentation fault
Lukas Bejda	2	0.188	16.901						Špatný parsing
Lukas Judicak	2	0.013	0.422	40.567					Špatný parsing
Martin Ludvik	2	0.004	ZV						Špatný parsing + segmentation fault
Martin Tkacik	1	0.037	1.061	105.039					Špatný parsing
Michal Puheim	1	0.033	1.231	122.056					Nepovolené funkce
Michal Repisky	1	0.012	0.497	36.808					Špatný parsing
Milos Stofa	1	0.021	0.021	0.155	1.69	22.268	ZV		Poslední výsledek je chybný
Milos Stofa	2	0, 003	0.031	0.146	1.694	23.016	471.164	Not tested	Chyba pri malých císlech - segmentation fault
Peter Fabian	1	0.012	0.353	29.763					Chyba pri malých císlech - segmentation fault
Peter Zarnay	1								Nesplnena specifikace, nepovolené funkce, nacítání není rešeno pres standardní vstup, napevno zadaná délka vstupního retezce
Pool	1	0.017	0.031	0.487	5.536	61.052	1218.761		Chyba pri malých císlech - segmentation fault
Samuel Brezani	2	0.004	0.023	0.936	88.592				Špatný parsing
Tomáš Kuzma	1	0.007	0.058	2.332	223.178				Špatný parsing