Matematický problém – Visual Basic – Fórum – Programujte.com

Ahoj
Dnes nechci radu, spíš to bude vánoční soutěžní úkol :-)
Vyzkoušejte si jak fungují reálná čísla v počítači.
Zvolíme datový typ Double.

Dim a As Double
Dim b As Double
Dim c As Double

Do proměnné a uložíme hodnotu 0,1
a = 0.1

Proměnná b bude obsahovat tento jednořádkový výpočet
b = (a * a) / a

Proměnná c bude obsahovat stejný, ale dvouřádkový výpočet
c = a * a
c = c / a

Nyní si necháme zobrazit oba výsledky
Print b, c

No sláva, objeví se   0,1 a 0,1

Ale pozor, zkusíme odečíst b od c - výsledek by měl být nula, ale ...
Print b - c

Rozdíl je -1,38777878078145E-17

Tak co, dámy a pánové, kde je problém ?

Neni zadny problem.

Windows neumi pocitat. Tohle si muzes otestovat i ve win kalkulacce, ta ti da malokdy spravny vysledek. A tusim i zavorkovani tam je rozbite.

Programovaci jazyky pouzivaji casove usporne mat. algoritmy, ktere pocitaji floaty na hodne des. mist. Pocita se s tim, ze vysledek budes zaokrouhlovat a ze nepotrebujes 100% presnost pro ty ostatni mista.
Je spoustu algoritmu, muzes treba pro deleni a nasobeni pricitat a odcitat cisla cyklem. Ale 1000 opakovani nebo jeden logaritmus je rozdil.

 

#1 Luboš
moje kapesní kalkulajda HP32S dala výsledek 0.0000000E0

Ale když chcete matematický problém, tu je:

máme 10 kombinací 4-místných binárních číslic (říká se jim "nibble"), například 1001 , což je v dekadickém pojetí číslo 9. Tak takovýchto "nibble" máme 10. Nazveme je nibble-0 až nibble-9.

Nibble-0 má nejnižší význam a nibble-9 má nejvyšší význam.  Seřadíme je vedle sebe od nibble-0 do nibble 9 a vznikne nám 40-bitové binární číslo, které reprezentuje dekadickou hodnotu 2 umocněné na 40.

K tomu máme mikropočítač, který umí 16-bitovou aritmetiku.

A co s tím máme udělat:

máme vymyslet program pro náš mikropočítač s 16-bitovou aritmetikou, který toto 40-bitové číslo přečte a převede jej na jednotlivé číslice, které seřazené vedle sebe zobrazí dekadickou hodnotu onoho 40-bitového binárního čísla.

Kdopak si troufne?   

#1 Luboš
Problém je v převodu desetinného čísla do dvojkové soustavy.

#4 Kit
pletete si pojmy.

"desetinné číslo" je například:  3.14

"dvojková soustava" je například :  100111011

Jenže naším úkolem je převést binární 40-místné číslo na dekadické číslice které vyjadřují dekadický ekvivalent onoho 40-bitového binárního čísla. A toto se musí provést pomocí 16-bitové aritmetiky v nějakém (jakémkoliv) mikropočítači.

Příklad:

binární číslo   1100111  se má převést na číslice "1", "0" a "3".

#5 remmidemmi
Kit odpovídal na původní dotaz. Tvůj úkol nikdo neřeší.

#3 remmidemmi
umíš dělit ručně na papíře? V různých soustavách to funguje stejně. Pokud procesor umí dělit jako např 8051, můžeš to dělat v 16 soustavě. Pokud umí jen sčítat a odčítat, pak ve dvojkové soustavě.

Cifry pak získávat zprava, od nejmenší "váhy". Provádim v cyklu:
1. Modulo 10, získám cifru, zapíšu ji do výstupu (nebo se má formátovat jako ASCII?), pokud mají být seřazeny zleva doprava, pokládám jednotlivé cifry do LiFo (zásobník, např. u 7-segm. displeje to není nutné, stačí vypisovat zprava doleva)
2. číslo podělíš 10, podíl si uložíš pro další iteraci cyklu

Cyklus opakuji dokud nezískám všech 13 cifer vč. neplatných nul. Cyklus lze ukončit i po vykonání bodu 2 v případě, že modulo bylo menší než 10 a podíl roven 0.

Jinak to sem asi nepatří.

hu

