Quote notation
Encyclopedia
Quote notation is a representation of rational number
s for which the addition, subtraction, and multiplication algorithms are the same as for natural number
s, and division is easier than the usual division algorithm, and works in the same right-to-left direction as the other arithmetic algorithms. Arithmetic in quote notation produces exact answers, with no roundoff error. It was invented by Eric Hehner
of the University of Toronto
, and published in the SIAM
Journal on Computation
, v.8, n.2, May 1979, pp. 124–134. It is related to Kurt Hensel
's p-adic number
s.
s with a quote mark and radix point
. For example, 12'3.4 is in quote notation. The radix point may come before the quote mark, as in 12.3'4 , or at the same place, as in 12!3 .
The radix point (in base ten it is called a decimal
point) has its usual function; moving it left divides by the base; moving it right multiplies by the base. When the radix point is at the right end, the multiplicative factor is 1, and the point can be omitted. Scientific notation
may be used as an alternative to the radix point.
We can think of the quote mark as saying that the digits to its left are repeated indefinitely to the left. For example, we can think of 12'34 as the infinite sequence ...1212121234 . If the repeated sequence is 0s, it and the quote mark can be omitted.
The natural number
s look as usual: 0, 1, 2, ... , or, including quote and point, 0!, 0'1., 0'2., ... . The negative integer
s begin with the digit one less than the base. For example, in decimal, minus three is 9'7 . Numbers beginning with any other repeating sequence are not integers. For example, in decimal, 6'7 is the fraction one-third, and 7'6 is minus one and seven-ninths.
Let
and 
be sequences of digits. Let 
be a sequence of zeros of the same length as 
. Let 
be the largest digit (one less than the base). Let 
be a sequence of 
s of the same length as 
. Then the number represented by 
is 
. For example, 12'345 = 345 − 12000/99 = 7385/33.
In quote notation, to add, just add. There are no sign or magnitude comparisons, and no common denominators. Addition is the same as for natural numbers. Here are some examples.
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
In quote notation, to subtract, just subtract. There are no sign or magnitude comparisons, and no common denominators. When a minuend
digit is less than the corresponding subtrahend
digit, do not borrow from the minuend digit to its left; instead, carry (add one) to the subtrahend digit to its left. Here are some examples.
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
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
To someone who is unfamiliar with quote notation, 592' is unfamiliar, and translation to −16/27 is helpful. To someone who normally uses quote notation, −16/27 is a formula with a negation and a division operation; performing those operations yields the answer 592' .
. The commonly used division algorithm also produces duplicate representations; for example, 0.499999... and 0.5 represent the same number. In decimal, there is a kind of guess for each digit, which is seen to be right or wrong as the calculation progresses.
In quote notation, division produces digits from right-to-left, the same as all other arithmetic algorithms; therefore further arithmetic is easy. Quote arithmetic is exact, with no error. Each rational number has a unique representation (if the repetition is expressed as simply as possible, and we have no meaningless 0s at the right end after a radix point). Each digit is determined by a "division table", which is the inverse of part of the multiplication table
; there is no "guessing". Here is an example.
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
Division works when the divisor
and the base have no factors in common except 1. In the previous example, 27 has factors 1, 3, and 27. The base is 10, which has factors 1, 2, 5, and 10. So division worked. When there are factors in common, they must be removed. For example, to divide 4 by 15, first multiply both 4 and 15 by 2:
4/15 = 8/30
Any 0s at the end of the divisor just tell where the radix point goes in the result. So now divide 8 by 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
Removing common factors is annoying, and it is unnecessary if the base is a prime number
. Computers use base 2, which is a prime number, so division always works. And the division tables are trivial. The only questions are: what times 1 ends in 0? and: what times 1 ends in 1. Thus the rightmost bit
s in the differences are the bits in the answer. For example, one divided by three, which is 1/11 , proceeds as follows.
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
If the quote comes at the end, just append a zero after the radix point. For example, 592' = 592!0 , which is negative because 5 is more than 0. And 59.2' = 59.2'0 which is negative.
If the leading digit equals the first digit after the quote, then either the number is 0!0 = 0, or the representation can be shortened by rolling the repetition to the right. For example, 23'25 = 32'5 which is positive because 3 is less than 5.
In binary, if it starts with 1 it is negative, and if it starts with 0 it is nonnegative, assuming the repetition has been rolled to the right as far as possible.
). For example, to negate 01'1, which is one-third, flip the bits to get 10'0, then add 1 to get 10'1, and roll right to shorten it to 01' which is minus one-third.
Rational number
In mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...
s for which the addition, subtraction, and multiplication algorithms are the same as for natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s, and division is easier than the usual division algorithm, and works in the same right-to-left direction as the other arithmetic algorithms. Arithmetic in quote notation produces exact answers, with no roundoff error. It was invented by Eric Hehner
Eric Hehner
Eric C. R. Hehner, called Rick, is a Canadian computer scientist.Eric Hehner was born on 16 September 1947 in Ottawa. He studied mathematics and physics at Carleton University, obtaining his first degree in 1969. He gained a PhD in computer science from the University of Toronto in 1974. He then...
of the University of Toronto
University of Toronto
The University of Toronto is a public research university in Toronto, Ontario, Canada, situated on the grounds that surround Queen's Park. It was founded by royal charter in 1827 as King's College, the first institution of higher learning in Upper Canada...
, and published in the SIAM
Society for Industrial and Applied Mathematics
The Society for Industrial and Applied Mathematics was founded by a small group of mathematicians from academia and industry who met in Philadelphia in 1951 to start an organization whose members would meet periodically to exchange ideas about the uses of mathematics in industry. This meeting led...
Journal on Computation
SIAM Journal on Computing
The SIAM Journal on Computing is a scientific journal focusing on the mathematical and formal aspects of computer science. It is published by the Society for Industrial and Applied Mathematics . As of September 2008, Éva Tardos serves as editor-in-chief.-External links:** on DBLP...
, v.8, n.2, May 1979, pp. 124–134. It is related to Kurt Hensel
Kurt Hensel
Kurt Wilhelm Sebastian Hensel was a German mathematician born in Königsberg, Prussia.He was the son of the landowner and entrepreneur Sebastian Hensel, brother of the philosopher Paul Hensel, grandson of the composer Fanny Mendelssohn and the painter Wilhelm Hensel, and a descendant of the...
's p-adic number
P-adic number
In mathematics, and chiefly number theory, the p-adic number system for any prime number p extends the ordinary arithmetic of the rational numbers in a way different from the extension of the rational number system to the real and complex number systems...
s.
Representation
A rational number is represented as a sequence of digitNumerical digit
A digit is a symbol used in combinations to represent numbers in positional numeral systems. The name "digit" comes from the fact that the 10 digits of the hands correspond to the 10 symbols of the common base 10 number system, i.e...
s with a quote mark and radix point
Radix point
In mathematics and computing, a radix point is the symbol used in numerical representations to separate the integer part of a number from its fractional part . "Radix point" is a general term that applies to all number bases...
. For example, 12'3.4 is in quote notation. The radix point may come before the quote mark, as in 12.3'4 , or at the same place, as in 12!3 .
The radix point (in base ten it is called a decimal
Decimal
The decimal numeral system has ten as its base. It is the numerical base most widely used by modern civilizations....
point) has its usual function; moving it left divides by the base; moving it right multiplies by the base. When the radix point is at the right end, the multiplicative factor is 1, and the point can be omitted. Scientific notation
Scientific notation
Scientific notation is a way of writing numbers that are too large or too small to be conveniently written in standard decimal notation. Scientific notation has a number of useful properties and is commonly used in calculators and by scientists, mathematicians, doctors, and engineers.In scientific...
may be used as an alternative to the radix point.
We can think of the quote mark as saying that the digits to its left are repeated indefinitely to the left. For example, we can think of 12'34 as the infinite sequence ...1212121234 . If the repeated sequence is 0s, it and the quote mark can be omitted.
The natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s look as usual: 0, 1, 2, ... , or, including quote and point, 0!, 0'1., 0'2., ... . The negative integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s begin with the digit one less than the base. For example, in decimal, minus three is 9'7 . Numbers beginning with any other repeating sequence are not integers. For example, in decimal, 6'7 is the fraction one-third, and 7'6 is minus one and seven-ninths.
Let
and be sequences of digits. Let be a sequence of zeros of the same length as . Let be the largest digit (one less than the base). Let be a sequence of s of the same length as . Then the number represented by is . For example, 12'345 = 345 − 12000/99 = 7385/33.Addition
In our usual sign-and-magnitude notation, to add the two integers 25 and −37, one first compares signs, and determines that the addition will be performed by subtracting the magnitudes. Then one compares the magnitudes to determine which will be subtracted from which, and to determine the sign of the result. In our usual fraction notation, to add 2/3 + 4/5 requires finding a common denominator, multiplying each numerator by the new factors in this common denominator, then adding the numerators, then dividing the numerator and denominator by any factors they have in common.In quote notation, to add, just add. There are no sign or magnitude comparisons, and no common denominators. Addition is the same as for natural numbers. Here are some examples.
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
Subtraction
In our usual sign-and-magnitude notation, subtraction involves sign comparison and magnitude comparison, and may require adding or subtracting the magnitudes, just like addition. In our usual fraction notation, subtraction requires finding a common denominator, multiplying, subtracting, and reducing to lowest terms, just like addition.In quote notation, to subtract, just subtract. There are no sign or magnitude comparisons, and no common denominators. When a minuend
Subtraction
In arithmetic, subtraction is one of the four basic binary operations; it is the inverse of addition, meaning that if we start with any number and add any number and then subtract the same number we added, we return to the number we started with...
digit is less than the corresponding subtrahend
Subtraction
In arithmetic, subtraction is one of the four basic binary operations; it is the inverse of addition, meaning that if we start with any number and add any number and then subtract the same number we added, we return to the number we started with...
digit, do not borrow from the minuend digit to its left; instead, carry (add one) to the subtrahend digit to its left. Here are some examples.
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
Multiplication
Multiplication is the same as for natural numbers. To recognize the repetition in the answer, it helps to add the partial results pairwise. Here are some examples.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
To someone who is unfamiliar with quote notation, 592' is unfamiliar, and translation to −16/27 is helpful. To someone who normally uses quote notation, −16/27 is a formula with a negation and a division operation; performing those operations yields the answer 592' .
Division
The commonly used division algorithm produces digits from left-to-right, which is opposite to addition, subtraction, and multiplication. This makes further arithmetic difficult. For example, how do we add 1.234234234234... + 5.67676767... ? Usually we use a finite number of digits and accept an approximate answer with roundoff errorRound-off error
A round-off error, also called rounding error, is the difference between the calculated approximation of a number and its exact mathematical value. Numerical analysis specifically tries to estimate this error when using approximation equations and/or algorithms, especially when using finitely many...
. The commonly used division algorithm also produces duplicate representations; for example, 0.499999... and 0.5 represent the same number. In decimal, there is a kind of guess for each digit, which is seen to be right or wrong as the calculation progresses.
In quote notation, division produces digits from right-to-left, the same as all other arithmetic algorithms; therefore further arithmetic is easy. Quote arithmetic is exact, with no error. Each rational number has a unique representation (if the repetition is expressed as simply as possible, and we have no meaningless 0s at the right end after a radix point). Each digit is determined by a "division table", which is the inverse of part of the multiplication table
Multiplication table
In mathematics, a multiplication table is a mathematical table used to define a multiplication operation for an algebraic system....
; there is no "guessing". Here is an example.
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
Division works when the divisor
Divisor
In mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...
and the base have no factors in common except 1. In the previous example, 27 has factors 1, 3, and 27. The base is 10, which has factors 1, 2, 5, and 10. So division worked. When there are factors in common, they must be removed. For example, to divide 4 by 15, first multiply both 4 and 15 by 2:
4/15 = 8/30
Any 0s at the end of the divisor just tell where the radix point goes in the result. So now divide 8 by 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
Removing common factors is annoying, and it is unnecessary if the base is a prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
. Computers use base 2, which is a prime number, so division always works. And the division tables are trivial. The only questions are: what times 1 ends in 0? and: what times 1 ends in 1. Thus the rightmost bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
s in the differences are the bits in the answer. For example, one divided by three, which is 1/11 , proceeds as follows.
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
Sign determination
If the leading digit is less than the first digit after the quote, the number is positive. For example, 123'45 is positive because 1 is less than 4. If the leading digit is more than the first digit after the quote, the number is negative. For example, 54'3 is negative because 5 is more than 3 .If the quote comes at the end, just append a zero after the radix point. For example, 592' = 592!0 , which is negative because 5 is more than 0. And 59.2' = 59.2'0 which is negative.
If the leading digit equals the first digit after the quote, then either the number is 0!0 = 0, or the representation can be shortened by rolling the repetition to the right. For example, 23'25 = 32'5 which is positive because 3 is less than 5.
In binary, if it starts with 1 it is negative, and if it starts with 0 it is nonnegative, assuming the repetition has been rolled to the right as far as possible.
Negation
To negate, complement each digit, and then add 1. For example, in decimal, to negate 12'345, complement and get 87'654, and then add 1 to get 87'655. In binary, flip the bits, then add 1 (same as 2's complementTwo's complement
The two's complement of a binary number is defined as the value obtained by subtracting the number from a large power of two...
). For example, to negate 01'1, which is one-third, flip the bits to get 10'0, then add 1 to get 10'1, and roll right to shorten it to 01' which is minus one-third.
External links
- "A new representation of the rational numbers for fast easy arithmetic", E.C.R. Hehner and R.N.S. Horspool