Lab1a

Bitar och bytes

I denna laboration kommer du att träna på olika talsystem och teckenuppsättningar som används i datorsammanhang. Du kommer också att träna på begrepp som Gbyte, Gflop och GHz.

När jag letade efter något dator-relaterat på www, snubblade jag över en bild av en kille som tatuerat följande mönster (mellan armhåla och midja, minst 0.5 m hög tatuering med andra ord). Jag undrade vad det hela betydde och kom efter lite arbete (mesta tiden gick åt till att skriva av ettor och nollor från bilden) fram till en mening (jag kan dock inte förklara varför man väljer att smycka sig med något sådant :-). Det blir en bra övning i alla fall.

Finn en mening med följande:

01010000
01100101
01100001
01100011
01100101
01100110
01110101
01101100
01000110
01110010
01110101
01110011
01110100
01110010
01100001
01110100
01101001
01101111
01101110

Jag har en gammal version av Encyclopædia Britannica. Enligt Britannicas hemsida består dagens version av "32 volumes" ... "packed with 44 million words covering the breadth of human knowledge." Gör en uppskattning av hur många bytes som krävs för att lagra textdelen, av de 32 volymerna, elektroniskt. Du kan alltså bortse från bilder och illustrationer. Antag också att vi inte använder någon textkomprimeringsteknik utan att vi lagrar texten på det uppenbara sättet. Hur många CD-skivor (du behöver inte läsa hela sidan, utan leta efter ordet capacity i texten) krävs för att lagra texten? Hur många DVD-skivor? Tala också om vilka antaganden du gör.

Mer om textkomprimering. Det finns flera web-ställen där man kan hitta sk e-books (en digitalt lagrad bok). De ställen jag tänker på lagrar endast äldre böcker, som inte längre är skyddade av copyright (detaljer för sverige). Det är alltså helt lagligt att hämta och lagra dessa böcker.

En bra start är Gutenberg-projektets hemsida. Där står:

There are over 20,000 free books in the Project Gutenberg Online Book Catalog.
A grand total of over 100,000 titles is available at Project Gutenberg Partners, Affiliates and Resources.

Bland "Partners, Affiliates and Resources" hittar man den svenska motsvarigheten: Runeberg-projektet.

Hämta en intressant e-book, packa (eventuellt) upp den, och räkna antalet tecken, ord och rader (ledning wc). Testa också kommandot ls -l, (l som i long) kommentar?

Skriven text innehåller en hel del redundans och kan därför komprimeras.

Använd kommandona zip, gzip respektive bzip2 för att se hur mycket texten kan komprimeras. Vilket kommando lyckas bäst på din text? Hur packar man upp tro?

Att lösa ett linjärt ekvationssystem, A x = b, där A är en n x n-matris kräver ungefär n^3 / 3 additioner och lika många multiplikationer. Primärminnet brukar vara flaskhalsen när det gäller att lösa stora matrisproblem (se min HPC-kurs för massor med detaljer), men låt oss anta att vi använder en optimerad algoritm där tiden för flyttalsoperationerna dominerar.

Antag att vi har oändligt mycket primärminne på en studentdator vid MV (en AMD64-dator). Hur stort problem (hur stort n) skulle vi kunna lösa på en sekund, en timme, ett dygn? Ledning cat /proc/cpuinfo

Vad är svaren om vi tar hänsyn till att vi har begränsat minne på datorn?
Ledning: head -1 /proc/meminfo
(head tar ut början av en fil, head -1 tar ut första raden. Finns givetvis tail också.)
Allt detta minne kan inte utnyttjas för matrisdata (unix, fönstersystem etc. lägger ju också beslag på minne). Men för att förenkla problemställningen kan du anta att allt minne kan användas för lagring av data. När man löser A x = b används samma minne, A, för matriserna som uppstår under lösningens gång. Man bildar inga nya matriser, med andra ord.
För den som känner till virtuellt minne (simulering av större minne med hjälp av disk): vi vill inte använda virtuellt minne i detta fall (det tar alldeles för mycket tid).

När elementära funktioner, som sin och exp, beräknas i en dator kan man inte lagra en tabell som innehåller ett tabellvärde för varje flyttal (i stället används approximation med polynom eller rationella funktioner, kombinerat med andra steg). I följande uppgift kommer du att se varför tabellmetoden inte fungerar.