#5 remmidemmi
Viz IEEE 754.  Uznávám, že to není jednoduché na pochopení, ale vysvětluje to, proč číslo 0,1 má v desítkové soustavě jen jedno desetinné místo, ale ve dvojkové soustavě je to nekonečná řada, která je v jednom místě useknuta, aby se vešla do registru. Tím převodem vznikne nepřesnost, která se dá dalšími operacemi zveličit.

#7 hlucheucho
Jak prosímtě na šestnáctibitovém počítači chceš dělit čtyřicetibitové číslo? V tom je pointa toho úkolu, že je potřeba si s tím pohrát.

#9 gna
Nevidím v tom problém, bohužel ani důvod. Algoritmus dělení v takovém případě podléhá účelu.

#9 gna
Stejně jako dělíš ručně na papíře. Algoritmus je stejný, jen v závislosti na možnostech procesoru zvolíš šestnáctkovou nebo binární soustavu: 

1259 / 10 = 125
 25
  59
   9  -  toto je modulo, první cifra zprava,


125 / 10 = 12
 25
  5 - modulo, druhá cifra zprava

atd

v hex 

4 EB / A = 07D
4E
 8B
  9  -  prvni cifra zprava

atd

Ještě pozn: si to představ na 8051 (8-bitový MCU) a ve dvojkové soustavě ke všemu v assembleru. Kdysi jsem to dělal, hodně práce.

hu

Tak mne napadá, že na 16 bitovém procesoru by se to nemuselo to dělat v šestnáctkové soustavě, ale zkusit využít lépe ALU tím, že by se zvolila soustava se základem větším, tj 65536 Pak by podíl a modulo získal ve 3 krocích. Neověřoval jsem to.

hu
 

#11 hlucheucho
Já jsem asi špatně pochopil ty číslice. Pokud každé 4 bity reprezentují jednu desítkovou číslici, tak pak to takhle půjde.

#13 gna
Je to BCD a procesory mívají instrukce, které s tím umí pracovat.

#13 gna
Zadání jsem pochopil tak, že mám 40-bitové číslo převést na BCD. Ukázal jsem, jak na to v šestnáctkové soustavě, tedy to 40-bitové číslo zpracovávám po čtveřicích bitů. Podmínka je, že mikropočítač umí dělit a modulo alespoň v rozsahu 1 Byte (např 8051 na to měla instrukci DIV AB. Do A se vložil dělenec, do B dělitel po vykonání DIV AB byl v A podíl, v B modulo). Pokud procesor jen umí sčítat a odčítat, tak se to dá udělat ve dvojkové soustavě. A pokud neumí ani to, nezbývá, než mu sčítání a odčítání naprogramovat a dělení pak udělat ve dvojkové soustavě. To vše třeba na osmibitovém počítači a při tom zpracovávat třeba 64-bitové číslo.

Jinak kombinační logickou funkci pro dělení neznám a neumím odvodit. A docela by mne zajímalo jak vypadá...

hu

#15 hlucheucho
Není to složité. Jeden činitel napíšeš pod sebou tolikrát, kolik je bitů a pokaždé ho posuneš o jeden bit vpravo. Bity druhého činitele dáš svisle do sloupečku vedle toho. Sečteš pak jen řádky,  ve kterých je jednička z toho druhého činitele.

#16 Kit
činitelé? To je násobení. To je popsáno např v katalogu CMOS 4000 u násobičky, přímo je tam napsaná kombinační logická funkce.. A mne zajímá dělení. Jinými slovy, co dělá ALU 8051 při instrukci DIV AB

hu

#17 hlucheucho
Totéž, ale obráceně, místo sčítání odečítáš. Písemné dělení v desítkové soustavě určitě umíš, zkus udělat totéž ve dvojkové soustavě.

#18 Kit
Jako na papíře jenže dvojkově jsem to dělal před 17 lety na 8051. A kombinační logika to nebyla.

I po tolika letech bych chtěl vidět zápis kde Y0 ... Y8 je funkcí A0...A8, B0 .... B8 tak, jako je to v katalozích u násobičky nebo sčítačky.

hu

Edit: představ si, že máš jen AND, OR, XOR a NOT hradla

#19 hlucheucho

