This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations .(August 2018) |
Part of a series on |
Numeral systems |
---|
List of numeral systems |
Golden ratio base is a non-integer positional numeral system that uses the golden ratio (the irrational number 1 + √5/2 ≈ 1.61803399 symbolized by the Greek letter φ) as its base. It is sometimes referred to as base-φ, golden mean base, phi-base, or, colloquially, phinary. Any non-negative real number can be represented as a base-φ numeral using only the digits 0 and 1, and avoiding the digit sequence "11" – this is called a standard form. A base-φ numeral that includes the digit sequence "11" can always be rewritten in standard form, using the algebraic properties of the base φ — most notably that φ1 + φ0 = φ2. For instance, 11φ = 100φ.
Despite using an irrational number base, when using standard form, all non-negative integers have a unique representation as a terminating (finite) base-φ expansion. The set of numbers which possess a finite base-φ representation is the ring Z[1 + √5/2]; it plays the same role in this numeral systems as dyadic rationals play in binary numbers, providing a possibility to multiply.
Other numbers have standard representations in base-φ, with rational numbers having recurring representations. These representations are unique, except that numbers with a terminating expansion also have a non-terminating expansion. For example, 1 = 0.1010101… in base-φ just as 1 = 0.99999… in base-10.
Decimal | Powers of φ | Base φ |
---|---|---|
1 | φ0 | 1 |
2 | φ1 + φ−2 | 10.01 |
3 | φ2 + φ−2 | 100.01 |
4 | φ2 + φ0 + φ−2 | 101.01 |
5 | φ3 + φ−1 + φ−4 | 1000.1001 |
6 | φ3 + φ1 + φ−4 | 1010.0001 |
7 | φ4 + φ−4 | 10000.0001 |
8 | φ4 + φ0 + φ−4 | 10001.0001 |
9 | φ4 + φ1 + φ−2 + φ−4 | 10010.0101 |
10 | φ4 + φ2 + φ−2 + φ−4 | 10100.0101 |
In the following example of conversion from non-standard to standard form, the notation 1 is used to represent the signed digit -1.
211.01φ is not a standard base-φ numeral, since it contains a "11" and additionally a "2" and a "1" = −1, which are not "0" or "1".
To put a numeral in standard form, we may use the following substitutions: , , , . The substitutions may be applied in any order we like, as the result will be the same. Below, the substitutions applied to the number on the previous line are on the right, the resulting number on the left.
Any positive number with a non-standard terminating base-φ representation can be uniquely standardized in this manner. If we get to a point where all digits are "0" or "1", except for the first digit being negative, then the number is negative. (The exception to this is when the first digit is negative one and the next two digits are one, like 1111.001=1.001.) This can be converted to the negative of a base-φ representation by negating every digit, standardizing the result, and then marking it as negative. For example, use a minus sign, or some other significance to denote negative numbers.
We can either consider our integer to be the (only) digit of a nonstandard base-φ numeral, and standardize it, or do the following:
1 × 1 = 1, φ × φ = 1 + φ and 1/φ = −1 + φ. Therefore, we can compute
and
So, using integer values only, we can add, subtract and multiply numbers of the form (a + bφ), and even represent positive and negative integer powers of φ.
(a + bφ) > (c + dφ) if and only if 2(a − c) − (d − b) > (d − b) × √5. If one side is negative, the other positive, the comparison is trivial. Otherwise, square both sides, to get an integer comparison, reversing the comparison direction if both sides were negative. On squaring both sides, the √5 is replaced with the integer 5.
So, using integer values only, we can also compare numbers of the form (a + bφ).
The above procedure will never result in the sequence "11", since 11φ = 100φ, so getting a "11" would mean we missed a "1" prior to the sequence "11".
Start, e.g., with integer = 5, with the result so far being ...00000.00000...φ
Highest power of φ ≤ 5 is φ3 = 1 + 2φ ≈ 4.236067977
Subtracting this from 5, we have 5 − (1 + 2φ) = 4 − 2φ ≈ 0.763932023..., the result so far being 1000.00000...φ
Highest power of φ ≤ 4 − 2φ ≈ 0.763932023... is φ−1 = −1 + 1φ ≈ 0.618033989...
Subtracting this from 4 − 2φ ≈ 0.763932023..., we have 4 − 2φ − (−1 + 1φ) = 5 − 3φ ≈ 0.145898034..., the result so far being 1000.10000...φ
Highest power of φ ≤ 5 − 3φ ≈ 0.145898034... is φ−4 = 5 − 3φ ≈ 0.145898034...
Subtracting this from 5 − 3φ ≈ 0.145898034..., we have 5 − 3φ − (5 − 3φ) = 0 + 0φ = 0, with the final result being 1000.1001φ.
Just as with any base-n system, numbers with a terminating representation have an alternative recurring representation. In base-10, this relies on the observation that 0.999...=1. In base-φ, the numeral 0.1010101... can be seen to be equal to 1 in several ways:
This non-uniqueness is a feature of the numeration system, since both 1.0000 and 0.101010... are in standard form.
In general, the final 1 of any number in base-φ can be replaced with a recurring 01 without changing the value of that number.
Every non-negative rational number can be represented as a recurring base-φ expansion, as can any non-negative element of the field Q[√5] = Q + √5Q, the field generated by the rational numbers and √5. Conversely any recurring (or terminating) base-φ expansion is a non-negative element of Q[√5]. For recurring decimals, the recurring part has been overlined:
The justification that a rational gives a recurring expansion is analogous to the equivalent proof for a base-n numeration system (n = 2,3,4,...). Essentially in base-φ long division there are only a finite number of possible remainders, and so once there must be a recurring pattern. For example, with 1/2 = 1/10.01φ = 100φ/1001φ long division looks like this (note that base-φ subtraction may be hard to follow at first):
.0 1 0 0 1 ________________________ 1 0 0 1 ) 1 0 0.0 0 0 0 0 0 0 0 1 0 0 1 trade: 10000 = 1100 = 1011 ------- so 10000 − 1001 = 1011 − 1001 = 10 1 0 0 0 0 1 0 0 1 ------- etc.
The converse is also true, in that a number with a recurring base-φ; representation is an element of the field Q[√5]. This follows from the observation that a recurring representation with period k involves a geometric series with ratio φ−k, which will sum to an element of Q[√5].
The base-φ representations of some interesting numbers:
It is possible to adapt all the standard algorithms of base-10 arithmetic to base-φ arithmetic. There are two approaches to this:
For addition of two base-φ numbers, add each pair of digits, without carry, and then convert the numeral to standard form. For subtraction, subtract each pair of digits without borrow (borrow is a negative amount of carry), and then convert the numeral to standard form. For multiplication, multiply in the typical base-10 manner, without carry, then convert the numeral to standard form.
For example,
A more "native" approach is to avoid having to add digits 1+1 or to subtract 0 – 1. This is done by reorganising the operands into nonstandard form so that these combinations do not occur. For example,
The subtraction seen here uses a modified form of the standard "trading" algorithm for subtraction.
No non-integer rational number can be represented as a finite base-φ number. In other words, all finitely representable base-φ numbers are either integers or (more likely) an irrational in a quadratic field Q[√5]. Due to long division having only a finite number of possible remainders, a division of two integers (or other numbers with finite base-φ representation) will have a recurring expansion, as demonstrated above.
Fibonacci coding is a closely related numeration system used for integers. In this system, only digits 0 and 1 are used and the place values of the digits are the Fibonacci numbers. As with base-φ, the digit sequence "11" is avoided by rearranging to a standard form, using the Fibonacci recurrence relation Fk+1 = Fk + Fk−1. For example,
It is possible to mix base-φ arithmetic with Fibonacci integer sequences. The sum of numbers in a General Fibonacci integer sequence that correspond with the nonzero digits in the base-φ number, is the multiplication of the base-φ number and the element at the zero-position in the sequence. For example:
In computing and electronic systems, binary-coded decimal (BCD) is a class of binary encodings of decimal numbers where each digit is represented by a fixed number of bits, usually four or eight. Sometimes, special bit patterns are used for a sign or other indications.
The decimal numeral system is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers of the Hindu–Arabic numeral system. The way of denoting numbers in the decimal system is often referred to as decimal notation.
The duodecimal system is a positional notation numeral system using twelve as its base. The number twelve is instead written as "10" in duodecimal, whereas the digit string "12" means "1 dozen and 2 units". Similarly, in duodecimal, "100" means "1 gross", "1000" means "1 great gross", and "0.1" means "1 twelfth".
A numeral system is a writing system for expressing numbers; that is, a mathematical notation for representing numbers of a given set, using digits or other symbols in a consistent manner.
A number is a mathematical object used to count, measure, and label. The original examples are the natural numbers 1, 2, 3, 4, and so forth. Numbers can be represented in language with number words. More universally, individual numbers can be represented by symbols, called numerals; for example, "5" is a numeral that represents the number five. As only a relatively small number of symbols can be memorized, basic numerals are commonly organized in a numeral system, which is an organized way to represent any number. The most common numeral system is the Hindu–Arabic numeral system, which allows for the representation of any number using a combination of ten fundamental numeric symbols, called digits. In addition to their use in counting and measuring, numerals are often used for labels, for ordering, and for codes. In common usage, a numeral is not clearly distinguished from the number that it represents.
A palindromic number is a number that remains the same when its digits are reversed. In other words, it has reflectional symmetry across a vertical axis. The term palindromic is derived from palindrome, which refers to a word whose spelling is unchanged when its letters are reversed. The first 30 palindromic numbers are:
222 is the natural number following 221 and preceding 223.
A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" (zero) and "1" (one).
The quater-imaginary numeral system is a numeral system, first proposed by Donald Knuth in 1960. Unlike standard numeral systems, which use an integer as their bases, it uses the imaginary number 2i as its base. It is able to (almost) uniquely represent every complex number using only the digits 0, 1, 2, and 3. Numbers less than zero, which are ordinarily represented with a minus sign, are representable as digit strings in quater-imaginary; for example, the number −1 is represented as "103" in quater-imaginary notation.
Two's complement is the most common method of representing signed integers on computers,and more generally, fixed point binary values. Two's complement uses the binary digit with the greatest place value as the sign to indicate whether the binary number is positive or negative. When the most significant bit is 1, the number is signed as negative; and when the most significant bit is 0 the number is signed as positive.
A power of two is a number of the form 2n where n is an integer, that is, the result of exponentiation with number two as the base and integer n as the exponent.
666 is the natural number following 665 and preceding 667.
In a positional numeral system, the radix or base is the number of unique digits, including the digit zero, used to represent numbers. For example, for the decimal system the radix is ten, because it uses the ten digits from 0 through 9.
Bijective numeration is any numeral system in which every non-negative integer can be represented in exactly one way using a finite string of digits. The name refers to the bijection that exists in this case between the set of non-negative integers and the set of finite strings using a finite set of symbols.
Non-standard positional numeral systems here designates numeral systems that may loosely be described as positional systems, but that do not entirely comply with the following description of standard positional systems:
In computer science, the double dabble algorithm is used to convert binary numbers into binary-coded decimal (BCD) notation. It is also known as the shift-and-add-3 algorithm, and can be implemented using a small number of gates in computer hardware, but at the expense of high latency.
A non-integer representation uses non-integer numbers as the radix, or base, of a positional numeral system. For a non-integer radix β > 1, the value of
Single-precision floating-point format is a computer number format, usually occupying 32 bits in computer memory; it represents a wide dynamic range of numeric values by using a floating radix point.
The ones' complement of a binary number is the value obtained by inverting (flipping) all the bits in the binary representation of the number. The name "ones' complement" refers to the fact that such an inverted value, if added to the original, would always produce an "all ones" number. This mathematical operation is primarily of interest in computer science, where it has varying effects depending on how a specific computer represents numbers.