fbpx
Wikipedia

Dyadic rational

In mathematics, a dyadic rational or binary rational is a number that can be expressed as a fraction whose denominator is a power of two. For example, 1/2, 3/2, and 3/8 are dyadic rationals, but 1/3 is not. These numbers are important in computer science because they are the only ones with finite binary representations. Dyadic rationals also have applications in weights and measures, musical time signatures, and early mathematics education. They can accurately approximate any real number.

Dyadic rationals in the interval from 0 to 1

The sum, difference, or product of any two dyadic rational numbers is another dyadic rational number, given by a simple formula. However, division of one dyadic rational number by another does not always produce a dyadic rational result. Mathematically, this means that the dyadic rational numbers form a ring, lying between the ring of integers and the field of rational numbers. This ring may be denoted .

In advanced mathematics, the dyadic rational numbers are central to the constructions of the dyadic solenoid, Minkowski's question-mark function, Daubechies wavelets, Thompson's group, Prüfer 2-group, surreal numbers, and fusible numbers. These numbers are order-isomorphic to the rational numbers; they form a subsystem of the 2-adic numbers as well as of the reals, and can represent the fractional parts of 2-adic numbers. Functions from natural numbers to dyadic rationals have been used to formalize mathematical analysis in reverse mathematics.

Applications

In measurement

 
Kitchen weights measuring dyadic fractions of a pound from 2 lb down to 1/64 lb (1/4 oz)

Many traditional systems of weights and measures are based on the idea of repeated halving, which produces dyadic rationals when measuring fractional amounts of units. The inch is customarily subdivided in dyadic rationals rather than using a decimal subdivision.[1] The customary divisions of the gallon into half-gallons, quarts, pints, and cups are also dyadic.[2] The ancient Egyptians used dyadic rationals in measurement, with denominators up to 64.[3] Similarly, systems of weights from the Indus Valley civilisation are for the most part based on repeated halving; anthropologist Heather M.-L. Miller writes that "halving is a relatively simple operation with beam balances, which is likely why so many weight systems of this time period used binary systems".[4]

In computing

Dyadic rationals are central to computer science as a type of fractional number that many computers can manipulate directly.[5] In particular, as a data type used by computers, floating-point numbers are often defined as integers multiplied by positive or negative powers of two. The numbers that can be represented precisely in a floating-point format, such as the IEEE floating-point datatypes, are called its representable numbers. For most floating-point representations, the representable numbers are a subset of the dyadic rationals.[6] The same is true for fixed-point datatypes, which also use powers of two implicitly in the majority of cases.[7] Because of the simplicity of computing with dyadic rationals, they are also used for exact real computing using interval arithmetic,[8] and are central to some theoretical models of computable numbers.[9][10][11]

Generating a random variable from random bits, in a fixed amount of time, is possible only when the variable has finitely many outcomes whose probabilities are all dyadic rational numbers. For random variables whose probabilities are not dyadic, it is necessary either to approximate their probabilities by dyadic rationals, or to use a random generation process whose time is itself random and unbounded.[12]

In music

 
Five bars from Igor Stravinski's The Rite of Spring
showing time signatures 3
16
, 2
16
, 3
16
, and 2
8

Time signatures in Western musical notation traditionally are written in a form resembling fractions (for example: 2
2
, 4
4
, or 6
8
),[13] although the horizontal line of the musical staff that separates the top and bottom number is usually omitted when writing the signature separately from its staff. As fractions they are generally dyadic,[14] although non-dyadic time signatures have also been used.[15] The numeric value of the signature, interpreted as a fraction, describes the length of a measure as a fraction of a whole note. Its numerator describes the number of beats per measure, and the denominator describes the length of each beat.[13][14]

In mathematics education

In theories of childhood development of the concept of a fraction based on the work of Jean Piaget, fractional numbers arising from halving and repeated halving are among the earliest forms of fractions to develop.[16] This stage of development of the concept of fractions has been called "algorithmic halving".[17] Addition and subtraction of these numbers can be performed in steps that only involve doubling, halving, adding, and subtracting integers. In contrast, addition and subtraction of more general fractions involves integer multiplication and factorization to reach a common denominator. Therefore, dyadic fractions can be easier for students to calculate with than more general fractions.[18]

Definitions and arithmetic

The dyadic numbers are the rational numbers that result from dividing an integer by a power of two.[9] A rational number   in simplest terms is a dyadic rational when   is a power of two.[19] Another equivalent way of defining the dyadic rationals is that they are the real numbers that have a terminating binary representation.[9]

Addition, subtraction, and multiplication of any two dyadic rationals produces another dyadic rational, according to the following formulas:[20]

 

However, the result of dividing one dyadic rational by another is not necessarily a dyadic rational.[21] For instance, 1 and 3 are both dyadic rational numbers, but 1/3 is not.

Additional properties

 
Dyadic rational approximations to the square root of 2 ( ), found by rounding to the nearest smaller integer multiple of   for   The height of the pink region above each approximation is its error.
 
Real numbers with no unusually-accurate dyadic rational approximations. The red circles surround numbers that are approximated within error   by  . For numbers in the fractal Cantor set outside the circles, all dyadic rational approximations have larger errors.

Every integer, and every half-integer, is a dyadic rational.[22] They both meet the definition of being an integer divided by a power of two: every integer is an integer divided by one (the zeroth power of two), and every half-integer is an integer divided by two.

Every real number can be arbitrarily closely approximated by dyadic rationals. In particular, for a real number  , consider the dyadic rationals of the form  , where   can be any integer and   denotes the floor function that rounds its argument down to an integer. These numbers approximate   from below to within an error of  , which can be made arbitrarily small by choosing   to be arbitrarily large. For a fractal subset of the real numbers, this error bound is within a constant factor of optimal: for these numbers, there is no approximation   with error smaller than a constant times  .[23][24] The existence of accurate dyadic approximations can be expressed by saying that the set of all dyadic rationals is dense in the real line.[22] More strongly, this set is uniformly dense, in the sense that the dyadic rationals with denominator   are uniformly spaced on the real line.[9]

