Notacja cytatu - Quote notation

Notacja cytat jest reprezentacja liczb wymiernych na podstawie Kurt Hensel „s liczb p-adic . W notacji cudzysłowu operacje arytmetyczne przyjmują szczególnie proste, spójne formy, dając dokładne odpowiedzi bez błędu zaokrąglenia . Algorytmy arytmetyczne notacji cudzysłowu działają w kierunku od prawej do lewej; algorytmy dodawania, odejmowania i mnożenia są takie same jak w przypadku liczb naturalnych , a dzielenie jest łatwiejsze niż zwykły algorytm dzielenia. Notacja została wymyślona przez Erica Hehnera z University of Toronto i Nigela Horspoola , a następnie z McGill University i opublikowana w SIAM Journal on Computing , wersja 8, nr 2, maj 1979, strony 124–134.

Reprezentacja

Wprowadzenie

Standardowa reprezentacja liczb wymiernych zaczyna się od znaku (+ lub -; jeśli żaden znak nie jest zapisany, domniemany znak to +) i jest kontynuowany (skończoną lub nieskończoną) sekwencją cyfr z kropką (nazywaną przecinkiem dziesiętnym o podstawie dziesięć) ) gdzieś w sekwencji. Dla przykładów,

–12.345

0,33333 ...

Aby reprezentacja była skończona, nad powtarzającymi się cyframi można zastosować nadliczbę. Oto kilka przykładów:

{\ displaystyle -0.02 {\ overline {34}}}

Standardową praktyką jest również pozostawianie operatorów negacji i dzielenia w reprezentacji liczb, bez wykonywania negacji lub dzielenia. Na przykład –1/3 (minus jedna trzecia).

W notacji cudzysłowu każda liczba wymierna ma unikalną (aż do normalizacji) skończoną reprezentację jako ciąg cyfr z punktem podstawy i cudzysłowem gdzieś w sekwencji. Cudzysłów oznacza, że cyfry po jego lewej stronie są powtarzane w nieskończoność w lewo. Dla przykładów,

12'34,56 = ... 12121234,56

12,34'56 = ... 1234123412,3456

123! 45 = ... 123123123,45

Wykrzyknik jest używany, gdy cytat i punkt znajdują się w tym samym miejscu. Jeśli powtórzona sekwencja to wszystkie zera, można pominąć zera i cudzysłów. Punkt podstawy ma swoją zwykłą funkcję; przesunięcie w lewo dzieli przez podstawę , a przesunięcie w prawo mnoży przez podstawę. Gdy punkt podstawy znajduje się na prawym końcu, mnożnik wynosi 1 i punkt można pominąć. To nadaje liczbom naturalnym ich znaną postać. Notacja naukowa może być stosowana jako alternatywa dla punktu podstawy.

Interpretacja wiodącej powtarzającej się sekwencji jest rozszerzeniem sumy szeregu geometrycznego :

{\ Displaystyle 1 + 10 ^ {k} + 10 ^ {2k} + 10 ^ {3k} + ... = {\ tfrac {1} {1-10 ^ {k}}}}

.

Na przykład:

{\ Displaystyle 1 + 10 + 100 + 1000 + ... = {\ tfrac {1} {1-10}} = - {\ tfrac {1} {9}}}

i

{\ Displaystyle 1 + 1000 + 1000 ^ {2} + 1000 ^ {3} + ... = {\ tfrac {1} {1-1000}} = - {\ tfrac {1} {999}}}

.

Zgodnie z tą konwencją liczby w notacji cudzysłowu są interpretowane 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

Prowadzi to do reguły:

abc ... z '= - abc ... z / 999 ... 9,

z taką samą liczbą 9 w mianowniku, jak cyfry w powtarzającej się części ciągu. Ogólna forma w notacji matematycznej: ciąg

{\ Displaystyle d_ {n + m} d_ {n + m-1} \ dotsb d_ {n + 1} ^ {\; \; \; \; \, \ shortmid} d_ {n} d_ {n-1} \ dotsb d_ {2} d_ {1} d_ {0}}

reprezentuje liczbę

{\ Displaystyle \ sum _ {i = 0} ^ {n} d_ {i} b ^ {i} - \ sum _ {i = n + 1} ^ {n + m} d_ {i} b ^ {i} / (b ^ {m} -1)}

gdzie jest podstawa reprezentacji. To są cyfry. ${\ displaystyle b \ in \ mathbb {Z} \ setminus \ {\ pm 1,0 \}}$ ${\ Displaystyle d_ {i} \ in \ {0,1, \ dotsc, b-1 \}}$

Liczby naturalne