Du har en reellvärd funktion som är definierad för alla tänkbara 64-bitars flyttal. Antag också att du inte kan utnyttja periodicitet eller andra egenskaper hos funktionen. Ungefär hur många byte skulle krävas för att lagra en tabell med alla (approximationer av) funktionsvärdena? Hur många stora hårddiskar, om vardera 1Ti-byte, krävs?

Det är ett problem att skapa mycket snabba datorer som har stor fysisk utbredning (i superdatorer tänker man på detta och skapar kompakta konstruktioner).

Hur långt (i meter) hinner en elektrisk signal under en clockcykel på våra datorer?
Ledning: Det elektriska fältet utbreder sig med ljusets fart.

Det är inte ovanligt med språkförbistring när man hanterar text på datorer. Säg att vi vill sortera följande rader i (svensk) bokstavsordning:

Johansson
Östergren
Ågren
Bengtsson
Ädelgran
Andersson

Skapa en fil (läs detta om du använder gedit), namn, som innehåller namnen i ovanstående ordning (klipp och klistra) och använd unix-kommandot sort, skriv alltså:

sort namn

Blir det rätt? Om inte, försök att förklara varför (du behöver dock inte i detalj förklara varför man får just detta resultat). Det är inte sort-kommandot det är fel på.

Eftersom detta är en praktisk och viktig fråga (i bland) så kommer här en längre utläggning.
För att sort skall fungera korrekt måste man tala om vilket språk (inte programspråk utan engelska, svenska etc) man vill arbeta med. Så här fungerar det i korta drag. I ett terminalfönster går det ett underordnat program, ett skal (eng. shell), som läser dina kommandon och ser till att dessa utförs. En del kommandon är inbyggda i skalet som t.ex. cd-kommandot (change directory). Kommandot which talar om var man hittar kommandot (så här kan det se ut med skalet tcsh):

% which cd
cd: shell built-in command.

ls-kommandot, däremot, utgörs av ett kompilerat C-program, och när man skriver ls i ett terminalfönster (för att lista namnen på sina filer) kör skalet i gång kommandot.

% which ls
/bin/ls
% file /bin/ls vilken typ av fil är det?
/bin/ls: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV),
for GNU/Linux 2.2.5, dynamically linked (uses shared libs), stripped

Det finns många olika skal, här är några:

Namn på skalet	Kommandonamn
Bourne shell	sh
C shell (vitsigt)	csh
TC-Shell, T-shell	tcsh
bash, Bourne again shell, (ännu vitsigare)	bash
Korn shell	ksh

På vårt system kör man normalt bash ellet tcsh (som jag själv använder). Om man bara gör enkla saker i skalet ser man inte så stora skillnader mellan de olika varianterna. Om man programmerar (man kan loopa över filer etc.) kan det vara rätt stora variationer. För att ta reda på vilket skal du använder, kan du t.ex. ge kommandosekvensen:

ps -p $$ | tail -1

och läsa ordet längst till höger på raden (det kan också gå bra med echo $shell eller echo $SHELL). Det kan se ut så här:

% ps -p $$ | tail -1
28894 pts/7 00:00:00 tcsh

Nåväl, åter till sort. Skalet håller sig med en del variabler (finns olika kategorier också), en av dessa lagrar t.ex. utseendet på prompten (den strängs som skrivs ut när skalet är redo att läsa ett nytt kommando). Andra variabler håller reda på vilken språk (eng. locale) man vill ha. Vissa kommandon, som t.ex. sort, tittar på locale och anpassar sorteringen efter valt språk. Så här får man gör för att det skall fungera på svenska:

I tcsh:
% setenv LC_ALL swedish
% sort namn

I bash:
% export LC_ALL=swedish
% sort namn

Observera att detta endast fungerar i det aktuella skalet där man har satt LC_ALL-variabeln. Det går att förändra sin omgivning, via initeringsfiler för skalet, så att man rätt språk oavsett vilket fönster man kör i. Jag går dock inte in på detta.
Om du vill kan du testa danish (eller dansk) i stället för swedish. locale -a ger en lista på alla alternativ.

För att se aktuellt värde på variabeln kan man skriva ut den med echo-kommandot (ungefär print). $LC_ALL är variabelns värde ($ är en evalueringsoperator).

% echo $LC_ALL
swedish