Z2adic.txt 0.0.8 UTF-8 2024-01-17 *---|----1----|----2----|----3----|----4----|----5----|----6----|----7----|--* The Miser Project ================= Z 2'S COMPLEMENT ARITHMETIC IMPLEMENTATION ------------------------------------------ The interpretation of Integer Arithmetic is based on the ‹ba› simulation of Boolean Algebra using ob.bvx for arbitrary length Boolean vectors. See boole.txt for details. For Z2adic, ob.bvx structures are interpreted as 2's complement binary numerals. The terminal element, followed by a ":" is taken as the sign. It is called a bumper and it stands for an indefinite sequence of the same digit. The numerals are taken to have taken as being an extension of that bit indefinitely. The notation is little-endian. The first element is the lowest-order bit of the numeral. The name is a combination of Z (the negative and non-negative integer domain) and 2-adic with respect to the form of numerals and their connection to the more general 2-adic numerals. 1. SYNOPSIS: THE FUNDAMENTAL REPRESENTATION For the arithmetic interpretation, write 0 and 1 instead of the corresponding bot, ⊥, and top, ⊤. 1:0 represents 1, 01:0 represents 2, 11:0 represents 3, and 001:0 represents 4. Notice that the left-to-right reading of the bits is from low-order bit to successively higher ones. The form :0 is a "bumper." It signifies an inexhaustible sequence of 0 digits (bits). It is a shorthand for as many 0 digits as are useful. The unique canonical form of a :0-terminated sequence is achieved by removing every 0 the left of the :0 bumper up until any 1 bit. So :0 is the canonical form for representing integer 0. The form :1 is the bumper for an inexhaustible sequence of 1 bits. The canonical form of of a :1-terminated sequence is achieved by removing ever 0 to the left of the :1 bumper up until any 0. So :1 for 111...:1 with any number of 1's forming 111... . The binary numerals are taken as 2's-complement binary numerals in which :1 represents integer -1, 0:1 represents -2, 10:1 for -3, and so on. In this scheme the negation of a number is expressed by adding 1 (an incoming carry) to the 1's-complement of the Z2adic expression of the given number. Ths can be done in a single left-to-right scan of the original numeral, replacing digits as follows. 1. a. If there is a carry in, a 0 remains 0 and there's a carry out. b. If there is no carry in, a 0 becomes 1 with no carry out. 2. a. If there is a carry in, a 1 remains 1 with no carry out. b. If there is no carry in, a 1 becomes a 0 with no carry out. 3. a. If there is a carry in, :0 remains :0 and we're done. b. If there is no carry in, :0 becomes :1 and we're done. 4 a. If there is a carry in, :1 becomes the pair 1:0 and we're done. b. If there is no carry in, :1 becomes :0 and we're done. In this scheme, the 2's complement of :0 is :0 as expected. And the 2's complement of :1 is 1:0 as expected. [EDITOR'S NOTE: THE RULE 3a DEPENDS ON A KIND OF JUST-SHORT-OF- INFINITARY ARGUMENT. THAT NEEDS TO BE DEALT WITH SOMEWHERE BELOW.] BOILERPLATE BELOW HERE - REWRITING FOR mathZ PENDING **************************************************** CONTENT 2. MATHEMATICAL STRUCTURES ‹N› AND ‹Z› 1.1 Notation and Basic Operations 1.2 Basic Constraints (Axioms) 1.3 Additional Characteristics 1.4 Interpretations 3. Zadic IMPLEMENTATION OF ‹Z› 2.1 Prototypical (Standard) Representation 2.2 Notable Qualities 2.3 ‹bp› Interpretation in ‹ob› 4. ‹Z› PRIMITIVE OPERATIONS 3.4 ‹ba› Simulation in ‹ob›: All-‹bvn› Interpretation ob.bvx 3.5 Circling back: Distinguishing ob.bvx as ‹ba› interpretation 5. NOTES AND REFERENCES Sources on N, Z, and 2's complement numeral representations of finite Z. ** TRANSFORMATION NEEDED BELOW HERE ** 2. MATHEMATICAL STRUCTURE The mathematical structure ‹Z› is introduced in the same manner as for ‹ob› and . We start with the structure ‹N› of Peano Numbers, and then expand that to achieve structure ‹Z› of all integers. ‹N› = 〈Ni,Nf,Nt〉 ‹Z› = 〈Zi,Zf,Zt〉 2.1 Notation and Basic Operations The ‹ba› domain of discourse, Ba, is a finite set having at least two distinct members, two of which are distinguished as ⊤ and ⊥, respectively. The ‹bp› domain of discourse, Bp, consists of only the two distinguished entities and is taken as the prototypical (standard) Boolean Algebra. ⊤ (nickname "top") ⊥ (nickname "bot") The basic operations consist of a small number of functions typically expressed as operations. ~ x "comp" x, signifies the complement of x, comp(x) x ∩ y x "cap" y also known as the meet of x and y, meet(x,y) x ∪ y x "cup" y also known as the join of x and y, join(x,y) x ∸ y x "sep" y, sep(x,y) is x ∪ y excluding x ∩ y, also known as the symmetric difference, that which is separate between x and y, if anything. In addition to equality, there is also an ordering relation, x ⊆ y x "sub" y, sub(x, y) comparable to the subset relation among sets. To simplify expressions and reduce parentheses, the above listing is taken as an order of precedence, from strongest to weakest. That is x ∩ ~ y ∪ ~ x ∩ y = (x ∩ (~ y)) ∪ ((~ x) ∩ y) 1.2 Basic Constraints (Axioms) The basic conditions on all ‹ba› structures are presented in terms of axioms, arrangements that hold whatever the domain of discourse, Ba, happens to be and however the operations are defined in satisfaction of these constraints without any inconsistency. The conditions Ba1-Ba5 are standard axioms for Boolean Algebras. They are invariants, applying without exception in the context of a structure that satisfies Boolean Algebra conditions. This can also be said to constitute a Boolean Algebra interpretation of a satisfying structure. Ba1. Commutativity x ∪ y = y ∪ x x ∩ y = y ∩ x Ba2. Identity x ∪ ⊥ = x x ∩ ⊤ = x Ba3. Distributivity x ∪ (y ∩ z) = (x ∪ y) ∩ (x ∪ z) x ∩ (y ∪ z) = (x ∩ y) ∪ (x ∩ z) Ba4. Complements x ∪ ~ x = ⊤ x ∩ ~ x = ⊥ Ba5. Subordination x ⊆ y ⇔ x = x ∩ y 1.3 Additional Characteristics The following are consequences of the chosen axioms. They apply to any Boolean Algebra structure ‹ba› with distinguished domain of discourse Ba and definite basic operations satisfying Ba1-Ba5. Ba6. Associativity x ∪ (y ∪ z) = (x ∪ y) ∪ z x ∩ (y ∩ z) = (x ∩ y) ∩ z Ba7. Absorption x ∪ (x ∩ y) = x x ∩ (x ∪ y) = x Ba8. Unique Complement Pairs x = ~ ~ x x ≠ ~ x Ba9. Separation (definition) x ∸ y = x ∩ ~ y ∪ ~ x ∩ y Ba10. Partial Ordering ⊥ ⊆ y (hence "bot") x ⊆ ⊤ (hence "top") Ba11. Identity x = y ⇔ x ⊆ y ∧ y ⊆ x Ba12. The number of members in the domain of discourse Ba is even and a power of 2. 1.4 Interpretations After [Forster2003], an interpretation where "="s correspond is termed an implementation. We will make that the case. 2. Z2adic IMPLEMENTATION OF ‹Z› 3.4 ‹Z› Implementation in ‹ob›: Treatment of ob.bvx By virtue of the isomorphism between any ‹ba› and some ‹bn› (section 3.1) and thence some ‹bvn› (section 3.2), it is sufficient to interpret the ‹bvn› in ‹ob›. * For 0 and 1 vi entities in ‹bvn› n-tuples [v1, v2, ..., vn], use the interpretation ob.p01.bp in the equivalence form (section 2.5), signified I(vi). * Interpret the sequence [v1, v2, ..., vn] with the construction ob.c(I(v1), (ob.c(I(v2), ob.c(..., ob.c(I(v(n-1)), xn)...)))) where xn is restricted to a singleton under interpretation ob.p01.bp. This ‹ob› representation is abbreviated [I(v1), I(v2), ..., I(vn):] with I(vn) not a pair. * For representation of corresponding ‹bvn› and the concrete-isomorph sequence [xn, ... x2, x1] (section 3.3), interpret via ‹ob› sequence representation [I(x1), I(x2), ..., I(xn):]. Interpretation of the ‹bvn›-represented basic operations (section 1.1) is by corresponding ob.bvx functions represented as follows. ob.bvx.bot = ob.p01.bp.bot (i.e., representing [0, 0, ...] here) ob.bvx.top = ob.p01.bp.top (i.e., representing [1, 1, ...] here) ob.is-singleton(x) ⇒ ob.bvx.comp(x) = ob.p01.bp.comp(x) ¬ ob.is-singleton(x) ⇒ ob.bvx.comp(x) = ob.c( ob.p01.bp.comp(ob.a(x)), ob.bvx.comp(ob.b(x)) ) ob.is-singleton(x) ∧ ob.is-singleton(y) ⇒ ob.bvx.meet(x, y) = ob.p01.bp.meet(x, y) ob.is-singleton(x) ∧ ¬ ob.is-singleton(y) ⇒ ob.bvx.meet(x, y) = ob.bvx.meet(y, x) ¬ ob.is-singleton(x) ∧ ob.is-individual(y) ⇒ ob.bvx.meet(x, y) = y ¬ ob.is-singleton(x) ∧ ob.is-enclosure(y) ⇒ ob.bvx.meet(x, y) = x ¬ ob.is-singleton(x) ∧ ¬ ob.is-singleton(y) ⇒ ob.bvx.meet(x, y) = ob.c( ob.p01.bp.meet(ob.a(x), ob.a(y)), ob.bvx.meet(ob.b(x),ob.b(y)) ) Using the above representation of ob.bvx.meet, represent each of ob.bvx.join and ob.bvx.sep by substitution of "join" for "meet" and substitution of "sep" for "meet", respectively. Adjust the two ¬ ob.is-singleton(x) ∧ ob.is-singleton(y) cases appropriately (in the manner of section 2.1 standard operations) taking y as if one of ob.bvx.bot or ob.bvx.top. ob.is-singleton(x) ∧ ob.is-singleton(y) ⇒ ( ob.bvx.sub(x, y) ⇔ ob.p01.bp.sub(x, y) ) ob.is-individual(x) ∧ ¬ ob.is-singleton(y) ⇒ ob.bvx.sub(x, y) ob.is-enclosure(x) ∧ ¬ ob.is-singleton(y) ⇒ ( ob.bvx.sub(x, y) ⇔ ob.bvx.sub(x, ob.b(y)) ) ¬ ob.is-singleton(x) ∧ ob.is-singleton(y) ⇒ ( ob.bvx.sub(x, y) ⇔ ob.p01.bp.sub(ob.a(x), y) ∧ ob.bvx.sub(ob.b(x), y) ) ¬ ob.is-singleton(x) ∧ ¬ ob.is-singleton(y) ⇒ ( ob.bvx.sub(x, y) ⇔ ob.p01.bp.sub(ob.a(x), ob.a(y)) ∧ ob.bvx.sub(ob.b(x),ob.b(y)) ) ob.bvx.is-eq(x, y) ⇔ ob.bvx.sub(x,y) ∧ ob.bvx.sub(y,x) with the interpretation of ‹bvn› x = y being ob.bvx.is-eq(I(x),I(y)). Note some features of this interpretation. * The ob.bvx representations are total. Every ob has interpretation as a sequence under this simulation of ‹bvn› and the representation is defined over all definite obs. * Provided that the represented operations are confined to operand obs that are interpretations of ‹bvn› = 〈Bvn,Bvnf,Bvnt〉 domain elements, there is complete fidelity of ob.bvx as a simulation of ‹bvn›. * The interpretation of ‹bv1› in ob.bvx is equivalent to simulation in ob.p01.bp restricted to singletons. * When an operand sequence [x1, x2, ..., xm:] is of length less than that of another operand [y1, y2, ..., yn:], the ob.bvx representation is as if the shorter sequence is extended to match the length of the longer one by suffixing its xm element enought times, [x1, x2, ..., xm, xm, ..., xm:] * ob.bvx simulates a Boolean Algebra, one that accomodates all ‹bvn› of arbitrary (but finite) n. * Another interpretation of ob.bvx is as a simulation of binary numerals of arbitrary length. In this case, xi corresponds to 2^(i-1) and a subset corresponds to to the sum of those powers for which xi = 1. The extension of shorter sequences can be taken as viewing the shortened one as contraction of an arbitrary x. We can go farther and derive canonical forms by contraction. ob.is-singleton(x) ⇒ ob.bvx.cf(x) = ob.p01.bp.cf(x) ¬ ob.is-singleton(x) ⇒ ob.bvx.cf(x) = contraction(ob.p01.bp.cf(ob.a(x)), ob.b(x)) where ob.is-singleton(y) ⇒ contraction(x, y) = trimback(x, ob.p01.bp.cf(y)) ¬ ob.is-singleton(y) ⇒ contraction(x, y) = contraction(ob.c(ob.p01.bp.cf(ob.a(y)),x), ob.b(y)) where ob.is-singleton(x) ∧ x = y ⇒ trimback(x, y) = y ob.is-singleton(x) ∧ x ≠ y ⇒ trimback(x, y) = ob.c(x, y) ¬ ob.is-singleton(x) ∧ ob.a(x) = y ⇒ trimback(x, y) = trimback(ob.b(x), y) ¬ ob.is-singleton(x) ∧ ob.a(x) ≠ y ⇒ trimback(x, y) = repack(x, y) where ob.is-singleton(x) ⇒ repack(x, y) = ob.c(x, y) ¬ ob.is-singleton(x) ⇒ repack(x, y) = repack(ob.b(x), ob.c(ob.a(x), y)) Here the auxiliary function representations for contraction, trimback, and repack are internal to the representation of ob.bvx.cf(x). There are preconditions only satisfied by how the subordinate representations are appealed to in the representation of their superiors, above. These together ensure that the result is an ob.bvx canonical form. ob.bvx.cf(x) is an ob sequence in which the elements are ob.p01.bp.cf canonical forms, whether labelled as ⊥ and ⊤ or 0 and 1. Furthermore, ob.bvx.cf(x) is the shortest ob sequence, [v1:] or [v1, v2, ..., v(n-1), vn:], where v(n-1) is different than vn. It can be seen that [0:] in this notation is equivalent to [0, 0, 0, ...], hence the ⊥ of ‹bvx›, and [1:] is equivalent to [1, 1, 1, ...] and hence the ⊤. 3.5 Circling back: Distinguishing ob.bvx as ‹ba› interpretation Concluding that the representation, ob.bvx, is amenable to interpretation of any Boolean Algebra in ‹ob› leaves open questions about which Boolean Algebra and which interpretation thereof, and how is that conveyed. Assuming some sequence, An = [a1, a2, ..., an], the indicator functions (section 3.3), can be represented as follows. Associate, with An, the corresponding vectors Vn = [[1,0:], [0,1,0:], ..., [0,...,0,1:]] where the last has n-1 leading 0's and V1 = [[1:]]. Then ob.bvx.sub(vi, x) ⇔ ob.bvx.bvn.Iai(x) = 1, by definition. In order to interpret a specific ‹bvn›, n > 0, in ob.bvx, one can clamp the canonical forms such that only n bits of variation are in the interpretation and the set of canonical forms. ob.bvx.bvn.top = [1,...,1,0:] "with n 1's" ob.bvx.bvn.clamp(x) = ob.bvx.meet(x, ob.bvx.bvn.top) ob.bvx.bvn.cf(x) = ob.bvx.comp(ob.bvx.comp(ob.bvx.bvn.clamp(x) ) ). That some ob.bvx vectors have an additional (n+1)-th position does not impact taking other ob.bvx operations as ob.bvx.bvn operations, provided that the ‹bvn› x = y is interpreted in ‹ob› as ob.bvx.bvn.cf(x) = ob.bvx.bvn.cf(y) and ob.bvx.bvn.sub(x,y) ⇔ ob.bvx.sub(ob.bvx.bvn.clamp(x), y) Association with ai is still implicit and also order-dependent. It is tempting to go farther and present the association explicitly, say with Mn = [[v1, I(a1)], [v2, I(a2)], ..., [vn, I(an)]] where we require some manner of interpretation/expression of the ai, internal to the structure, especially in simple domains such as that of ‹ob›. For interpretation in ‹ob› by means such as ob.bvx, there are two important circumstances to be dealt with, especially when carried into computational-interpretation: the designation of the ai and preserving association with vi in operands of the represented primitive operations. Such implementation/simulation exigencies apply in the reduction to computation no matter the simplicity of the mathematical formulations. There are provisions in computational systems that bring some order to securing of interpretation constraints by computational means, including reconciliation between what appear to be incompatible interpretations of the same structures. Investigation of those prospects is left to consideration of extensions to the basic ‹ob› model of computation. 5. NOTES AND REFERENCES **** DECIDE WHAT MATTERS HERE AND REFERENCE boole.txt as needed. Symbols for Boolean operations are kept distinct from the logical connectives used in FOL= notation, hence the use of complement, meet, join, sep symbols and fussiness in qualifying names of function representations by the name of the particular structure and interpreta- tion, if any. These notational devices facilitate recognition of correspondences without implying identity, avoiding for a time any tacit collapsing of separate notions together as if about the same theoretical entities. * Miser Project: Representing Functions in ‹ob›'s Abstract World. Orcmid's Live Hideout blog article, available at in a series of posts that articulate ‹ob› structure, featuring representations include those for Boolean Algebra, here. This material prefaces introduction of the model of computation, * Hamilton, Dennis E. ‹ob› Mathematical Structure. 2018-11-17 article obtheory.txt 0.2.1, accessed on the Internet at . The mathematical formulation of the essential structure. [Forster2003] Forster, Thomas. Reasoning About Theoretical Entities. World Scientific (New Jersey: 2003). ISBN 981-238-567-3 [Knuth1998] Knuth, Donald E. Positional Number Systems. Section 4.1, pp. 194-280 in The Art of Computer Programming, Volume 2: Seminumerical Algorithms, ed.3. Addison-Wesley (Upper Saddle River, NJ: 1998). ISBN 0-201-89684-2. Page 203 introduces 2's complement arithmetic on n-bit numbers, where there is a negative number that has no positive complement. Exercise 4.1(7) considers the equivalent of our extension/bumper case for 10's complement arithmetic and what is sensible about the rule 4a here. Exercise 4.1(31) introduces K. Hensle's 2-adic numbers and the integer cases are precisely those of arithZ here. Internet at . *---|----1----|----2----|----3----|----4----|----5----|----6----|----7----|--* Copyright 2018-2024 Dennis E. Hamilton Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. *---|----1----|----2----|----3----|----4----|----5----|----6----|----7----|--* ATTRIBUTION Hamilton, Dennis E. Z2adic Integer Arithmetic in oMiser. Miser Theory Conception text file Z2adic.txt version 0.0.8 dated 2024-01-17, available on the Internet as a version of *---|----1----|----2----|----3----|----4----|----5----|----6----|----7----|--* TODO: * Complete the refactoring and establish tombstones in the previous location. There are incorrect cross-references in this material. * It is terrible to have so much material lying around from boole.txt still. I need to clean this up and also complete the refactoring to obreps/. * I don't need to deal with rationals yet. I think that will be Q2adic and I suspect that the recurring bits will be tricky. The Z2adic part should be the same. There is a difficulty on how to work to the "right" of the binary point and how that gets reconciled. The problem seems to be with addition. * When representation, interpretation, manifestation, implementation, and simulation are worked out more clearly, review these materials for consistent usage and links to related resources of the project and and elsewhere, especially ones of reference/historical value. * Find a nice algebraic characterization of Z, maybe even from Peano, and give the attribution and and further considerations. We are on the edge of recursive function theory here. * Replace rulers with the preferred form now used that also allows digital- signature armor. * Replace the references to wordpress pages to the Blogger pages but then to orcmid.github.io/miser pages. * There is something wrong with the [Knuth1998] Exercise 4.1(31). Having 1/7 and -1/7 be exactly represented in 2-adic numerals doesn't compute and there is no binary point in the examples. Track this down. See for related references and explanations. Also, Wikipedia refers to an older K. Hensel paper. * I am trying to square dyadic rational, in this case binary rational with this. * provides a similar case to what Knuth provides. I still don't understand how the rationals fall out and I am only using the Z integers representation. There is still some missing trick here. I think it has to do with repetitions but the tie-in with many Higher Algebra cases obscures all of this for me. * I have chosen Zadic for the name here. I need to be able to back that up or switch to an arithmetic, although Nadic, Zadic, and Qadic are fun. * I am satisfied with the rules given in the synopsis/sketch. I do need to distinguish the (prime) radix that's understood. So, should it be Z2adic or Zadic2. I think it should be first. Then Q2adic follows. Also, there can be an N1adic as well as an N2adic, the first being the counting with sticks (or successors of 0). * I posted a demonstration of the inexhaustible bumpers and the carry rule in the Z2adic case to FOM. We'll see how that lands. I am restating it here, now. *---|----1----|----2----|----3----|----4----|----5----|----6----|----7----|--* 0.0.8 2024-01-17T18:26Z More TODOs, much more refactoring required 0.0.7 2024-01-15T20:33Z Touch-ups, simplifying title 0.0.6 2023-11-10T20:38Z Adjust as part of refactoring to orcmid.github.io 0.0.5 2023-11-10T20:32Z Migrate to orcmid.github.io/miser/obrep/Z2adic.txt as part of Miser Project on GitHub refactoring. 0.0.4 2023-02-05T05:48Z Adjust to name Z2adic.txt and introduce a short-hand numerical-bumpered notation that is more compact than the list forms employed in the oMiser computational interpretation. 0.0.3 2023-02-05T02:41Z Small change commited before changing the name again. 0.0.2 2023-02-03T16:48Z Rename mathZ to Zadic and touch up accordingly. 0.0.1 2023-02-03T16:04Z Ponderings on 2-adic and what that means, with new references and some more scrapping of the boilerplate. 0.0.0 2023-01-30T23:22Z Draft synopsis over boilerplate of boole.txt version 0.5.3 *** end of Z2adic.txt ***