Te liczby naturalne są zazwyczaj napisany w taki sposób, jeden zazwyczaj oczekuje się ich zobaczyć, ale mogą być również napisany przy użyciu wyraźnej cytat, wyraźny punkt radix lub nadmiarowych zer na obu końcach. Na przykład liczbę całkowitą dwa można zapisać jako 2 lub 2. lub 0'2 lub 0'2. lub nawet 000'02.000 , a liczbę całkowitą zero można zapisać jako 0 lub 0 ' lub 0 lub 0! .

Ujemne liczby całkowite

Ujemne liczby całkowite zaczynają się od cyfry o jeden mniejszej od podstawy. Na przykład w systemie dziesiętnym minus trzy zapisuje się jako 9'7 .

9'7 = 7 - 90/9 = –3

Tak jak

9 ' = - 9/9 = –1,

łatwo zrozumieć, że na przykład:

–189 = –1 × 189 = 9 ' × 189 = 1701 + 17010 + 170100 + ... = ... 999811 = 9'811 = 811 - 1000

lub alternatywnie jako:

9'000 = –1000,

–189 = 811 - 1000 = 811 + 9'000

Liczby zaczynające się od dowolnej innej powtarzającej się sekwencji nie są liczbami całkowitymi. Na przykład:

6'7 = 7 - 60/9 = 1/3

i

7'6 = 6 - 70/9 = - 16/9

Interpretacja notacji cudzysłowu

Algorytm konwersji

Aby przekonwertować notację cudzysłowu na notację standardową, można użyć następującego algorytmu.

Niech

x

i

y

będą ciągami cyfr, jak w .

