TASK.txt

****************
* 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]

== 7. Průběžné výsledky ==

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.