The dyadic rationals are precisely those numbers possessing finite binary expansions.[9] Their binary expansions are not unique; there is one finite and one infinite representation of each dyadic rational other than 0 (ignoring terminal 0s). For example, 0.112 = 0.10111...2, giving two different representations for 3/4.[9][25] The dyadic rationals are the only numbers whose binary expansions are not unique.[9]

In advanced mathematics

Algebraic structure

Because they are closed under addition, subtraction, and multiplication, but not division, the dyadic rationals are a ring but not a field.[26] The ring of dyadic rationals may be denoted  , meaning that it can be generated by evaluating polynomials with integer coefficients, at the argument 1/2.[27] As a ring, the dyadic rationals are a subring of the rational numbers, and an overring of the integers.[28] Algebraically, this ring is the localization of the integers with respect to the set of powers of two.[29]

As well as forming a subring of the real numbers, the dyadic rational numbers form a subring of the 2-adic numbers, a system of numbers that can be defined from binary representations that are finite to the right of the binary point but may extend infinitely far to the left. The 2-adic numbers include all rational numbers, not just the dyadic rationals. Embedding the dyadic rationals into the 2-adic numbers does not change the arithmetic of the dyadic rationals, but it gives them a different topological structure than they have as a subring of the real numbers. As they do in the reals, the dyadic rationals form a dense subset of the 2-adic numbers,[30] and are the set of 2-adic numbers with finite binary expansions. Every 2-adic number can be decomposed into the sum of a 2-adic integer and a dyadic rational; in this sense, the dyadic rationals can represent the fractional parts of 2-adic numbers, but this decomposition is not unique.[31]

Addition of dyadic rationals modulo 1 (the quotient group   of the dyadic rationals by the integers) forms the Prüfer 2-group.[32]

Dyadic solenoid

Considering only the addition and subtraction operations of the dyadic rationals gives them the structure of an additive abelian group. Pontryagin duality is a method for understanding abelian groups by constructing dual groups, whose elements are characters of the original group, group homomorphisms to the multiplicative group of the complex numbers, with pointwise multiplication as the dual group operation. The dual group of the additive dyadic rationals, constructed in this way, can also be viewed as a topological group. It is called the dyadic solenoid, and is isomorphic to the topological product of the real numbers and 2-adic numbers, quotiented by the diagonal embedding of the dyadic rationals into this product.[30] It is an example of a protorus, a solenoid, and an indecomposable continuum.[33]

Functions with dyadic rationals as distinguished points

 
Minkowski's question-mark function maps rational numbers to dyadic rationals
 
A Daubechies wavelet, showing points of non-smoothness at dyadic rationals

Because they are a dense subset of the real numbers, the dyadic rationals, with their numeric ordering, form a dense order. As with any two unbounded countable dense linear orders, by Cantor's isomorphism theorem,[34] the dyadic rationals are order-isomorphic to the rational numbers. In this case, Minkowski's question-mark function provides an order-preserving bijection between the set of all rational numbers and the set of dyadic rationals.[35]

The dyadic rationals play a key role in the analysis of Daubechies wavelets, as the set of points where the scaling function of these wavelets is non-smooth.[26] Similarly, the dyadic rationals parameterize the discontinuities in the boundary between stable and unstable points in the parameter space of the Hénon map.[36]

The set of piecewise linear homeomorphisms from the unit interval to itself that have power-of-2 slopes and dyadic-rational breakpoints forms a group under the operation of function composition. This is Thompson's group, the first known example of an infinite but finitely presented simple group.[37] The same group can also be represented by an action on rooted binary trees,[38] or by an action on the dyadic rationals within the unit interval.[32]

Other related constructions

In reverse mathematics, one way of constructing the real numbers is to represent them as functions from unary numbers to dyadic rationals, where the value of one of these functions for the argument   is a dyadic rational with denominator   that approximates the given real number. Defining real numbers in this way allows many of the basic results of mathematical analysis to be proven within a restricted theory of second-order arithmetic called "feasible analysis" (BTFA).[39]

The surreal numbers are generated by an iterated construction principle which starts by generating all finite dyadic rationals, and then goes on to create new and strange kinds of infinite, infinitesimal and other numbers.[40] This number system is foundational to combinatorial game theory, and dyadic rationals arise naturally in this theory as the set of values of certain combinatorial games.[41][42][19]