{\ displaystyle x'y}

Niech

z

będzie cyfrą 1, po której następuje ciąg zer o takiej samej długości jak

y

.

Niech

a

będzie cyfrą o największej wartości (o jedną mniej niż podstawa). W systemie dziesiętnym mamy

a = 9

.

Niech

w

będzie ciągiem

a

s o tej samej długości co

x

.

Następnie liczba reprezentowana przez jest podawana przez . ${\ displaystyle x'y}$ ${\ displaystyle y-xz / w}$

Jako przykład weźmiemy 12'345 i przekonwertujemy je na notację standardową.

x = 12

y = 345

z = 1000

a = 9

w = 99

Następnie następuje nasz standardowy zapis,

{\ Displaystyle 345 - {\ dfrac {12 \ razy 1000} {99}} = {\ dfrac {7385} {33}}.}

Określenie znaku

Jeśli wiodąca cyfra jest mniejsza niż pierwsza cyfra po cudzysłowie, liczba jest dodatnia. Na przykład 123'45 jest dodatnie, ponieważ 1 jest mniejsze niż 4. Jeśli pierwsza cyfra jest większa niż pierwsza cyfra po cudzysłowie, liczba jest ujemna. Na przykład 54'3 jest ujemne, ponieważ 5 to więcej niż 3.

Jeśli cytat znajduje się na końcu, po prostu dodaj zero po punkcie podstawy. Na przykład 592 ' = 592! 0 , co jest wartością ujemną, ponieważ 5 to więcej niż 0. A 59,2' = 59,2'0, co również jest ujemne.

Jeśli wiodąca cyfra jest równa pierwszej cyfrze po cudzysłowie, to albo liczba wynosi 0! 0 = 0 , albo reprezentację można skrócić, przewijając powtórzenie w prawo. Na przykład 23'25 = 32'5, co jest wartością dodatnią, ponieważ 3 jest mniejsze niż 5.

W systemie binarnym , jeśli zaczyna się od 1, jest ujemne, a jeśli zaczyna się od 0, jest nieujemne, zakładając, że powtórzenie zostało przesunięte w prawo tak daleko, jak to możliwe.

Arytmetyka

Dodanie

W naszej zwykłej notacji znak i wielkość, aby dodać dwie liczby całkowite 25 i -37, najpierw porównuje się znaki i ustala, że dodawanie zostanie wykonane przez odjęcie wielkości. Następnie porównuje się wielkości, aby określić, która z nich zostanie odjęta, i określić znak wyniku. W naszym zwykłym zapisie ułamkowym dodanie 2/3 + 4/5 wymaga znalezienia wspólnego mianownika, pomnożenia każdego licznika przez nowe czynniki w tym wspólnym mianowniku, a następnie dodania liczników, a następnie podzielenia licznika i mianownika przez wszelkie czynniki, które mają w wspólny.

Aby dodać, po prostu dodaj. Nie ma porównań znaków ani wielkości ani wspólnych mianowników. Dodawanie jest takie samo jak w przypadku liczb naturalnych. Oto kilka przykładów.

  9'7 minus three              9'4 minus six
+ 0'6 add plus six          +  9'2 add minus eight
—————                        —————
  0'3 makes plus three       9'8 6 makes minus fourteen

  6'7 one-third
+ 7'6 add minus one and seven-ninths
—————
  4'3 makes minus one and four-ninths

Odejmowanie

W naszej zwykłej notacji znak i wielkość odejmowanie obejmuje porównywanie znaków i porównywanie wielkości i może wymagać dodania lub odjęcia wielkości, tak jak dodawanie. W naszej zwykłej notacji ułamkowej odejmowanie wymaga znalezienia wspólnego mianownika, mnożenia, odejmowania i redukowania do najniższych wyrazów, tak jak dodawanie.

W notacji cudzysłowu, aby odjąć, po prostu odejmij. Nie ma porównań znaków ani wielkości ani wspólnych mianowników. Kiedy cyfra odejścia jest mniejsza niż odpowiadająca jej cyfra odjemna , nie pożyczaj od cyfry odejścia po jej lewej stronie; zamiast tego przenieś (dodaj jeden) do odejmowanej cyfry po jej lewej stronie. Oto kilka przykładów.

  9'7 minus three              9'4 minus six
- 0'6 subtract plus six     -  9'2 subtract minus eight
—————                        —————
  9'1 makes minus nine         0'2 makes plus two

  6'7 one-third
- 7'6 subtract minus one and seven-ninths
—————
8'9 1 makes plus two and one-ninth

Mnożenie

Mnożenie jest takie samo jak w przypadku liczb naturalnych. Aby rozpoznać powtórzenie w odpowiedzi, warto dodać parami wyniki częściowe. Oto kilka przykładów.

6'7 x 0'3 = 0'1 one-third times three makes one

6'7 x 7'6 one-third times minus one and seven-ninths:
multiply 6'7 by 6:        0'2 answer digit 2
multiply 6'7 by 7:      6'9
              add:     ————
                        6'9 answer digit 9
multiply 6'7 by 7:    6'9
              add:   ————
                      3'5 answer digit 5
multiply 6'7 by 7:  6'9
              add: ————
                    0'2 repetition of original
makes 592' minus sixteen twenty-sevenths

Dla kogoś, kto nie jest zaznajomiony z notacją cudzysłowu, 592 'jest nieznane, a tłumaczenie na −16/27 jest pomocne. Dla kogoś, kto normalnie używa notacji cudzysłowu, −16/27 jest formułą zawierającą negację i dzielenie; wykonanie tych operacji daje odpowiedź 592 '.

Podział

Powszechnie używany algorytm dzielenia generuje cyfry od lewej do prawej, co jest przeciwieństwem dodawania, odejmowania i mnożenia. Utrudnia to dalsze działania arytmetyczne. Na przykład, jak dodać 1,234234234234 ... + 5.67676767 ...? Zwykle używamy skończonej liczby cyfr i akceptujemy przybliżoną odpowiedź z błędem zaokrąglenia . Powszechnie używany algorytm dzielenia również tworzy zduplikowane reprezentacje; na przykład 0,499999 ... i 0,5 reprezentują tę samą liczbę. W systemie dziesiętnym dla każdej cyfry istnieje rodzaj przypuszczenia, który w miarę postępu obliczeń jest postrzegany jako poprawny lub błędny.

W notacji cudzysłowu dzielenie tworzy cyfry od prawej do lewej, tak samo jak wszystkie inne algorytmy arytmetyczne; dlatego dalsza arytmetyka jest łatwa. Cytuj arytmetyka jest dokładna, bez błędów. Każda liczba wymierna ma unikalną reprezentację (jeśli powtórzenie jest wyrażone tak prosto, jak to tylko możliwe, a nie mamy bezsensownych zer na prawym końcu po punkcie podstawy). Każda cyfra jest określona przez „tabelę dzielenia”, która jest odwrotnością części tabliczki mnożenia ; nie ma „zgadywania”. Oto przykład.

9'84 / 0'27 minus sixteen divided by twenty-seven
since 0'27 ends in 7 and 9'84 ends in 4, ask:

                          9'8 4 What times 7 ends in 4? It's 2
multiply 0'27 by 2:       0'5 4
          subtract:       —————
                          9'3   What times 7 ends in 3? It's 9.
multiply 0'27 by 9:   0'2 4 3
          subtract:   ———————
                      9'7 5   What times 7 ends in 5? It's 5.
multiply 0'27 by 5: 0'1 3 5
          subtract: ———————
                    9'8 4 repetition of original
makes 592' minus sixteen twenty-sevenths

Dzielenie działa, gdy dzielnik i podstawa nie mają wspólnych współczynników z wyjątkiem 1. W poprzednim przykładzie 27 ma współczynniki 1, 3 i 27. Podstawą jest 10, która ma współczynniki 1, 2, 5 i 10. Tak więc dzielenie pracował. Jeśli istnieją wspólne czynniki, należy je usunąć. Na przykład, aby podzielić 4 przez 15, najpierw pomnóż 4 i 15 przez 2:

4/15 = 8/30

Wszelkie 0 na końcu dzielnika mówią tylko, gdzie znajduje się punkt podstawy w wyniku. Więc teraz podziel 8 przez 3.

                      0'8 What times 3 ends in 8? It's 6.
multiply 0'3 by 6:  0'1 8
         subtract:   ————
                      9' What times 3 ends in 9? It's 3.
multiply 0'3 by 3:  0'9
         subtract: ————
                    9' repetition of earlier difference
makes 3'6 two and two-thirds
Now move the decimal point one place left, to get
3!6 four-fifteenths

Usuwanie czynników wspólnych jest denerwujące i nie jest konieczne, jeśli podstawą jest liczba pierwsza . Komputery używają podstawy 2, która jest liczbą pierwszą, więc dzielenie zawsze działa. A tabele podziału są banalne. Jedyne pytania to: kiedy 1 kończy się na 0? i: jakie czasy 1 kończy się na 1? Zatem najbardziej prawe bity w różnicach to bity w odpowiedzi. Na przykład jedna podzielona przez trzy, czyli 1/11, przebiega w następujący sposób.

             0'1 rightmost bit is 1
  subtract 0'1 1
           —————
             1'  rightmost bit is 1
subtract 0'1 1
         —————
         1'0   rightmost bit is 0
subtract   0'
         ————
         1'   repetition of earlier difference
makes 01'1 one-third

Negacja

Aby zanegować, uzupełnij każdą cyfrę, a następnie dodaj 1. Na przykład dziesiętnie, aby zanegować 12'345 , uzupełnij i uzyskaj 87'654 , a następnie dodaj 1, aby uzyskać 87'655 . W systemie binarnym odwróć bity, a następnie dodaj 1 (tak samo jak uzupełnienie do 2 ). Na przykład, aby zanegować 01'1 , czyli jedną trzecią, odwróć bity, aby uzyskać 10'0 , a następnie dodaj 1, aby uzyskać 10'1 , i obróć w prawo, aby skrócić je do 01 ', czyli minus jedna trzecia.

Porównanie z innymi reprezentacjami

Istnieją dwie powszechnie używane reprezentacje liczb wymiernych. Używa się znaku (+ lub -), po którym następuje nieujemna liczba całkowita (licznik), po której następuje symbol dzielenia, po którym następuje dodatnia liczba całkowita (mianownik). Na przykład –58/2975. (Jeśli nie jest zapisany żaden znak, jest to +.) Drugi to znak, po którym następuje sekwencja cyfr, z punktem podstawy (nazywanym kropką dziesiętną w systemie dziesiętnym) gdzieś w sekwencji i nadciśnieniem nad jednym lub większą liczbą z prawej strony cyfr. Na przykład . (Istnieją alternatywne zapisy dla overcore; patrz Powtarzanie ułamka dziesiętnego ). O nadliczbie można myśleć, że oznacza to, że cyfry pod nim powtarzają się na zawsze w prawo. W tym przykładzie jest to –0,023434343434…. Notacja cudzysłowu nie wymaga znaku; ma ciąg cyfr z punktem podstawy gdzieś w sekwencji i cudzysłowem gdzieś w sekwencji. Na przykład 4,3'2. Cytat można traktować jako stwierdzenie, że cyfry po jego lewej stronie powtarzają się na zawsze po lewej stronie. W tym przykładzie jest to ... 43434343434.32. Wszystkie trzy przykłady w tym akapicie reprezentują tę samą liczbę wymierną. ${\ displaystyle -0.02 {\ overline {34}}}$

{\ Displaystyle -58 / 2975 = -0,02 {\ overline {34}} = 4,3 {\ tekst {'}} 2}

Te trzy reprezentacje można porównać na dwa sposoby: miejsce wymagane do przechowywania i czas wymagany do wykonywania operacji arytmetycznych.

Przestrzeń

Notacja cudzysłowu i notacja overcore wymagają zasadniczo tej samej przestrzeni. Hehner i Horspool przyznają na s. 12: „Ale notacja cudzysłowu i notacja licznik-mianownik mogą się znacznie różnić.” Najgorszy przypadek ma miejsce w przypadku niektórych głównych mianowników (patrz małe twierdzenie Fermata ). Na przykład +1/7 = 285714'3 (binarnie jest to 011'1). Aby przedstawić +1/947 w systemie dwójkowym jako znak, licznik i mianownik wymaga 12 bitów, a notacja cudzysłowu wymaga 947 bitów. (Wymagane dodatkowe bity są do oddzielania dwóch liczb o zmiennej długości, ale te są takie same dla wszystkich trzech przedstawień, więc ignorowanie ich nie wpływa na porównanie.) Liczba miejsc wymagane do reprezentowania repetend liczby racjonalnego ze w bazie $b$ cytat notację których maksymalna we wszystkich baz $b$ jest wykładnikiem na $przykład multiplikatywna grupa liczb modulo$ $D$ , który jest przedstawiony w funkcji Carmichael . ${\ displaystyle n / d}$ ${\ Displaystyle \ gcd (d, b) = 1}$ ${\ displaystyle \ operatorname {ord} _ {d} (b) = \ min \ {k \; \ colon \, b ^ {k} \ equiv 1 {\ text {mod}} d \}}$ ${\ Displaystyle \ lambda (d)}$

Wydajność algorytmów komputerowych mierzona jest długością wejścia . Długość liczby wymiernej w notacji licznik-mianownik jest zasadniczo suma logarytmów dwóch liczb, więc jest to w długość racjonalnej liczby w notacji cytując jest sumą logarytmu liczniku a długość z okres ułamka, ${\ displaystyle n / d}$ ${\ Displaystyle {\ mathcal {O}} (\ log (n) + \ log (d)).}$ ${\ displaystyle n / d}$ ${\ Displaystyle {\ mathcal {O}} (\ log (n))}$ ${\ displaystyle {\ mathcal {O}} (d)}$ więc jest w, a więc wykładniczy w długości wejścia. ${\ Displaystyle {\ mathcal {O}} (\ log (n) + d)}$

Hehner i Horspool na str. 8:

„180 000 najkrótszych reprezentacji licznik-mianownik wymaga średnio 15,65 bitów, a te same liczby w notacji cudzysłowu wymagają średnio 39,48 bitów. Przyjmowanie najkrótszych liczb licznik-mianownik, a następnie przekładanie tych liczb na notację cudzysłowu skutkuje tendencyjnym porównaniem na korzyść licznika-mianownika. Jeśli weźmiemy wszystkie binarne reprezentacje kwotowań do 14 bitów włącznie (wszystkie pozycje kwotowań i wszystkie pozycje punktów radix), a następnie odrzucimy te, które nie są znormalizowane, otrzymamy 1551 567 liczb wymagających średnio 13,26 bitów. Jeśli przetłumaczymy je na notację licznik-mianownik, a następnie znormalizujemy wynik, usuwając wspólne czynniki, wymagają średnio 26,48 bitów. To porównanie jest tendencyjne na korzyść notacji cudzysłowu. Trudno jest zaprojektować obiektywne porównanie ”.

... a jeszcze trudniej udowodnić. W rzeczywistości ekstrapolacja skończonej próbki do nieskończonego zbioru ma tylko ograniczone znaczenie matematyczne.

Z drugiej strony Hehner i Horspool opisują notację cytatów jako atrakcyjną do wykorzystania w sprzęcie komputerowym (s. 1). Instrukcje sprzętowe wielu komputerów działają na stosunkowo małych fragmentach pamięci o stałej długości, takich jak słowo (32 bity), podwójne słowo (64 bity), 128-bitowe słowo, 256-bitowe słowo. Jest tylko kilka procesorów, które działają na 512-bitowych danych.

W poniższej tabeli przedstawiono mianowniki, w przypadku których notacja cudzysłowu odpowiedniego ułamka nie pasuje do binarnej liczby całkowitej o rozmiarze odpowiednio 32, 64, 128, 256 i 512 bitów. Podano najmniejsze 20 mianowników $d$ dla każdego rozmiaru porcji, ich czynniki pierwsze, długość powtórzenia ułamka i wartość Carmichaela ${\ displaystyle 1 / d}$ ${\ displaystyle \ mathrm {ord} _ {d} (2)}$ ${\ displaystyle 1 / d}$ ${\ Displaystyle \ lambda (d).}$

${\ Displaystyle \ mathrm {ord} _ {d} (2)> 32}$
$re$	$czynniki$	$ord$	$λ$
37	37	36	36
53	53	52	52
59	59	58	58
61	61	60	60
67	67	66	66
71	71	35	70
74	2 · 37	36	36
79	79	39	78
81	3 ⁴	54	54
83	83	82	82
95	5 · 19	36	36
97	97	48	96
101	101	100	100
103	103	51	102
106	2 · 53	52	52
107	107	106	106
109	109	36	108
111	3 · 37	36	36
115	5 · 23	44	44
118	2 · 59	58	58

${\ Displaystyle \ mathrm {ord} _ {d} (2)> 64}$
$re$	$czynniki$	$ord$	$λ$
67	67	66	66
83	83	82	82
101	101	100	100
107	107	106	106
121	11 ²	110	110
125	5 ³	100	100
131	131	130	130
134	2 · 67	66	66
137	137	68	136
139	139	138	138
149	149	148	148
163	163	162	162
166	2 · 83	82	82
167	167	83	166
169	13 ²	156	156
173	173	172	172
179	179	178	178
181	181	180	180
191	191	95	190
193	193	96	192

${\ Displaystyle \ mathrm {ord} _ {d} (2)> 128}$
$re$	$czynniki$	$ord$	$λ$
131	131	130	130
139	139	138	138
149	149	148	148
163	163	162	162
169	13 ²	156	156
173	173	172	172
179	179	178	178
181	181	180	180
197	197	196	196
211	211	210	210
227	227	226	226
243	3 ⁵	162	162
262	2 · 131	130	130
263	263	131	262
269	269	268	268
271	271	135	270
278	2 · 139	138	138
289	17 ²	136	272
293	293	292	292
298	2 · 149	148	148

${\ Displaystyle \ mathrm {ord} _ {d} (2)> 256}$
$re$	$czynniki$	$ord$	$λ$
269	269	268	268
293	293	292	292
317	317	316	316
347	347	346	346
349	349	348	348
361	19 ²	342	342
373	373	372	372
379	379	378	378
389	389	388	388
419	419	418	418
421	421	420	420
443	443	442	442
461	461	460	460
467	467	466	466
491	491	490	490
509	509	508	508
521	521	260	520
523	523	522	522
538	2 · 269	268	268
541	541	540	540

${\ Displaystyle \ mathrm {ord} _ {d} (2)> 512}$
$re$	$czynniki$	$ord$	$λ$
523	523	522	522
541	541	540	540
547	547	546	546
557	557	556	556
563	563	562	562
587	587	586	586
613	613	612	612
619	619	618	618
653	653	652	652
659	659	658	658
661	661	660	660
677	677	676	676
701	701	700	700
709	709	708	708
757	757	756	756
773	773	772	772
787	787	786	786
797	797	796	796
821	821	820	820
827	827	826	826

Tabela pokazuje, że notacja cudzysłowu jest w stanie obsłużyć tylko bardzo małe mianowniki, nawet przy największych dostępnych obecnie rozmiarach fragmentów.

Ponadto Hehner i Horspool starają się pomniejszyć analizę najgorszego przypadku, ale już te małe tabele powyżej pokazują, że przypadki niekorzystne dla ich tezy są dość częste: 20 najmniejszych liczb, które wybijają kawałki, stanowią około 10% w zakresie około 200.

Częstotliwość ta dobrze koreluje z twierdzeniami Paula Erdősa i innych, które pokazują asymptotycznie wykładnicze zachowanie $λ$ (patrz rozdziały: Funkcja Carmichaela # Wartość średnia , funkcja Carmichaela # Przedział przeważający , funkcja Carmichaela # Granice dolne i funkcja Carmichaela # Kolejność minimalna ).

Czas

Aby dodać dwie liczby w notacji licznik-mianownik, na przykład (+ a / b ) + (- c / d ), należy wykonać następujące czynności:

• porównanie znaków w celu określenia, czy będziemy dodawać, czy odejmować; w naszym przykładzie znaki są różne, więc będziemy odejmować

• następnie 3 mnożenia; w naszym przykładzie a × d , b × c , b × d

• wtedy, jeśli odejmujemy, porównanie a × d do b × c, aby określić, które jest odejmowane, a które odjemne, i jaki jest znak wyniku; powiedzmy a × d < b × c więc znak będzie -

• następnie dodawanie lub odejmowanie; b × c - a × d i mamy - ( b × c - a × d ) / ( b × d )

• znalezienie największego wspólnego dzielnika nowego licznika i mianownika

• dzielenie licznika i mianownika przez ich największy wspólny dzielnik w celu uzyskania znormalizowanego wyniku

Normalizacja wyniku nie jest konieczna do poprawności, ale bez niej wymagania przestrzenne szybko rosną podczas sekwencji operacji. Odejmowanie jest prawie identyczne jak dodawanie.

Dodanie dwóch liczb w notacji overscore jest problematyczne, ponieważ nie ma właściwego końca, od którego można by zacząć. Najłatwiejszym sposobem dodania jest przetłumaczenie liczb na notację cytowania, a następnie dodanie i przetłumaczenie z powrotem. Podobnie do odejmowania.

Aby dodać dwie liczby w notacji cudzysłowu, po prostu dodaj je w ten sam sposób, w jaki dodajesz dwie dodatnie liczby całkowite. Powtórzenie jest rozpoznawane, gdy powtarzające się części dwóch operandów powracają do swoich początkowych cyfr. Następnie wynik można znormalizować przechylaniem, sprawdzając, czy pierwsza cyfra jest równa pierwszej cyfrze po cudzysłowie. Podobnie do odejmowania. Zarówno w przypadku dodawania, jak i odejmowania notacja cudzysłowu jest lepsza od pozostałych dwóch notacji.

Mnożenie w notacji licznik-mianownik to dwa mnożenia liczb całkowitych, znalezienie największego wspólnego dzielnika, a następnie dwa dzielenia. Mnożenie w notacji overscore jest problematyczne z tego samego powodu co dodawanie. Mnożenie w notacji cudzysłowu przebiega dokładnie tak samo, jak mnożenie dodatnich liczb całkowitych, porównując każdą nową sumę z poprzednimi sumami w celu wykrycia powtórzenia. W przypadku mnożenia notacja cudzysłowu jest lepsza niż notacja z nadrycą i może być nieco lepsza niż notacja licznik-mianownik.

Dzielenie w notacji licznik-mianownik ma taką samą złożoność jak mnożenie w notacji licznik-mianownik. Dzielenie w notacji overscore jest problematyczne, ponieważ wymaga sekwencji odejmowań, które są problematyczne w notacji overscore. Dzielenie w notacji cudzysłowu przebiega tak samo, jak mnożenie w notacji cudzysłowu, tworząc cyfry odpowiedzi od prawej do lewej, z których każda jest określona przez skrajną prawą cyfrę bieżącej różnicy i dzielnika (trywialne w systemie dwójkowym). W przypadku dzielenia notacja cudzysłowu jest lepsza zarówno od notacji typu overscore, jak i notacji licznik-mianownik.

Wady

Koszt

Nie należy jednak ukrywać, że najgorszy przypadek koszt w przestrzeni (a dla niektórych operacji również koszt w czasie) opisanego notacji cudzysłowu dotyczy liczby wymiernej z mianownikiem - w porównaniu z reprezentacją licznik-mianownik, fakt co sprawia, że notacja cudzysłowu nie nadaje się jako środek do dokładnej obsługi liczb wymiernych o dowolnej wielkości, np. w pakiecie algebry komputerowej . ${\ displaystyle {\ mathcal {O}} (d)}$ ${\ Displaystyle d \ in \ mathbb {N}}$ ${\ Displaystyle {\ mathcal {O}} (\ log d)}$

Przykłady
${\ displaystyle d = 19:}$
	−1/19	= 052631578947368421!
	−2/19	= 105263157894736842!
	[-1/10011] ₂	= [000011010111100101!] ₂
	[−10/10011] ₂	= [000110101111001010!] ₂
	Oznacza to: liczby dziesiętne / podwójne w notacji cudzysłowu odpowiadają 3 odpowiednio. 7 miejsc po przecinku / liczby podwójne w notacji licznik-mianownik. ${\ displaystyle d-1 = 18}$

${\ displaystyle d = 59:}$
	−1/59	= 0169491525423728813559322033898305084745762711864406779661!
	−2/59	= 0338983050847457627118644067796610169491525423728813559322!
	[−1/111011] ₂	= [0000010001010110110001111001011111011101010010011100001101!] ₂
	[−10/111011] ₂	= [0000100010101101100011110010111110111010100100111000011010!] ₂
	Oznacza to: liczby dziesiętne / podwójne w notacji cudzysłowu odpowiadają 3 odpowiednio. 8 miejsc po przecinku / podwójnych w notacji licznik-mianownik. ${\ displaystyle d-1 = 58}$

Uwaga: Sekwencja liczb dziesiętnych / podwójnych reprezentacji licznika 2 to obrócone przesunięcie reprezentacji licznika 1.

Zaokrąglanie przez obcięcie

Obcięcie po lewej stronie nie może być używane do celów zaokrąglania w systemie notacji kwotowań. Autorzy nie podają przybliżonych wersji operatorów dodawania, odejmowania, mnożenia i dzielenia, zamiast tego proponują konwersję do notacji nadrycji, a następnie obcięcie po prawej stronie.

Oznacza to, że operacje muszą zostać rozszerzone na pełną powtarzającą się grupę, a następnie przekonwertowane, co w świetle sekcji #Cost nie wydaje się praktyczną propozycją.

Zero-dzielniki

Jeśli podstawa jest złożona , pierścień zawiera zero dzielników . Załóżmy . Ponieważ żaden racjonalny element nie jest zerowym dzielnikiem. Ale istnieją (nieracjonalne) liczby, które są i , ale iloczyn jest . ${\ displaystyle d = e \ cdot f}$ ${\ displaystyle \ mathbb {Z} _ {d}}$ ${\ Displaystyle d = 10 = 2 \ cdot 5}$ ${\ Displaystyle \ mathbb {Q} _ {2} \ cap \ mathbb {Q} _ {5} = \ mathbb {Q}}$ ${\ displaystyle \ mathbb {Z} _ {10}}$ ${\ displaystyle 1_ {2}, 1_ {5} \ in \ mathbb {Z} _ {10}}$ ${\ displaystyle 1_ {2} \ equiv _ {\ mathbb {Z} _ {2}} 1}$ ${\ displaystyle 1_ {5} \ equiv _ {\ mathbb {Z} _ {5}} 1}$ ${\ Displaystyle 1_ {2} \ cdot 1_ {5} = _ {\ mathbb {Z} _ {10}} 0}$

Uwagi

^ To samo dotyczy każdej notacji wartość-miejsce, niezależnie od wybranej podstawy.
^ Dlatego tłumacząc w przód iw tył, starają się sprawiać wrażenie, że przedstawiają obiektywną ocenę.
^
Do tej pory każda obsługa obiektów o zmiennej długości odbywa się w oprogramowaniu, a nie w sprzęcie. Jest to najprawdopodobniej spowodowane
1. stopień powikłań nie został jeszcze opanowany,
2. przynajmniej dla proponowanych obiektów,
3. zysk rozwiązania sprzętowego jest zbyt mały w porównaniu z oprogramowaniem,
4. lub punkt sprzedaży jest zbyt niski.
^ Źródło tak naprawdę nie rozwiązuje problemu: „Ale notacja cudzysłowu i notacja licznik-mianownik mogą się znacznie różnić.” i wzmianka, która wymaga 946 bitów w powtarzającej się grupie. Ale takich mianowników jest nieskończenie wiele, wszystkie mają stosunkowo dużą funkcję totientową , np. sol. z . W swoim trzecim „Dodatku dodanym później” dodają kilka uwag . ${\ displaystyle {\ mathcal {O}} (d)}$ ${\ displaystyle d = 947}$ ${\ displaystyle d = 802787}$ ${\ Displaystyle \ varphi (d) = 802786}$
${\ displaystyle d = 59}$

Bibliografia

Hehner, ECR; Horspool, RNS (maj 1979), Nowa reprezentacja liczb wymiernych dla szybkiej i łatwej arytmetyki (PDF) , SIAM J. Comput. 8 nr 2 strony 124-134

[1] To samo dotyczy każdej notacji wartość-miejsce, niezależnie od wybranej podstawy.

[2] Dlatego tłumacząc w przód iw tył, starają się sprawiać wrażenie, że przedstawiają obiektywną ocenę.

[3] Do tej pory każda obsługa obiektów o zmiennej długości odbywa się w oprogramowaniu, a nie w sprzęcie. Jest to najprawdopodobniej spowodowane

stopień powikłań nie został jeszcze opanowany,

przynajmniej dla proponowanych obiektów,

zysk rozwiązania sprzętowego jest zbyt mały w porównaniu z oprogramowaniem,

lub punkt sprzedaży jest zbyt niski.

[4] stopień powikłań nie został jeszcze opanowany,

[5] rzynajmniej dla proponowanych obiektów,

[6] zysk rozwiązania sprzętowego jest zbyt mały w porównaniu z oprogramowaniem,

[7] ub punkt sprzedaży jest zbyt niski.

[4] Źródło tak naprawdę nie rozwiązuje problemu: „Ale notacja cudzysłowu i notacja licznik-mianownik mogą się znacznie różnić.” i wzmianka, która wymaga 946 bitów w powtarzającej się grupie. Ale takich mianowników jest nieskończenie wiele, wszystkie mają stosunkowo dużą funkcję totientową , np. sol. z . W swoim trzecim „Dodatku dodanym później” dodają kilka uwag . ${\ displaystyle {\ mathcal {O}} (d)}$ ${\ displaystyle d = 947}$ ${\ displaystyle d = 802787}$ ${\ Displaystyle \ varphi (d) = 802786}$
${\ displaystyle d = 59}$

[9] stopień powikłań nie został jeszcze opanowany,

[10] rzynajmniej dla proponowanych obiektów,

[11] zysk rozwiązania sprzętowego jest zbyt mały w porównaniu z oprogramowaniem,

[12] ub punkt sprzedaży jest zbyt niski.

Languages

In other projects

Notacja cytatu - Quote notation

Zawartość

Reprezentacja

Wprowadzenie

Liczby naturalne

Ujemne liczby całkowite

Interpretacja notacji cudzysłowu

Algorytm konwersji

Określenie znaku

Arytmetyka

Dodanie

Odejmowanie

Mnożenie

Podział

Negacja

Porównanie z innymi reprezentacjami

Przestrzeń

Czas

Wady

Koszt

Zaokrąglanie przez obcięcie

Zero-dzielniki

Uwagi

Bibliografia