From: Michael Shulman <firstname.lastname@example.org> To: Jason Gross <email@example.com> Cc: Nicolai Kraus <firstname.lastname@example.org>, "HomotopyTypeTheory@googlegroups.com" <email@example.com> Subject: Re: [HoTT] two's complement integers Date: Thu, 4 Mar 2021 20:41:11 -0800 Message-ID: <CAOvivQxy2EJNScHu9Y2U=GLiHDrDxDq-Kg8Dz9TrFk3ZepiW8Q@mail.gmail.com> (raw) In-Reply-To: <CAKObCaqiyUcB+FrbvPmR-eS5ZMsb2CTVCtVbAYZeMUcOzCpmbA@mail.gmail.com> I don't have a particular application in mind at the moment. It just struck me how 2-adic integers have such simple coinductive definitions of the arithmetic operations, without any case distinctions at all, and I wondered whether there was a definition of plain integers with a similar property. It seems annoying to have to constantly case-split on a sign bit. I guess a lower-inductive representation could take advantage of the fact that the 2-adic representation of an integer other than 0 or -1 has a unique largest digit that differs from all larger digits, i.e. it's either ...0000 (i.e. 0) ...1111 (i.e. -1) ...0001 + arbitrary bit string ...1110 + arbitrary bit string This involves more case splits when defining arithmetic, but it would probably be an easy set to show that the HIT one is equivalent to. On Thu, Mar 4, 2021 at 7:02 PM Jason Gross <firstname.lastname@example.org> wrote: > > Note that the Coq standard library Z is a binary representation of integers and Z.testbit gives access to the infinite twos-compliment representation. Of course, it makes use of case-distinctions on sign to define it, but you go bit-by-bit; if the number is negative, you just invert the bit before returning it. Is there something you're after by having the representation not encode sign bits separately? > > On Thu, Mar 4, 2021, 21:27 Michael Shulman <email@example.com> wrote: >> >> On Thu, Mar 4, 2021 at 3:16 PM Nicolai Kraus <firstname.lastname@example.org> wrote: >> > I'm not sure what the precise thing is that you're looking for because, without further specification, any standard definition of Z would qualify :-) >> >> Yes, that seems to be what Martin suggested too with ℕ + ℕ. It seemed >> to me as though the distance between ℕ + ℕ and my ℤ is greater than >> the distance between his 𝔹 and 𝔹', but maybe not in any important >> way. >> >> > The HIT is neat, but wouldn't it in practice behave pretty similar to a standard representation via binary lists? E.g. something like Unit + Bool * List(Bool), where inl(*) is zero, the first Bool is the sign, and you add a 1 in front of the list in order to get a positive integer. What's the advantage of the HIT - maybe one can avoid case distinctions? >> >> Is there a non-HIT binary representation that can be interpreted as >> two's-complement (thereby avoiding case distinctions on sign)? I >> haven't been able to figure out a way to do that with mere lists of >> booleans. >> >> -- >> You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. >> To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheoryemail@example.com. >> To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAOvivQwtAMVnOG7D_A_s1EMAum4fv_x945MLB%2B01Y_pMdEKC2w%40mail.gmail.com. > > -- > You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. > To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheoryfirstname.lastname@example.org. > To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAKObCaqiyUcB%2BFrbvPmR-eS5ZMsb2CTVCtVbAYZeMUcOzCpmbA%40mail.gmail.com. -- You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheoryemail@example.com. To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAOvivQxy2EJNScHu9Y2U%3DGLiHDrDxDq-Kg8Dz9TrFk3ZepiW8Q%40mail.gmail.com.
prev parent reply other threads:[~2021-03-05 4:41 UTC|newest] Thread overview: 8+ messages / expand[flat|nested] mbox.gz Atom feed top 2021-03-04 20:43 Michael Shulman 2021-03-04 21:11 ` Martin Escardo 2021-03-04 22:05 ` Michael Shulman 2021-03-04 22:42 ` Martin Escardo 2021-03-04 23:16 ` Nicolai Kraus 2021-03-05 2:27 ` Michael Shulman 2021-03-05 3:02 ` Jason Gross 2021-03-05 4:41 ` Michael Shulman [this message]
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to='CAOvivQxy2EJNScHu9Y2U=GLiHDrDxDq-Kg8Dz9TrFk3ZepiW8Q@mail.gmail.com' \ --firstname.lastname@example.org \ --email@example.com \ --firstname.lastname@example.org \ --email@example.com \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: link
Discussion of Homotopy Type Theory and Univalent Foundations This inbox may be cloned and mirrored by anyone: git clone --mirror https://inbox.vuxu.org/hott # If you have public-inbox 1.1+ installed, you may # initialize and index your mirror using the following commands: public-inbox-init -V1 hott hott/ https://inbox.vuxu.org/hott \ firstname.lastname@example.org public-inbox-index hott Example config snippet for mirrors. Newsgroup available over NNTP: nntp://inbox.vuxu.org/vuxu.archive.hott AGPL code for this site: git clone https://public-inbox.org/public-inbox.git