Citace notace - Quote notation - Wikipedia
Citace notace je reprezentací racionální čísla na základě Kurt Hensel je p-adic čísla. V notaci uvozovek mají aritmetické operace obzvláště jednoduché a konzistentní formy, které poskytují přesné odpovědi bez č chyba zaokrouhlení. Aritmetické algoritmy notace nabídky fungují ve směru zprava doleva; Algoritmy sčítání, odčítání a násobení jsou stejné jako pro přirozená čísla a dělení je jednodušší než obvyklý algoritmus dělení. Zápis vynalezl Eric Hehner z University of Toronto a Nigel Horspool, pak v McGill University a zveřejněna v SIAM Journal on Computing, v. 8, č. 2, květen 1979, s. 124–134.
Zastoupení
Úvod
Standardní reprezentace racionálních čísel začíná znaménkem (+ nebo -; pokud není napsáno žádné znaménko, implikované znaménko je +) a pokračuje (konečnou nebo nekonečnou) posloupností číslic s bodem radix (nazývaným desetinnou čárkou v základní desítce) ) někde v pořadí. Například,
- –12.345
- 0.33333...
Aby byla reprezentace konečná, může být nad opakujícími se číslicemi použito nadměrné skóre. Některé příklady jsou:
Standardním postupem je také ponechat operátory negace a dělení v reprezentaci čísel bez provedení negace nebo dělení. Například –1/3 (mínus jedna třetina).
V notaci uvozovek má každé racionální číslo jedinečné (až do normalizace) konečné znázornění jako posloupnost číslic s bodem radix a uvozovku někde v posloupnosti. Citace znamená, že číslice nalevo se opakují nekonečně doleva. Například,
- 12'34.56 = ...12121234.56
- 12.34'56 = ...1234123412.3456
- 123!45 = ...123123123.45
Vykřičník se používá, jsou-li citace a bod na stejném místě. Pokud je opakovaná sekvence všech 0 s, lze vynechat nuly i nabídku. Radixový bod má svou obvyklou funkci; pohybem doleva se dělí o základna a jeho posunutím doprava se vynásobí základna. Když je bod radixu na pravém konci, multiplikativní faktor je 1 a bod lze vynechat. To dává přirozeným číslům jejich známou formu. Věděcký zápis lze použít jako alternativu k bodu radix.
Interpretace vedoucí opakující se sekvence je rozšířením součtu geometrické řady:
- .
Například:
a
- .
S touto konvencí jsou čísla v notaci uvozovek interpretována jako:
- 3' = ...333 = 3(... + 100 + 10 + 1) = –3/9 = –1/3
- 123' =...123123123 = 123(...1000000 + 1000 + 1) = –123/999
- 123'45.6 = 45.6 + 123'00 = 45.6 + 100 × 123' = 45.6 – 12300/999
To vede k pravidlu:
- abc ... z '= - abc ... z / 999 ... 9,
se stejným počtem 9 ve jmenovateli, jako jsou číslice v opakující se části posloupnosti. Obecná forma v matematické notaci: řetězec
představuje číslo
kde je základ reprezentace. The jsou číslice.
Přirozená čísla
The přirozená čísla jsou obecně psány tak, jak je obvykle očekáváte, ale lze je také psát pomocí explicitní nabídky, explicitního bodu radixu nebo redundantních nul na obou koncích. Například celé číslo dvě lze zapsat jako 2 nebo 2. nebo 0'2 nebo 0'2. nebo dokonce 000'02.000a celé číslo nula lze zapsat jako 0 nebo 0' nebo 0. nebo 0!.
Záporná celá čísla
Negativní celá čísla začněte číslicí o jednu menší než základna. Například v desítkové soustavě je mínus tři zapsán jako 9'7.
- 9'7 = 7 – 90/9 = –3
Tak jako
- 9' = – 9/9 = –1,
je snadno pochopitelné, že například:
- –189 = –1 × 189 = 9' × 189 = 1701 + 17010 + 170100 + ... = ...999811 = 9'811 = 811 – 1000
nebo alternativně jako:
- 9'000 = –1000,
- –189 = 811 – 1000 = 811 + 9'000
Čísla začínající jakoukoli jinou opakující se posloupností nejsou celá čísla. Například:
- 6'7 = 7 – 60/9 = 1/3
a
- 7'6 = 6 – 70/9 = – 16/9
Tlumočení nabídky
Algoritmus převodu
Chcete-li převést notaci nabídky na standardní notaci, můžete použít následující algoritmus.
- Nechat X a y být sekvence číslic, jako v .
- Nechat z být číslice 1 následovaná sekvencí nul stejné délky jako y.
- Nechat A být číslicí s největší hodnotou (o jednu menší než základna). V desítkové soustavě máme A = 9.
- Nechat w být posloupností As stejné délky jako X.
Pak číslo představované darováno .
Jako příklad si vezmeme 12'345 a převést jej na standardní notaci.
- X = 12
- y = 345
- z = 1000
- A = 9
- w = 99
Pak následuje naše standardní notace,
Určení znaménka
Pokud je počáteční číslice menší než první číslice po nabídce, je číslo kladné. Například, 123'45 je kladné, protože 1 je menší než 4. Pokud je úvodní číslice více než první číslice po nabídce, je číslo záporné. Například, 54'3 je negativní, protože 5 je více než 3.
Pokud citát přijde na konci, přidejte za bod radixu nulu. Například, 592' = 592!0, což je záporné, protože 5 je více než 0. A 59.2' = 59.2'0 což je také negativní.
Pokud se úvodní číslice rovná první číslici za uvozovkou, pak buď číslo je 0!0 = 0, nebo lze reprezentaci zkrátit otočením opakování doprava. Například, 23'25 = 32'5 což je pozitivní, protože 3 je méně než 5.
v binární, pokud začíná na 1, je záporné, a pokud začíná na 0, je to nezáporné, za předpokladu, že opakování bylo co nejvíce posunuto doprava.
Aritmetický
Přidání
V našem obvyklém zápisu znaménka a velikosti přidáme dvě celá čísla 25 a −37, jeden nejprve porovná znaménka a určí, že sčítání bude provedeno odečtením velikostí. Pak se porovná velikost, aby se určilo, od kterého se odečte, a aby se určilo znaménko výsledku. V naší obvyklé zlomkové notaci je pro přidání 2/3 + 4/5 nutné najít společného jmenovatele, vynásobit každý čitatel novými faktory v tomto společném jmenovateli, poté přidat čitatele a poté dělit čitatele a jmenovatele libovolnými faktory, které mají v běžný.
V uvozovkách, pro přidání, stačí přidat. Neexistují žádná srovnání znaménka nebo velikosti a žádní běžní jmenovatelé. Sčítání je stejné jako u přirozených čísel. Zde jsou nějaké příklady.
9'7 minus tři 9'4 minus šest + 0'6 přidat plus šest + 9'2 přidat minus osm ————— ————— 0'3 dělá plus tři 9'8 6 dělá mínus čtrnáct
6'7 jedna třetina + 7'6 přidá mínus jedna a sedmý devátý ————— 4'3 činí mínus jednu a čtyři devátá
Odčítání
V naší obvyklé notaci znaménko-a-velikost zahrnuje odčítání srovnání znaménka a srovnání velikosti a může vyžadovat přidání nebo odčítání velikostí, stejně jako sčítání. V naší obvyklé zlomkové notaci vyžaduje odčítání nalezení společného jmenovatele, násobení, odčítání a redukce na nejnižší členy, stejně jako sčítání.
V uvozovkách, odečíst, pouze odečíst. Neexistují žádná srovnávací znaménka ani magnitudy a žádní společní jmenovatelé. Když minuend číslice je menší než odpovídající subtrahend číslice, nepůjčujte si od minuendové číslice nalevo; místo toho noste (přidejte jednu) k číslici odčítání nalevo. Zde jsou nějaké příklady.
9'7 minus tři 9'4 minus šest - 0'6 odečíst plus šest - 9'2 odečíst minus osm ————— ————— 9'1 dělá minus devět 0'2 dělá plus dva
6'7 jedna třetina - 7'6 odečtení mínus jedna a sedmý devátý ————— 8'9 1 dělá plus dvě a jedna devátá
Násobení
Násobení je stejné jako u přirozených čísel. Chcete-li rozpoznat opakování v odpovědi, pomůže vám přidat dílčí výsledky po dvou. Zde jsou nějaké příklady.
6'7 x 0'3 = 0'1 jedna třetina krát tři dělá jeden
6'7 x 7'6 jedna třetina krát mínus jedna a sedmý devátý: vynásobte 6'7 číslem 6: 0'2 číslici odpovědi 2násobně 6'7 číslem 7: 6'9 doplňte: ———— 6'9 odpověď číslice 9násobek 6'7 od 7: 6'9 přidat: ———— 3'5 odpověď číslice 5multiply 6'7 od 7: 6'9 přidat: ———— 0'2 opakování originálu činí 592 'mínus šestnáct dvacet- sedminy
Pro někoho, kdo nezná notaci uvozovek, je 592 'neznámý a překlad do −16/27 je užitečný. Pro někoho, kdo běžně používá citaci, je −16/27 vzorec s operací negace a dělení; provádění těchto operací přináší odpověď 592 '.
Divize
Běžně používaný algoritmus dělení vytváří číslice zleva doprava, což je opak sčítání, odčítání a násobení. To ztěžuje další aritmetiku. Například, jak přidáme 1,234234234234 ... + 5,667676767 ...? Obvykle používáme konečný počet číslic a přibližnou odpověď přijímáme pomocí chyba zaokrouhlení. Běžně používaný algoritmus dělení také vytváří duplicitní reprezentace; například 0,499 999 ... a 0,5 představují stejné číslo. V desítkové soustavě existuje pro každou číslici určitý druh odhadu, který je při postupu výpočtu považován za správný nebo nesprávný.
V notaci uvozovek dělení vytváří číslice zprava doleva, stejné jako všechny ostatní aritmetické algoritmy; proto je další aritmetika snadná. Aritmetika nabídky je přesná, bez chyby. Každé racionální číslo má jedinečnou reprezentaci (pokud je opakování vyjádřeno co nejjednodušeji a nemáme žádný smysl 0s na pravém konci za bodem radix). Každá číslice je určena „tabulkou dělení“, což je inverzní funkce k části násobilka; neexistuje „hádání“. Zde je příklad.
9'84 / 0'27 minus šestnáct děleno dvaceti sedmičkami, protože 0'27 končí 7 a 9'84 končí 4, zeptejte se:
9'8 4 Kolikrát 7 končí na 4? Je to 2 násobně 0'27 o 2: 0'5 4 odečíst: ————— 9'3 Kolikrát 7 končí 3? Je to 9. násobek 0'27 krát 9: 0'2 4 3 odečíst: ——————— 9'7 5 Kolikrát 7 končí 5? Je to 5. několikrát 0'27 o 5: 0'1 3 5 odečíst: ——————— 9'8 4 opakování originálu dělá 592 'mínus šestnáct dvacátých sedmých
Divize funguje, když dělitel a základ nemají společné faktory kromě 1. V předchozím příkladu má 27 faktory 1, 3 a 27. Základna je 10, která má faktory 1, 2, 5 a 10. Takže dělení fungovalo. Pokud existují společné faktory, musí být odstraněny. Chcete-li například rozdělit 4 na 15, nejprve vynásobte 4 a 15 2:
4/15 = 8/30
Libovolné nuly na konci dělitele pouze řeknou, kam směřuje bod radix ve výsledku. Takže teď rozdělte 8 na 3.
0'8 Kolikrát 3 skončí za 8? Je to 6. vynásobit 0'3 x 6: 0'1 8 odečíst: ———— 9 'Kolikrát 3 skončí 9? Je to 3. násobek 0'3 krát 3: 0'9 odečíst: ———— 9 'opakování dřívějších rozdílů 3'6 dvě a dvě třetiny Nyní posuňte desetinnou čárku o jedno místo doleva a získáte 3! 6 čtyři patnáctiny
Odstranění běžných faktorů je nepříjemné a je zbytečné, pokud je základnou a prvočíslo. Počítače používají základnu 2, což je prvočíslo, takže dělení vždy funguje. A dělící tabulky jsou triviální. Jediné otázky jsou: kolikrát 1 končí 0? a: kolikrát 1 končí v 1? Tedy úplně vpravo bity v rozdílech jsou bity v odpovědi. Například jeden dělený třemi, což je 1/11, probíhá následovně.
0'1 bit zcela vpravo je 1 odečíst 0'1 1 ————— 1 'bit úplně vpravo je 1 odečíst 0'1 1 ————— 1'0 bit úplně vpravo je 0 odečíst 0' ———— 1 'opakování dřívějšího rozdíly 01'1 jedna třetina
Negace
Chcete-li negovat, doplňte každou číslici a poté přidejte 1. Například, v desítkové soustavě, k negaci 12'345, doplňte a získejte 87'654a poté přidejte 1 87'655. V binárním formátu převraťte bity a přidejte 1 (stejné jako Doplněk 2 ). Například negovat 01'1, což je jedna třetina, otočte bity, abyste získali 10'0, poté přidejte 1 a dostanete 10'1a přetočením doprava jej zkrátíte na 01' což je minus jedna třetina.
Srovnání s jinými vyjádřeními
Běžná použití racionálních čísel jsou dvě. Jeden používá znaménko (+ nebo -), za kterým následuje nezáporné celé číslo (čitatel), za kterým následuje symbol dělení a za ním celé kladné číslo (jmenovatel). Například –58/2975. (Pokud není napsáno žádné znaménko, znaménko je +.) Druhé je znaménko, za nímž následuje posloupnost číslic, s radixovým bodem (nazývaným desetinná tečka v základní desítce) někde v posloupnosti a přesahem nad jedním nebo více číslic zcela vpravo. Například, . (K nadskóre existují alternativní notace; viz Opakování desetinného místa.) O nadskóre lze uvažovat tak, že říká, že číslice pod ním se opakují navždy vpravo. V příkladu je to –0,023434343434 .... Citace notace nevyžaduje znamení; má posloupnost číslic s bodem radix někde v posloupnosti a uvozovku někde v posloupnosti. Například 4,3'2. Citát lze chápat tak, že říká, že číslice nalevo se opakují navždy doleva. V příkladu je to ... 43434343434.32. Všechny tři příklady v tomto odstavci představují stejné racionální číslo.
Tři reprezentace lze porovnat dvěma způsoby: prostor potřebný pro úložiště a čas potřebný pro aritmetické operace.
Prostor
Notace nabídky a notace overcore vyžadují v podstatě stejný prostor. Hehner a Horspool připouštějí na str. 12: „Ale citace a notace čitatele a jmenovatele se mohou značně lišit.“[Rem. 1] K nejhoršímu případu dochází u některých hlavních jmenovatelů (viz Fermatova malá věta ). Například +1/7 = 285714'3 (v binární podobě je to 011'1). Reprezentace +1/947 v binárním formátu jako znaménko a čitatel a jmenovatel vyžaduje 12 bitů a jako citace vyžaduje 947 bitů. (K oddělení dvou čísel s proměnnou délkou jsou nutné další bity, ale ty jsou u všech tří reprezentací stejné, takže jejich ignorování neovlivní srovnání.) Počet míst potřebných k reprezentaci opakovat racionálního čísla s v základně b citace je jehož maximum napříč všemi základnami b je exponent z multiplikativní skupina celých čísel modulo d který je dán Funkce Carmichael .
Výkon počítačových algoritmů se měří z hlediska délka vstupuDélka racionálního čísla v zápisu čitatele-jmenovatele je v podstatě součet logaritmy ze dvou čísel, takže je v Délka racionálního čísla v uvozovkách je součet logaritmu čitatele a délka opakování, tak je to v a tudíž exponenciální v délce vstupu.
Hehner a Horspool na str. 8:
- "180 000 nejkratších reprezentací čitatele a jmenovatele vyžaduje v průměru 15,65 bitů a stejná čísla v notaci uvozovek vyžadují v průměru 39,48 bitů." Vezmeme-li nejkratší čísla čitatel-jmenovatel a poté je přeložíme do citace notace, bude výsledkem zkreslené srovnání ve prospěch čitatele-jmenovatele. Pokud vezmeme všechny reprezentace binárních nabídek až do 14 bitů včetně (všechny pozice nabídek a všechny pozice radixových bodů), pak zahodíme ty, které nejsou normalizované, máme 1 551 567 čísel vyžadujících průměrně 13,26 bitů. Přeložíme-li je do zápisu čitatele-jmenovatele,[Rem. 2] poté normalizujte výsledek odstraněním běžných faktorů, vyžadují průměrně 26,48 bitů. Toto srovnání je zaujaté ve prospěch citace. Je obtížné navrhnout objektivní srovnání. “
... a ještě těžší prokázat. Extrapolace konečného vzorku na nekonečnou množinu má ve skutečnosti pouze omezený matematický význam.
Na druhou stranu Hehner a Horspool popisují notaci citace jako atraktivní pro použití v počítačovém hardwaru (str. 1). Hardwarové pokyny mnoha počítačů fungují na relativně malých částech paměti pevné délky, jako je slovo (32 bitů), dvojité slovo (64 bitů), 128 bitů slovo, 256 bitů slovo. Existuje pouze několik procesorů, které fungují 512 bitů data.[Rem. 3]
Následující tabulka ukazuje jmenovatele, kde je citace zápisu odpovídající zlomku nesedí na binární celé číslo o velikosti 32, 64, 128, 256 a 512 bitů. Uvedeno je nejmenších 20 jmenovatelů d pro každou velikost bloku, jejich hlavní faktory, délku opakování zlomku a hodnota Carmichael
|
|
|
|
|
Tabulka ukazuje, že notace citace je schopna zpracovat pouze docela malé jmenovatele, a to i při dosud největších velikostech bloků.
Kromě toho se Hehner a Horspool pokoušejí přehrát analýzu nejhorších případů, ale již tyto malé tabulky výše ukazují, že případy, které jsou pro jejich práci nepříznivé, jsou poměrně časté: 20 nejmenších počtů tryskajících kousky tvoří kolem 10% v rozmezí asi 200.
Tato frekvence dobře koreluje s teorémy o Paul Erdős a další, které ukazují asymptoticky exponenciální chování λ (viz oddíly Funkce Carmichael # Průměrná hodnota, Funkce Carmichael # Převládající interval, Funkce Carmichael # Dolní hranice, a Funkce Carmichael # Minimální objednávka ).
Čas
Chcete-li například přidat dvě čísla do zápisu čitatele-jmenovatele (+A/b) + (–C/d), vyžaduje následující kroky:
• porovnání znaménka k určení, zda budeme přidávat nebo odečítat; v našem příkladu se znaménka liší, takže budeme odečítat
• pak 3 násobení; v našem příkladu A×d, b×C, b×d
• pak, pokud odečítáme, srovnání A×d na b×C určit, který je subtrahend a který je minuend a co je znamením výsledku; řekněme A×d < b×C tak znamení bude -
• potom sčítání nebo odčítání; b×C – A×d a máme - (b×C – A×d)/(b×d)
• nalezení největší společný dělitel nového čitatele a jmenovatele
• vydělením čitatele a jmenovatele největším společným dělitelem k získání normalizovaného výsledku
Normalizace výsledku není nutná pro správnost, ale bez ní požadavky na prostor během sledu operací rychle rostou. Odečtení je téměř totožné s přidáním.
Přidání dvou čísel do noty nadskóre je problematické, protože na začátku není žádný pravý konec. Nejjednodušší způsob, jak provést sčítání, je přeložit čísla do citace notace, poté přidat a poté přeložit zpět. Podobně pro odčítání.
Chcete-li do nabídky uvést dvě čísla, jednoduše je přidejte stejným způsobem, jakým přidáte dvě kladná celá čísla. Opakování je rozpoznáno, když se opakující se části dvou operandů vrátí na své počáteční číslice. Výsledek může být poté normalizován kontrolou, zda se první číslice rovná první číslici po nabídce. Podobně pro odčítání. U sčítání i odčítání je citátový zápis lepší než ostatní dva zápisy.
Násobení v zápisu čitatele a jmenovatele je dvě celočíselná násobení, nalezení největšího společného dělitele a poté dvě dělení. Násobení v notaci overcore je problematické ze stejného důvodu, jako je sčítání. Násobení v zápisu uvozovek probíhá přesně jako kladné celočíselné násobení, porovnává se každý nový součet s předchozími součty, aby se detekovalo opakování. Pro multiplikaci je notace citace lepší než notace overscore a může být o něco lepší než notace čitatel-jmenovatel.
Rozdělení v zápisu čitatele a jmenovatele má stejnou složitost jako násobení v zápisu čitatele a jmenovatele. Dělení v notaci overcore je problematické, protože vyžaduje posloupnost odčítání, které jsou problematické v notaci overcore. Rozdělení v zápisu uvozovek postupuje stejně jako násobení v zápisu uvozovek, přičemž se číslice odpovědi vytvářejí zprava doleva, přičemž každá z nich je určena nejpravější číslicí aktuálního rozdílu a dělitelem (triviální v binární podobě). U dělení je notace uvozovek lepší než notace nadskóre a čitatele-jmenovatele.
Nevýhody
Náklady
Nemělo by však být potlačeno, že nejhorší náklady ve vesmíru (a u některých operací také náklady v čase) popsané nabídky jsou [Rem. 4] pro racionální číslo se jmenovatelem - ve srovnání s reprezentace čitatele-jmenovatele, což je skutečnost, díky které se notace citátu nehodí jako prostředek pro přesný zpracování racionálních čísel libovolné velikosti, např. v balíček počítačové algebry.
−1/19 | = 052631578947368421! | |
−2/19 | = 105263157894736842! | |
[−1/10011]2 | = [000011010111100101!]2 | |
[−10/10011]2 | = [000110101111001010!]2 | |
To znamená: desetinná místa / duály v notaci nabídky odpovídají 3 resp. 7 desetinných míst / duálů v notaci čitatele-jmenovatele. | ||
−1/59 | = 0169491525423728813559322033898305084745762711864406779661! | |
−2/59 | = 0338983050847457627118644067796610169491525423728813559322! | |
[−1/111011]2 | = [0000010001010110110001111001011111011101010010011100001101!]2 | |
[−10/111011]2 | = [0000100010101101100011110010111110111010100100111000011010!]2 | |
To znamená: desetinná místa / duály v notaci nabídky odpovídají 3 resp. 8 desetinných míst / duálů v zápisu čitatele-jmenovatele. |
- Poznámka: Posloupnost desetinných / duálních vyjádření čitatele 2 je a otočený posun znázornění čitatele 1.
Zaokrouhlování zkrácením
Zkrácení vlevo nelze použít pro zaokrouhlování v systému nabídek. Autoři neposkytují přibližné verze operátorů sčítání, odčítání, násobení a dělení, místo toho navrhují převod na notaci overscore a poté zkrácení vpravo.
To znamená, že operace musí být rozšířeny na celou opakující se skupinu a poté převedeny, což ve světle sekce #Náklady se nezdá být proveditelným návrhem.
Nulové dělitele
Pokud základna je kompozitní, prsten obsahuje nulové dělitele. Předpokládejme . Protože , žádný racionální vstup je nulový dělitel. Ale existují (neracionální) čísla což jsou a , ale produkt je .
Poznámky
- ^ Totéž platí pro každou notaci hodnoty místa, nezávisle na zvolené základně.
- ^ Překládáním sem a tam se tedy snaží navodit dojem, že představují objektivní hodnocení.
- ^ Až dosud se každá podpora pro objekty s proměnnou délkou provádí v softwaru - a nikoli v hardwaru. Je to pravděpodobně proto
- příslušná míra komplikace dosud nebyla zvládnuta,
- alespoň pro navrhované objekty,
- zisk hardwarového řešení je ve srovnání se softwarem příliš malý,
- nebo je prodejní místo příliš nízké.
- ^ Zdroj ve skutečnosti neřeší -problém: "Ale citace notace a čitatel-jmenovatel notace značně zviditelní." a zmínit což vyžaduje 946 bitů v opakující se skupině. Ale takových jmenovatelů je nekonečně mnoho, všichni mají relativně velké totient funkce, e. G. s .
Ve svém 3. dodatku přidaném později přidávají některé úvahy .
Reference
- Hehner, E.C.R .; Horspool, R.N.S. (Květen 1979), Nové znázornění racionálních čísel pro rychlou snadnou aritmetiku (PDF), SIAM J. Comput. 8 č. 2 str. 124-134