Discussion of Homotopy Type Theory and Univalent Foundations
 help / color / mirror / Atom feed
* [HoTT] two's complement integers
@ 2021-03-04 20:43 Michael Shulman
  2021-03-04 21:11 ` Martin Escardo
  0 siblings, 1 reply; 8+ messages in thread
From: Michael Shulman @ 2021-03-04 20:43 UTC (permalink / raw)
  To: HomotopyTypeTheory@googlegroups.com

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 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.

^ permalink raw reply	[flat|nested] 8+ messages in thread

end of thread, other threads:[~2021-03-05  4:41 UTC | newest]

Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-03-04 20:43 [HoTT] two's complement integers 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 is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).