Discussion of Homotopy Type Theory and Univalent Foundations
 help / color / mirror / Atom feed
From: Michael Shulman <shulman@sandiego.edu>
To: "HomotopyTypeTheory@googlegroups.com"
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.)


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 HomotopyTypeTheory+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAOvivQw4h46DtKATiwUvm%3DL%3DjEGng2XdYGAhKbi7fhis%2By_TPw%40mail.gmail.com.

             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:

* 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' \
    --to=shulman@sandiego.edu \
    --cc=homotopytypetheory@googlegroups.com \


* 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 \
	public-inbox-index hott

Example config snippet for mirrors.
Newsgroup available over NNTP:

AGPL code for this site: git clone https://public-inbox.org/public-inbox.git