[OT] Number theory [Was: A use for integer quotients]

[Bengt Richter]

On Sun, 29 Jul 2001 13:14:12 GMT, ullrich at math.okstate.edu (David C. Ullrich) wrote:

>On Sat, 28 Jul 2001 19:34:46 +0100, Gareth.McCaughan at pobox.com (Gareth
>McCaughan) wrote:
>
and
>>David Ullrich wrote:
>>
[...lots of set stuff...]>
>>This has long ceased to have anything to do with Python.
>>I suggest that we take it to e-mail or drop it entirely.
>
>Simply dropping it seems the sensible option, since
>neither of us is actually saying anything the other
>doesn't know - my original butting in was a just for
>the record thing.
>
>(Did they change the rules recently? Don't recall
>relevance to Python being a criterion here...)
>
>>(But if you prefer continuing in c.l.py, I don't mind.)
>
Something that might be relevant to Python: I have been using
bit twiddling operators and arithmetic operators for decades,
mostly putatively on things referred to as two's complement
integers, represented by an ordered sequence of bits,
but also other entities.

ISTM that thinking of bit twiddling as operating on integers
is not clean conceptually. I.e., I think there is an implicit
coercion to a set type for the twiddle operation and then implicitly
back to integer again when supposedly twiddling two integers
with a binary twiddling operation (same for unary, of course).

ISTM if i an j were taken as integers per se, 'i | j' would create a
set of two integers. Obviously the '|' operation is not referring
to the integers as integer-set members. I think that ought to be
made clear, but I am not sure about the best way to talk about
what's really happening. I'm grasping after something about
ordered-binary-coefficient-set-ordinal sets, or something
like that, I think. More below ;-)

PEP 218 introduces sets to the language. I think it would be good to say
something there too about integers-as-sets (and maybe have explicit
conversions to/from integers, and ordered sequences of integers such
as convert nicely to strings) (I am sending a Bcc to the author
gvwilson at ddj.com, in case he's interested in this).

If some paragraphs on this belonged in the docs (by URL link ;-)
where bit twiddle operations are explained, it sounds like you
guys would be the ones to get it officially right. (Or immediately know
an existing reference ;-)

BTW, I got to thinking about this because of a post mentioning
the '<<' operator as being uniquely bit twiddling in nature.
Yet ISTM it really does have an aritmetic meaning as well, i.e.,
'*2**' and '<<' are often interchangeable in code, and both
senses are used (even if sometimes intended in the alternate sense ;-).

So what is the best way to talk about a binary-represented integer
in the abstract? A vector of coefficients for radix powers doesn't
evoke the usages that ignore the radix powers, i.e., treating 1-or-0
coefficients as existence booleans for set elements identified by
position number (or *being* position number).

BTW, note the usefulness of boolean-as-integer returned from
comparison operators, if you want to be picky about plurals:

    print "There %s %d error%s." % ( ['were','was'][n==1], n, 's'*(n!=1) ) 

Sets seem a lot like dictionaries with values restricted to true/false.
Less generally, don't-care/no-key is sometimes useful.

You could convert an integer into a dictionary of  bitposition:bitvalue
pairs and back pretty reliably, so an integer could have a standard
conversion to a dictionary. Of course, you would probably hide
the implementation for efficiency ;-)

You could do a dictionary for numbers with non-binary radix, revealing that you
really have radixPower:coefficient pairs, and in the binary case are using
the pairs in an elementId:existence sense.

Side thought: You could write a Python program for addition etc. that would operate
on integers represented as sets. I wonder if this sort of thing could help students
understand what is going on in the hardware. Serial adder as set comprehension?

Time flies when you're having fun ('cause timing flies is a real
nuisance if you aren't having fun ;-)