The fusible numbers are a subset of the dyadic rationals, the closure of the set   under the operation  , restricted to pairs   with  . They are well-ordered, with order type equal to the epsilon number  . For each integer   the smallest fusible number that is greater than   has the form  . The existence of   for each   cannot be proven in Peano arithmetic,[43] and   grows so rapidly as a function of   that for   it is (in Knuth's up-arrow notation for large numbers) already larger than  .[44]

The usual proof of Urysohn's lemma utilizes the dyadic fractions for constructing the separating function from the lemma.

References

  1. ^ Rudman, Peter S. (2009), How Mathematics Happened: The First 50,000 Years, Prometheus Books, p. 148, ISBN 978-1-61592-176-8
  2. ^ Barnes, John (2016), Nice Numbers, Springer International Publishing, doi:10.1007/978-3-319-46831-0, ISBN 978-3-319-46830-3, Note that binary measures (2, 4, 8, 16) are very common indeed. This is particularly obvious with volumes.
  3. ^ Curtis, Lorenzo J. (1978), "Concept of the exponential law prior to 1900", American Journal of Physics, 46 (9): 896–906, Bibcode:1978AmJPh..46..896C, doi:10.1119/1.11512
  4. ^ Miller, Heather M.-L. (2013), "Weighty matters: evidence for unity and regional diversity from the Indus civilization weights", in Abraham, Shinu Anna; Gullapalli, Praveena; Raczek, Teresa P.; Rizvi, Uzma Z. (eds.), Connections and Complexity: New Approaches to the Archaeology of South Asia, Left Coast Press, pp. 161–177, doi:10.4324/9781315431857, ISBN 978-1-59874-686-0; see in particular p. 166
  5. ^ Resnikoff, Howard L.; Wells, Raymond O. Jr. (1998), "2.2.1: Digital computers and measurement", Wavelet Analysis: The Scalable Structure of Information, New York: Springer-Verlag, pp. 17–18, doi:10.1007/978-1-4612-0593-7, ISBN 0-387-98383-X, MR 1712468
  6. ^ Kirk, David B.; Hwu, Wen-mei W. (2013), "7.2 Representable numbers", Programming Massively Parallel Processors: A Hands-on Approach (2nd ed.), Morgan Kaufmann, pp. 155–159, ISBN 978-0-12-391418-7
  7. ^ Kneusel, Ronald T. (2017), "Chapter 6: Fixed-point numbers", Numbers and Computers (2nd ed.), Springer International Publishing, pp. 183–214, doi:10.1007/978-3-319-50508-4_6
  8. ^ van der Hoeven, Joris (2006), "Computations with effective real numbers", Theoretical Computer Science, 351 (1): 52–60, doi:10.1016/j.tcs.2005.09.060, MR 2201092
  9. ^ a b c d e f g Ko, Ker-I (1991), Complexity Theory of Real Functions, Progress in Theoretical Computer Science, Boston, Massachusetts: Birkhäuser Boston, Inc., pp. 41–43, doi:10.1007/978-1-4684-6802-1, ISBN 0-8176-3586-6, MR 1137517, S2CID 11758381
  10. ^ Zheng, Xizhong; Rettinger, Robert (2004), "Weak computability and representation of reals", Mathematical Logic Quarterly, 50 (4–5): 431–442, doi:10.1002/malq.200310110, MR 2090389, S2CID 15815720
  11. ^ Ambos-Spies, Klaus; Zheng, Xizhong (2019), "On the differences and sums of strongly computably enumerable real numbers", in Manea, Florin; Martin, Barnaby; Paulusma, Daniël; Primiero, Giuseppe (eds.), Computing with Foresight and Industry: 15th Conference on Computability in Europe, CiE 2019, Durham, UK, July 15–19, 2019, Proceedings, Lecture Notes in Computer Science, vol. 11558, Cham: Springer, pp. 310–322, doi:10.1007/978-3-030-22996-2_27, MR 3981892, S2CID 195795492
  12. ^ Jerrum, Mark R.; Valiant, Leslie G.; Vazirani, Vijay V. (1986), "Random generation of combinatorial structures from a uniform distribution", Theoretical Computer Science, 43 (2–3): 169–188, doi:10.1016/0304-3975(86)90174-X, MR 0855970
  13. ^ a b Jones, Shelly M.; Pearson, Dunn (May 2013), "Music: highly engaged students connect music to math", General Music Today, 27 (1): 18–23, doi:10.1177/1048371313486478, S2CID 220604326
  14. ^ a b Libbey, Theodore (2006), "Time signature", The NPR Listener's Encyclopedia of Classical Music, Workman Publishing, p. 873, ISBN 978-0-7611-2072-8
  15. ^ Yanakiev, Ivan K. (2020), "Mathematical devices in aid of music theory, composition, and performance", in Bozhikova, Milena (ed.), Music between Ontology and Ideology, Cambridge Scholars Publishing, pp. 35–62, ISBN 978-1-5275-4758-2; see in particular p. 37.
  16. ^ Hiebert, James; Tonnessen, Lowell H. (November 1978), "Development of the fraction concept in two physical contexts: an exploratory investigation", Journal for Research in Mathematics Education, 9 (5): 374–378, doi:10.2307/748774, JSTOR 748774
  17. ^ Pothier, Yvonne; Sawada, Daiyo (November 1983), "Partitioning: the emergence of rational number ideas in young children", Journal for Research in Mathematics Education, 14 (5): 307–317, doi:10.2307/748675, JSTOR 748675
  18. ^ Wells, David Graham (2015), Motivating Mathematics: Engaging Teachers And Engaged Students, World Scientific, pp. 32–33, ISBN 978-1-78326-755-2
  19. ^ a b Uiterwijk, Jos W. H. M.; Barton, Michael (2015), "New results for Domineering from combinatorial game theory endgame databases", Theoretical Computer Science, 592: 72–86, arXiv:1506.03949, doi:10.1016/j.tcs.2015.05.017, MR 3367582, S2CID 5899577
  20. ^ Equivalent formulas to these, written in the language of the Coq interactive theorem prover, are given by Krebbers, Robbert; Spitters, Bas (2013), "Type classes for efficient exact real arithmetic in Coq", Logical Methods in Computer Science, 9 (1): 1:01, 27, arXiv:1106.3448, doi:10.2168/LMCS-9(1:1)2013, MR 3029087, S2CID 218627153
  21. ^ O'Connor, Russell (2007), "A monadic, functional implementation of real numbers", Mathematical Structures in Computer Science, 17 (1): 129–159, doi:10.1017/S0960129506005871, MR 2311089, S2CID 221168970
  22. ^ a b Sabin, Malcolm (2010), Analysis and Design of Univariate Subdivision Schemes, Geometry and Computing, vol. 6, Springer, p. 51, ISBN 9783642136481
  23. ^ More precisely, for small positive values of  , the set of real numbers that have no approximation   with error smaller than a constant times   forms a Cantor set whose Hausdorff dimension, as a function of  , goes to one as   approaches zero. The illustration shows this set for  .
  24. ^ Nilsson, Johan (2009), "On numbers badly approximable by dyadic rationals", Israel Journal of Mathematics, 171: 93–110, doi:10.1007/s11856-009-0042-9, MR 2520103
  25. ^ Kac, Mark (1959), Statistical Independence in Probability, Analysis and Number Theory, Carus Mathematical Monographs, vol. 12, New York: John Wiley & Sons for the Mathematical Association of America, pp. 2–3, MR 0110114
  26. ^ a b Pollen, David (1992), "Daubechies' scaling function on [0,3]", Wavelets, Wavelet Analysis and Its Applications, vol. 2, Boston, Massachusetts: Academic Press, pp. 3–13, MR 1161245
  27. ^ Bajnok, Béla (2013), An Invitation to Abstract Mathematics, Undergraduate Texts in Mathematics, New York: Springer, p. 186, doi:10.1007/978-1-4614-6636-9, ISBN 978-1-4614-6635-2
  28. ^ In the notation of Estes and Ohm for rings that are both subrings of   and overrings of  , the dyadic rationals are the ring  . See section 7 of Estes, Dennis; Ohm, Jack (1967), "Stable range in commutative rings" (PDF), Journal of Algebra, 7 (3): 343–362, doi:10.1016/0021-8693(67)90075-0, MR 0217052
  29. ^ Lucyshyn-Wright, Rory B. B. (2018), "Convex spaces, affine spaces, and commutants for algebraic theories", Applied Categorical Structures, 26 (2): 369–400, arXiv:1603.03351, doi:10.1007/s10485-017-9496-9, MR 3770912, S2CID 3743682
  30. ^ a b Manners, Freddie (2015), "A solution to the pyjama problem", Inventiones Mathematicae, 202 (1): 239–270, arXiv:1305.1514, Bibcode:2015InMat.202..239M, doi:10.1007/s00222-014-0571-7, MR 3402799, S2CID 119148680; see section 6.2.1, "A model case:  ", pp. 255–257.
  31. ^ Robert, Alain M. (2000), "5.4 Fractional and integral parts of  -adic numbers", A Course in  -adic Analysis, Graduate Texts in Mathematics, vol. 198, New York: Springer-Verlag, pp. 40–43, doi:10.1007/978-1-4757-3254-2, ISBN 0-387-98669-3, MR 1760253
  32. ^ a b de Cornulier, Yves; Guyot, Luc; Pitsch, Wolfgang (2007), "On the isolated points in the space of groups" (PDF), Journal of Algebra, 307 (1): 254–277, arXiv:math/0511714, doi:10.1016/j.jalgebra.2006.02.012, MR 2278053, S2CID 11566447
  33. ^ Nadler, S. B. Jr. (1973), "The indecomposability of the dyadic solenoid", The American Mathematical Monthly, 80 (6): 677–679, doi:10.2307/2319174, JSTOR 2319174
  34. ^ Bhattacharjee, Meenaxi; Macpherson, Dugald; Möller, Rögnvaldur G.; Neumann, Peter M. (1997), "Rational numbers", Notes on Infinite Permutation Groups, Texts and Readings in Mathematics, vol. 12, Berlin: Springer-Verlag, pp. 77–86, doi:10.1007/978-93-80250-91-5_9, ISBN 81-85931-13-5, MR 1632579
  35. ^ Girgensohn, Roland (1996), "Constructing singular functions via Farey fractions", Journal of Mathematical Analysis and Applications, 203 (1): 127–141, doi:10.1006/jmaa.1996.0370, MR 1412484
  36. ^ Cvitanović, Predrag; Gunaratne, Gemunu H.; Procaccia, Itamar (1988), "Topological and metric properties of Hénon-type strange attractors", Physical Review A, Third Series, 38 (3): 1503–1520, Bibcode:1988PhRvA..38.1503C, doi:10.1103/PhysRevA.38.1503, MR 0970237, PMID 9900529
  37. ^ Brin, Matthew G. (1999), "The ubiquity of Thompson's group F in groups of piecewise linear homeomorphisms of the unit interval", Journal of the London Mathematical Society, Second Series, 60 (2): 449–460, arXiv:math/9705205, doi:10.1112/S0024610799007905, MR 1724861, S2CID 14490692
  38. ^ Cannon, J. W.; Floyd, W. J. (2011), "What is … Thompson's group?" (PDF), Notices of the American Mathematical Society, 58 (8): 1112–1113, MR 2856142
  39. ^ Fernandes, António M.; Ferreira, Fernando (2005), "Basic applications of weak König's lemma in feasible analysis" (PDF), Reverse Mathematics 2001, Lecture Notes in Logic, vol. 21, La Jolla, California: Association for Symbolic Logic, pp. 175–188, MR 2185433
  40. ^ Conway, J. H. (2001), On Numbers and Games (Second ed.), Natick, Massachusetts: A K Peters, ISBN 1-56881-127-6, MR 1803095; for the dyadic rationals, see "The numbers  ,  ,  ,  , and so on", pp. 10–12
  41. ^ Mauldon, J. G. (1978), "Num, a variant of Nim with no first-player win", The American Mathematical Monthly, 85 (7): 575–578, doi:10.2307/2320870, JSTOR 2320870, MR 0503877
  42. ^ Flanigan, J. A. (1982), "A complete analysis of black-white Hackendot", International Journal of Game Theory, 11 (1): 21–25, doi:10.1007/BF01771244, MR 0665515, S2CID 119964871
  43. ^ Erickson, Jeff; Nivasch, Gabriel; Xu, Junyan (June 2021), "Fusible numbers and Peano arithmetic", Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2021), IEEE, pp. 1–13, arXiv:2003.14342, doi:10.1109/lics52264.2021.9470703, S2CID 214727767
  44. ^ Sloane, N. J. A. (ed.), "Sequence A188545", The On-Line Encyclopedia of Integer Sequences, OEIS Foundation