Nejdřív bych chtěl ukončit moji otázku. Nejvíc se mi líbyla odpověď od Kit-a.
Jenom bych chtěl jeho poslední větu: "Tím převodem vznikne nepřesnost, která se dá dalšími operacemi zveličit." doplnit. 
Nechci nikoho poučovat, ale některé věci je asi potřeba připomenout.
Výpočty s reálnými čísly provádí mat. kooprocesor. Ten kromě datových typů Single(4 bajty) a Double(8 bajtů) použivý typ Extended (10 bajtů). Kooprocesor je implicitně nastaven tak, aby výpočty prováděl v této nejvyšší přesnosti.
U jednořádkového výpočtu kooprocesor načte první dvě čísla, převede je do typu Extended, provede násobení a výsledek uloží na vrchol svého zásobníku. Načte další číslo, převede je na typ Extended a vrchol zásobníku vydělí tímto číslem. Výsledek uloží do proměnné b, což znamená že jej musí převést z typu Extended na typ Double, tedy typ s menší přesností a provede zaokrouhlení.
U dvouřádkového výpočtu se výsledek po násobení zaokrouhlí a uloží do proměnné c.
Poté jej kooprocesor znovu načte, vydělí dalším číslem, zaokrouhlí a opět uloží do proměnné c.
V druhém případě se tedy zaokrouhlení provedlo dvakrát a tak vznikl sice malý, ale přeci jen rozdíl.

A ještě k úkolu od remmidemmi.
Pro jistotu jsem nahlédl do knihy Bity do bytu. Dříve narození asi tuto knihu znají.
Pro dělení je zde užit stejný algoritmus jaký uvedl hlucheucho. Podle mně by úplně měla stačit 8-bitová aritmetika. 
Hlavní výpočet (tedy odčítání hodnoty 10) by proběhl v registru a. 

Do a by se postupně ukládali bity 39 až 0

a=0
for x=39 to 0
nejdřív bych bity v a posunul do leva : a=a+a
zapsal bych aktuální bit: a(bit 0) = bit x
otestoval bych, zda je číslo menší jak 10
pokud ano, zapsal bych do výsledku nulu a přesunul bych se na začátek cyklu.
v opačném případě bych od a odečetl 10 a do výsledku zapsal jedničku
next x

Po ukončení cyklu zůstane v a zbytek po dělení - ten se zapíše jako BCD do výsledku
Pokud je výsledek dělení menší jak 10 tak se vše ukončí
V opačném případě se do bitů 39 až 0 zapíše tento výsledek a vše se opakuje.

Na svém počítači bych těch 40 bitů převedl do typu Extended, ten bych načetl do kooprocesoru a uložil do paměti jako datový typ BCD  :-) ale toto řešení mi asi neprojde  :-)

#20 Luboš
Na svém počítači bych těch 40 bitů převedl do typu Extended, ten bych načetl do kooprocesoru a uložil do paměti jako datový typ BCD  :-) ale toto řešení mi asi neprojde  :-)

Že v zadání byl 16-bitový počítač, tak asi koprocesor nemá. Takže odhaduješ správně, že neprojde.

Jinak jsem to zkusil po Bytech, "dílčí" dělenec by měl max 12 bitů, pro zpracování na 16-bitovém počítači bez potíží.

Další krok k efektivitě by bylo v okamžiku, kdy se dělením číslo "smrskne" na 16 bitů, dělit přímo na ALU.

Oba případy předpokládají, že procesor má instrukci pro dělení a modulo pro operandy 16 bitů.

hu

#3 remmidemmi

Pro jistotu jsem si svoje řešení vyzkoušel. Kdysi dávno jsem si složitější algoritmy otestoval nejdřív ve VB6 a pak je následně přepsal do assembleru.
Takže takto vypadá kód ve VB6.

Option Explicit

Private Sub Command1_Click()
Dim a As Byte
Dim x As Long
Dim z As Long
Dim c As Long
Dim i As Byte
Dim BCD(10) As Byte

z = 2147483647  ' toto číslo převedeme do BCD (max. kladné číslo typu Long)

Print "vstupní číslo = "; z

Do
    a = 0
    c = 0
    For x = 30 To 0 Step -1
        a = a + a
        c = c + c
        If (z And (2 ^ x)) > 0 Then 'test x-tého bitu
            a = a + 1
        End If
        If a > 9 Then
            c = c + 1
            a = a - 10
        End If
    Next x
    BCD(i) = a
    i = i + 1
    z = c
Loop While c > 9

If c > 0 Then   ' nulu na začátku není potřeba zapsat
    BCD(i) = c
Else
    i = i - 1
End If

Print "vysledek = ";

For c = i To 0 Step -1
    Print BCD(c);
Next c
Print

End Sub

V assembleru bych neměl problém celý kód přepsat tak, aby všechny proměnné byly typu byte, tedy v podstatě si vystačím s 8-bitovou aritmetikou

Pro remmidemmi: jak jsi to vyřešil ty ?