From: Michael Shulman <email@example.com> To: "HomotopyTypeTheory@googlegroups.com" <firstname.lastname@example.org> Subject: [HoTT] two's complement integers Date: Thu, 4 Mar 2021 12:43:28 -0800 Message-ID: <CAOvivQw4h46DtKATiwUvm=L=jEGng2XdYGAhKbi7fhis+y_TPw@mail.gmail.com> (raw) Has anyone considered the following HIT definition of the integers? data ℤ : Type where zero : ℤ -- 0 negOne : ℤ -- -1 dbl : ℤ → ℤ -- n ↦ 2n sucDbl : ℤ → ℤ -- n ↦ 2n+1 dblZero : dbl zero ≡ zero -- 2·0 = 0 sucDblNegOne : sucDbl negOne ≡ negOne -- 2·(-1)+1 = -1 The idea is that it's an arbitrary-precision version of little-endian two's-complement, with sucDbl and dbl representing 1 and 0 respectively, and negOne and zero representing the highest-order sign bit 1 and 0 respectively. Thus for instance sucDbl (dbl (sucDbl (sucDbl zero))) = 01101 = 13 dbl (sucDbl (dbl (dbl negOne))) = 10010 = -14 The two path-constructors enable arbitrary expansion of the precision, e.g. 01101 = 001101 = 0001101 = ... 10010 = 110010 = 1110010 = ... This seems like a fairly nice definition: it should already be a set without any truncation, it's binary rather than unary, and the arithmetic operations can be defined in the usual digit-by-digit way without splitting into cases by sign. Mathematically speaking, it represents integers by their images in the 2-adic integers, with zero and negOne representing infinite tails of 0s and 1s respectively. (An arbitrary 2-adic integer, of course, is just a stream of bits.) Best, Mike -- 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/CAOvivQw4h46DtKATiwUvm%3DL%3DjEGng2XdYGAhKbi7fhis%2By_TPw%40mail.gmail.com.
next reply other threads:[~2021-03-04 20:43 UTC|newest] Thread overview: 8+ messages / expand[flat|nested] mbox.gz Atom feed top 2021-03-04 20:43 Michael Shulman [this message] 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
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='CAOvivQw4h46DtKATiwUvm=L=jEGng2XdYGAhKbi7fhis+y_TPw@mail.gmail.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