dyadic, rational, mathematics, dyadic, rational, binary, rational, number, that, expressed, fraction, whose, denominator, power, example, dyadic, rationals, these, numbers, important, computer, science, because, they, only, ones, with, finite, binary, represen. In mathematics a dyadic rational or binary rational is a number that can be expressed as a fraction whose denominator is a power of two For example 1 2 3 2 and 3 8 are dyadic rationals but 1 3 is not These numbers are important in computer science because they are the only ones with finite binary representations Dyadic rationals also have applications in weights and measures musical time signatures and early mathematics education They can accurately approximate any real number Dyadic rationals in the interval from 0 to 1 The sum difference or product of any two dyadic rational numbers is another dyadic rational number given by a simple formula However division of one dyadic rational number by another does not always produce a dyadic rational result Mathematically this means that the dyadic rational numbers form a ring lying between the ring of integers and the field of rational numbers This ring may be denoted Z 1 2 displaystyle mathbb Z tfrac 1 2 In advanced mathematics the dyadic rational numbers are central to the constructions of the dyadic solenoid Minkowski s question mark function Daubechies wavelets Thompson s group Prufer 2 group surreal numbers and fusible numbers These numbers are order isomorphic to the rational numbers they form a subsystem of the 2 adic numbers as well as of the reals and can represent the fractional parts of 2 adic numbers Functions from natural numbers to dyadic rationals have been used to formalize mathematical analysis in reverse mathematics Contents 1 Applications 1 1 In measurement 1 2 In computing 1 3 In music 1 4 In mathematics education 2 Definitions and arithmetic 3 Additional properties 4 In advanced mathematics 4 1 Algebraic structure 4 2 Dyadic solenoid 4 3 Functions with dyadic rationals as distinguished points 4 4 Other related constructions 5 ReferencesApplications EditIn measurement Edit Kitchen weights measuring dyadic fractions of a pound from 2 lb down to 1 64 lb 1 4 oz Many traditional systems of weights and measures are based on the idea of repeated halving which produces dyadic rationals when measuring fractional amounts of units The inch is customarily subdivided in dyadic rationals rather than using a decimal subdivision 1 The customary divisions of the gallon into half gallons quarts pints and cups are also dyadic 2 The ancient Egyptians used dyadic rationals in measurement with denominators up to 64 3 Similarly systems of weights from the Indus Valley civilisation are for the most part based on repeated halving anthropologist Heather M L Miller writes that halving is a relatively simple operation with beam balances which is likely why so many weight systems of this time period used binary systems 4 In computing Edit Dyadic rationals are central to computer science as a type of fractional number that many computers can manipulate directly 5 In particular as a data type used by computers floating point numbers are often defined as integers multiplied by positive or negative powers of two The numbers that can be represented precisely in a floating point format such as the IEEE floating point datatypes are called its representable numbers For most floating point representations the representable numbers are a subset of the dyadic rationals 6 The same is true for fixed point datatypes which also use powers of two implicitly in the majority of cases 7 Because of the simplicity of computing with dyadic rationals they are also used for exact real computing using interval arithmetic 8 and are central to some theoretical models of computable numbers 9 10 11 Generating a random variable from random bits in a fixed amount of time is possible only when the variable has finitely many outcomes whose probabilities are all dyadic rational numbers For random variables whose probabilities are not dyadic it is necessary either to approximate their probabilities by dyadic rationals or to use a random generation process whose time is itself random and unbounded 12 In music Edit source Audio playback is not supported in your browser You can download the audio file Five bars from Igor Stravinski s The Rite of Springshowing time signatures 316 216 316 and 28 Time signatures in Western musical notation traditionally are written in a form resembling fractions for example 22 44 or 68 13 although the horizontal line of the musical staff that separates the top and bottom number is usually omitted when writing the signature separately from its staff As fractions they are generally dyadic 14 although non dyadic time signatures have also been used 15 The numeric value of the signature interpreted as a fraction describes the length of a measure as a fraction of a whole note Its numerator describes the number of beats per measure and the denominator describes the length of each beat 13 14 In mathematics education Edit In theories of childhood development of the concept of a fraction based on the work of Jean Piaget fractional numbers arising from halving and repeated halving are among the earliest forms of fractions to develop 16 This stage of development of the concept of fractions has been called algorithmic halving 17 Addition and subtraction of these numbers can be performed in steps that only involve doubling halving adding and subtracting integers In contrast addition and subtraction of more general fractions involves integer multiplication and factorization to reach a common denominator Therefore dyadic fractions can be easier for students to calculate with than more general fractions 18 Definitions and arithmetic EditThe dyadic numbers are the rational numbers that result from dividing an integer by a power of two 9 A rational number p q displaystyle p q in simplest terms is a dyadic rational when q displaystyle q is a power of two 19 Another equivalent way of defining the dyadic rationals is that they are the real numbers that have a terminating binary representation 9 Addition subtraction and multiplication of any two dyadic rationals produces another dyadic rational according to the following formulas 20 a 2 b c 2 d 2 d min b d a 2 b min b d c 2 max b d a 2 b c 2 d 2 d min b d a 2 b min b d c 2 max b d a 2 b c 2 d a c 2 b d displaystyle begin aligned frac a 2 b frac c 2 d amp frac 2 d min b d a 2 b min b d c 2 max b d 6px frac a 2 b frac c 2 d amp frac 2 d min b d a 2 b min b d c 2 max b d 6px frac a 2 b cdot frac c 2 d amp frac ac 2 b d end aligned However the result of dividing one dyadic rational by another is not necessarily a dyadic rational 21 For instance 1 and 3 are both dyadic rational numbers but 1 3 is not Additional properties Edit Dyadic rational approximations to the square root of 2 2 1 4142 displaystyle sqrt 2 approx 1 4142 found by rounding to the nearest smaller integer multiple of 1 2 i displaystyle 1 2 i for i 0 1 2 displaystyle i 0 1 2 dots The height of the pink region above each approximation is its error Real numbers with no unusually accurate dyadic rational approximations The red circles surround numbers that are approximated within error 1 6 2 i displaystyle tfrac 1 6 2 i by n 2 i displaystyle n 2 i For numbers in the fractal Cantor set outside the circles all dyadic rational approximations have larger errors Every integer and every half integer is a dyadic rational 22 They both meet the definition of being an integer divided by a power of two every integer is an integer divided by one the zeroth power of two and every half integer is an integer divided by two Every real number can be arbitrarily closely approximated by dyadic rationals In particular for a real number x displaystyle x consider the dyadic rationals of the form 2 i x 2 i textstyle lfloor 2 i x rfloor 2 i where i displaystyle i can be any integer and displaystyle lfloor dots rfloor denotes the floor function that rounds its argument down to an integer These numbers approximate x displaystyle x from below to within an error of 1 2 i displaystyle 1 2 i which can be made arbitrarily small by choosing i displaystyle i to be arbitrarily large For a fractal subset of the real numbers this error bound is within a constant factor of optimal for these numbers there is no approximation n 2 i displaystyle n 2 i with error smaller than a constant times 1 2 i displaystyle 1 2 i 23 24 The existence of accurate dyadic approximations can be expressed by saying that the set of all dyadic rationals is dense in the real line 22 More strongly this set is uniformly dense in the sense that the dyadic rationals with denominator 2 i displaystyle 2 i are uniformly spaced on the real line 9 The dyadic rationals are precisely those numbers possessing finite binary expansions 9 Their binary expansions are not unique there is one finite and one infinite representation of each dyadic rational other than 0 ignoring terminal 0s For example 0 112 0 10111 2 giving two different representations for 3 4 9 25 The dyadic rationals are the only numbers whose binary expansions are not unique 9 In advanced mathematics EditAlgebraic structure Edit Because they are closed under addition subtraction and multiplication but not division the dyadic rationals are a ring but not a field 26 The ring of dyadic rationals may be denoted Z 1 2 displaystyle mathbb Z tfrac 1 2 meaning that it can be generated by evaluating polynomials with integer coefficients at the argument 1 2 27 As a ring the dyadic rationals are a subring of the rational numbers and an overring of the integers 28 Algebraically this ring is the localization of the integers with respect to the set of powers of two 29 As well as forming a subring of the real numbers the dyadic rational numbers form a subring of the 2 adic numbers a system of numbers that can be defined from binary representations that are finite to the right of the binary point but may extend infinitely far to the left The 2 adic numbers include all rational numbers not just the dyadic rationals Embedding the dyadic rationals into the 2 adic numbers does not change the arithmetic of the dyadic rationals but it gives them a different topological structure than they have as a subring of the real numbers As they do in the reals the dyadic rationals form a dense subset of the 2 adic numbers 30 and are the set of 2 adic numbers with finite binary expansions Every 2 adic number can be decomposed into the sum of a 2 adic integer and a dyadic rational in this sense the dyadic rationals can represent the fractional parts of 2 adic numbers but this decomposition is not unique 31 Addition of dyadic rationals modulo 1 the quotient group Z 1 2 Z displaystyle mathbb Z tfrac 1 2 mathbb Z of the dyadic rationals by the integers forms the Prufer 2 group 32 Dyadic solenoid Edit Considering only the addition and subtraction operations of the dyadic rationals gives them the structure of an additive abelian group Pontryagin duality is a method for understanding abelian groups by constructing dual groups whose elements are characters of the original group group homomorphisms to the multiplicative group of the complex numbers with pointwise multiplication as the dual group operation The dual group of the additive dyadic rationals constructed in this way can also be viewed as a topological group It is called the dyadic solenoid and is isomorphic to the topological product of the real numbers and 2 adic numbers quotiented by the diagonal embedding of the dyadic rationals into this product 30 It is an example of a protorus a solenoid and an indecomposable continuum 33 Functions with dyadic rationals as distinguished points Edit Minkowski s question mark function maps rational numbers to dyadic rationals A Daubechies wavelet showing points of non smoothness at dyadic rationals Because they are a dense subset of the real numbers the dyadic rationals with their numeric ordering form a dense order As with any two unbounded countable dense linear orders by Cantor s isomorphism theorem 34 the dyadic rationals are order isomorphic to the rational numbers In this case Minkowski s question mark function provides an order preserving bijection between the set of all rational numbers and the set of dyadic rationals 35 The dyadic rationals play a key role in the analysis of Daubechies wavelets as the set of points where the scaling function of these wavelets is non smooth 26 Similarly the dyadic rationals parameterize the discontinuities in the boundary between stable and unstable points in the parameter space of the Henon map 36 The set of piecewise linear homeomorphisms from the unit interval to itself that have power of 2 slopes and dyadic rational breakpoints forms a group under the operation of function composition This is Thompson s group the first known example of an infinite but finitely presented simple group 37 The same group can also be represented by an action on rooted binary trees 38 or by an action on the dyadic rationals within the unit interval 32 Other related constructions Edit In reverse mathematics one way of constructing the real numbers is to represent them as functions from unary numbers to dyadic rationals where the value of one of these functions for the argument i displaystyle i is a dyadic rational with denominator 2 i displaystyle 2 i that approximates the given real number Defining real numbers in this way allows many of the basic results of mathematical analysis to be proven within a restricted theory of second order arithmetic called feasible analysis BTFA 39 The surreal numbers are generated by an iterated construction principle which starts by generating all finite dyadic rationals and then goes on to create new and strange kinds of infinite infinitesimal and other numbers 40 This number system is foundational to combinatorial game theory and dyadic rationals arise naturally in this theory as the set of values of certain combinatorial games 41 42 19 The fusible numbers are a subset of the dyadic rationals the closure of the set 0 displaystyle 0 under the operation x y x y 1 2 displaystyle x y mapsto x y 1 2 restricted to pairs x y displaystyle x y with x y lt 1 displaystyle x y lt 1 They are well ordered with order type equal to the epsilon number e 0 displaystyle varepsilon 0 For each integer n displaystyle n the smallest fusible number that is greater than n displaystyle n has the form n 1 2 k displaystyle n 1 2 k The existence of k displaystyle k for each n displaystyle n cannot be proven in Peano arithmetic 43 and k displaystyle k grows so rapidly as a function of n displaystyle n that for n 3 displaystyle n 3 it is in Knuth s up arrow notation for large numbers already larger than 2 9 16 displaystyle 2 uparrow 9 16 44 The usual proof of Urysohn s lemma utilizes the dyadic fractions for constructing the separating function from the lemma References Edit Rudman Peter S 2009 How Mathematics Happened The First 50 000 Years Prometheus Books p 148 ISBN 978 1 61592 176 8 Barnes John 2016 Nice Numbers Springer International Publishing doi 10 1007 978 3 319 46831 0 ISBN 978 3 319 46830 3 Note that binary measures 2 4 8 16 are very common indeed This is particularly obvious with volumes Curtis Lorenzo J 1978 Concept of the exponential law prior to 1900 American Journal of Physics 46 9 896 906 Bibcode 1978AmJPh 46 896C doi 10 1119 1 11512 Miller Heather M L 2013 Weighty matters evidence for unity and regional diversity from the Indus civilization weights in Abraham Shinu Anna Gullapalli Praveena Raczek Teresa P Rizvi Uzma Z eds Connections and Complexity New Approaches to the Archaeology of South Asia Left Coast Press pp 161 177 doi 10 4324 9781315431857 ISBN 978 1 59874 686 0 see in particular p 166 Resnikoff Howard L Wells Raymond O Jr 1998 2 2 1 Digital computers and measurement Wavelet Analysis The Scalable Structure of Information New York Springer Verlag pp 17 18 doi 10 1007 978 1 4612 0593 7 ISBN 0 387 98383 X MR 1712468 Kirk David B Hwu Wen mei W 2013 7 2 Representable numbers Programming Massively Parallel Processors A Hands on Approach 2nd ed Morgan Kaufmann pp 155 159 ISBN 978 0 12 391418 7 Kneusel Ronald T 2017 Chapter 6 Fixed point numbers Numbers and Computers 2nd ed Springer International Publishing pp 183 214 doi 10 1007 978 3 319 50508 4 6 van der Hoeven Joris 2006 Computations with effective real numbers Theoretical Computer Science 351 1 52 60 doi 10 1016 j tcs 2005 09 060 MR 2201092 a b c d e f g Ko Ker I 1991 Complexity Theory of Real Functions Progress in Theoretical Computer Science Boston Massachusetts Birkhauser Boston Inc pp 41 43 doi 10 1007 978 1 4684 6802 1 ISBN 0 8176 3586 6 MR 1137517 S2CID 11758381 Zheng Xizhong Rettinger Robert 2004 Weak computability and representation of reals Mathematical Logic Quarterly 50 4 5 431 442 doi 10 1002 malq 200310110 MR 2090389 S2CID 15815720 Ambos Spies Klaus Zheng Xizhong 2019 On the differences and sums of strongly computably enumerable real numbers in Manea Florin Martin Barnaby Paulusma Daniel Primiero Giuseppe eds Computing with Foresight and Industry 15th Conference on Computability in Europe CiE 2019 Durham UK July 15 19 2019 Proceedings Lecture Notes in Computer Science vol 11558 Cham Springer pp 310 322 doi 10 1007 978 3 030 22996 2 27 MR 3981892 S2CID 195795492 Jerrum Mark R Valiant Leslie G Vazirani Vijay V 1986 Random generation of combinatorial structures from a uniform distribution Theoretical Computer Science 43 2 3 169 188 doi 10 1016 0304 3975 86 90174 X MR 0855970 a b Jones Shelly M Pearson Dunn May 2013 Music highly engaged students connect music to math General Music Today 27 1 18 23 doi 10 1177 1048371313486478 S2CID 220604326 a b Libbey Theodore 2006 Time signature The NPR Listener s Encyclopedia of Classical Music Workman Publishing p 873 ISBN 978 0 7611 2072 8 Yanakiev Ivan K 2020 Mathematical devices in aid of music theory composition and performance in Bozhikova Milena ed Music between Ontology and Ideology Cambridge Scholars Publishing pp 35 62 ISBN 978 1 5275 4758 2 see in particular p 37 Hiebert James Tonnessen Lowell H November 1978 Development of the fraction concept in two physical contexts an exploratory investigation Journal for Research in Mathematics Education 9 5 374 378 doi 10 2307 748774 JSTOR 748774 Pothier Yvonne Sawada Daiyo November 1983 Partitioning the emergence of rational number ideas in young children Journal for Research in Mathematics Education 14 5 307 317 doi 10 2307 748675 JSTOR 748675 Wells David Graham 2015 Motivating Mathematics Engaging Teachers And Engaged Students World Scientific pp 32 33 ISBN 978 1 78326 755 2 a b Uiterwijk Jos W H M Barton Michael 2015 New results for Domineering from combinatorial game theory endgame databases Theoretical Computer Science 592 72 86 arXiv 1506 03949 doi 10 1016 j tcs 2015 05 017 MR 3367582 S2CID 5899577 Equivalent formulas to these written in the language of the Coq interactive theorem prover are given by Krebbers Robbert Spitters Bas 2013 Type classes for efficient exact real arithmetic in Coq Logical Methods in Computer Science 9 1 1 01 27 arXiv 1106 3448 doi 10 2168 LMCS 9 1 1 2013 MR 3029087 S2CID 218627153 O Connor Russell 2007 A monadic functional implementation of real numbers Mathematical Structures in Computer Science 17 1 129 159 doi 10 1017 S0960129506005871 MR 2311089 S2CID 221168970 a b Sabin Malcolm 2010 Analysis and Design of Univariate Subdivision Schemes Geometry and Computing vol 6 Springer p 51 ISBN 9783642136481 More precisely for small positive values of e displaystyle varepsilon the set of real numbers that have no approximation n 2 i displaystyle n 2 i with error smaller than a constant times e 2 i displaystyle varepsilon 2 i forms a Cantor set whose Hausdorff dimension as a function of e displaystyle varepsilon goes to one as e displaystyle varepsilon approaches zero The illustration shows this set for e 1 6 displaystyle varepsilon tfrac 1 6 Nilsson Johan 2009 On numbers badly approximable by dyadic rationals Israel Journal of Mathematics 171 93 110 doi 10 1007 s11856 009 0042 9 MR 2520103 Kac Mark 1959 Statistical Independence in Probability Analysis and Number Theory Carus Mathematical Monographs vol 12 New York John Wiley amp Sons for the Mathematical Association of America pp 2 3 MR 0110114 a b Pollen David 1992 Daubechies scaling function on 0 3 Wavelets Wavelet Analysis and Its Applications vol 2 Boston Massachusetts Academic Press pp 3 13 MR 1161245 Bajnok Bela 2013 An Invitation to Abstract Mathematics Undergraduate Texts in Mathematics New York Springer p 186 doi 10 1007 978 1 4614 6636 9 ISBN 978 1 4614 6635 2 In the notation of Estes and Ohm for rings that are both subrings of Q displaystyle mathbb Q and overrings of Z displaystyle mathbb Z the dyadic rationals are the ring Z 2 displaystyle mathbb Z 2 See section 7 of Estes Dennis Ohm Jack 1967 Stable range in commutative rings PDF Journal of Algebra 7 3 343 362 doi 10 1016 0021 8693 67 90075 0 MR 0217052 Lucyshyn Wright Rory B B 2018 Convex spaces affine spaces and commutants for algebraic theories Applied Categorical Structures 26 2 369 400 arXiv 1603 03351 doi 10 1007 s10485 017 9496 9 MR 3770912 S2CID 3743682 a b Manners Freddie 2015 A solution to the pyjama problem Inventiones Mathematicae 202 1 239 270 arXiv 1305 1514 Bibcode 2015InMat 202 239M doi 10 1007 s00222 014 0571 7 MR 3402799 S2CID 119148680 see section 6 2 1 A model case Z 1 2 displaystyle widehat mathbb Z 1 2 pp 255 257 Robert Alain M 2000 5 4 Fractional and integral parts of p displaystyle p adic numbers A Course in p displaystyle p adic Analysis Graduate Texts in Mathematics vol 198 New York Springer Verlag pp 40 43 doi 10 1007 978 1 4757 3254 2 ISBN 0 387 98669 3 MR 1760253 a b de Cornulier Yves Guyot Luc Pitsch Wolfgang 2007 On the isolated points in the space of groups PDF Journal of Algebra 307 1 254 277 arXiv math 0511714 doi 10 1016 j jalgebra 2006 02 012 MR 2278053 S2CID 11566447 Nadler S B Jr 1973 The indecomposability of the dyadic solenoid The American Mathematical Monthly 80 6 677 679 doi 10 2307 2319174 JSTOR 2319174 Bhattacharjee Meenaxi Macpherson Dugald Moller Rognvaldur G Neumann Peter M 1997 Rational numbers Notes on Infinite Permutation Groups Texts and Readings in Mathematics vol 12 Berlin Springer Verlag pp 77 86 doi 10 1007 978 93 80250 91 5 9 ISBN 81 85931 13 5 MR 1632579 Girgensohn Roland 1996 Constructing singular functions via Farey fractions Journal of Mathematical Analysis and Applications 203 1 127 141 doi 10 1006 jmaa 1996 0370 MR 1412484 Cvitanovic Predrag Gunaratne Gemunu H Procaccia Itamar 1988 Topological and metric properties of Henon type strange attractors Physical Review A Third Series 38 3 1503 1520 Bibcode 1988PhRvA 38 1503C doi 10 1103 PhysRevA 38 1503 MR 0970237 PMID 9900529 Brin Matthew G 1999 The ubiquity of Thompson s group F in groups of piecewise linear homeomorphisms of the unit interval Journal of the London Mathematical Society Second Series 60 2 449 460 arXiv math 9705205 doi 10 1112 S0024610799007905 MR 1724861 S2CID 14490692 Cannon J W Floyd W J 2011 What is Thompson s group PDF Notices of the American Mathematical Society 58 8 1112 1113 MR 2856142 Fernandes Antonio M Ferreira Fernando 2005 Basic applications of weak Konig s lemma in feasible analysis PDF Reverse Mathematics 2001 Lecture Notes in Logic vol 21 La Jolla California Association for Symbolic Logic pp 175 188 MR 2185433 Conway J H 2001 On Numbers and Games Second ed Natick Massachusetts A K Peters ISBN 1 56881 127 6 MR 1803095 for the dyadic rationals see The numbers 1 4 displaystyle tfrac 1 4 3 4 displaystyle tfrac 3 4 1 1 2 displaystyle 1 tfrac 1 2 3 displaystyle 3 and so on pp 10 12 Mauldon J G 1978 Num a variant of Nim with no first player win The American Mathematical Monthly 85 7 575 578 doi 10 2307 2320870 JSTOR 2320870 MR 0503877 Flanigan J A 1982 A complete analysis of black white Hackendot International Journal of Game Theory 11 1 21 25 doi 10 1007 BF01771244 MR 0665515 S2CID 119964871 Erickson Jeff Nivasch Gabriel Xu Junyan June 2021 Fusible numbers and Peano arithmetic Proceedings of the 36th Annual ACM IEEE Symposium on Logic in Computer Science LICS 2021 IEEE pp 1 13 arXiv 2003 14342 doi 10 1109 lics52264 2021 9470703 S2CID 214727767 Sloane N J A ed Sequence A188545 The On Line Encyclopedia of Integer Sequences OEIS Foundation Retrieved from https en wikipedia org w index php title Dyadic rational amp oldid 1123375333, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.