PEP 303: Extend divmod() for Multiple Divisors
Thomas Bellman
Please give your comments. It can also be read on the web at
<URL: http://www.python.org/peps/pep-0303.html>.
(I have also written an implementation for this, but I want to
check it some more for reference count correctness before I post
it here or at SourceForge.)
PEP: 303
Title: Extend divmod() for Multiple Divisors
Version: $Revision: 1.2 $
Last-Modified: $Date: 2002/12/31 16:02:49 $
Author: Thomas Bellman <bellman+p...@lysator.liu.se>
Status: Draft
Type: Standards Track
Content-Type: text/plain
Created: 31-Dec-2002
Python-Version: 2.3
Post-History:
Abstract
This PEP describes an extension to the built-in divmod() function,
allowing it to take multiple divisors, chaining several calls to
divmod() into one.
Specification
The built-in divmod() function would be changed to accept multiple
divisors, changing its signature from divmod(dividend, divisor) to
divmod(dividend, *divisors). The dividend is divided by the last
divisor, giving a quotient and a remainder. The quotient is then
divided by the second to last divisor, giving a new quotient and
remainder. This is repeated until all divisors have been used,
and divmod() then returns a tuple consisting of the quotient from
the last step, and the remainders from all the steps.
A Python implementation of the new divmod() behaviour could look
like:
def divmod(dividend, *divisors):
modulos = ()
q = dividend
while divisors:
q,r = q.__divmod__(divisors[-1])
modulos = (r,) + modulos
divisors = divisors[:-1]
return (q,) + modulos
Motivation
Occasionally one wants to perform a chain of divmod() operations,
calling divmod() on the quotient from the previous step, with
varying divisors. The most common case is probably converting a
number of seconds into weeks, days, hours, minutes and seconds.
This would today be written as:
def secs_to_wdhms(seconds):
m,s = divmod(seconds, 60)
h,m = divmod(m, 60)
d,h = divmod(h, 24)
w,d = divmod(d, 7)
return (w,d,h,m,s)
This is tedious and easy to get wrong each time you need it.
If instead the divmod() built-in is changed according the proposal,
the code for converting seconds to weeks, days, hours, minutes and
seconds then become
def secs_to_wdhms(seconds):
w,d,h,m,s = divmod(seconds, 7, 24, 60, 60)
return (w,d,h,m,s)
which is easier to type, easier to type correctly, and easier to
read.
Other applications are:
- Astronomical angles (declination is measured in degrees, minutes
and seconds, right ascension is measured in hours, minutes and
seconds).
- Old British currency (1 pound = 20 shilling, 1 shilling = 12 pence)
- Anglo-Saxon length units: 1 mile = 1760 yards, 1 yard = 3 feet,
1 foot = 12 inches.
- Anglo-Saxon weight units: 1 long ton = 160 stone, 1 stone = 14
pounds, 1 pound = 16 ounce, 1 ounce = 16 dram
- British volumes: 1 gallon = 4 quart, 1 quart = 2 pint, 1 pint
= 20 fluid ounces
Rationale
The idea comes from APL, which has an operator that does this. (I
don't remember what the operator looks like, and it would probably
be impossible to render in ASCII anyway.)
The APL operator takes a list as its second operand, while this
PEP proposes that each divisor should be a separate argument to
the divmod() function. This is mainly because it is expected that
the most common uses will have the divisors as constants right in
the call (as the 7, 24, 60, 60 above), and adding a set of
parentheses or brackets would just clutter the call.
Requiring an explicit sequence as the second argument to divmod()
would seriously break backwards compatibility. Making divmod()
check its second argument for being a sequence is deemed to be too
ugly to contemplate. And in the case where one *does* have a
sequence that is computed other-where, it is easy enough to write
divmod(x, *divs) instead.
Requiring at least one divisor, i.e rejecting divmod(x), has been
considered, but no good reason to do so has come to mind, and is
thus allowed in the name of generality.
Calling divmod() with no divisors should still return a tuple (of
one element). Code that calls divmod() with a varying number of
divisors, and thus gets a return value with an "unknown" number of
elements, would otherwise have to special case that case. Code
that *knows* it is calling divmod() with no divisors is considered
to be too silly to warrant a special case.
Processing the divisors in the other direction, i.e dividing with
the first divisor first, instead of dividing with the last divisor
first, has been considered. However, the result comes with the
most significant part first and the least significant part last
(think of the chained divmod as a way of splitting a number into
"digits", with varying weights), and it is reasonable to specify
the divisors (weights) in the same order as the result.
The inverse operation:
def inverse_divmod(seq, *factors):
product = seq[0]
for x,y in zip(factors, seq[1:]):
product = product * x + y
return product
could also be useful. However, writing
seconds = (((((w * 7) + d) * 24 + h) * 60 + m) * 60 + s)
is less cumbersome both to write and to read than the chained
divmods. It is therefore deemed to be less important, and its
introduction can be deferred to its own PEP. Also, such a
function needs a good name, and the PEP author has not managed to
come up with one yet.
Calling divmod("spam") does not raise an error, despite strings
supporting neither division nor modulo. However, unless we know
the other object too, we can't determine whether divmod() would
work or not, and thus it seems silly to forbid it.
Backwards Compatibility
Any module that replaces the divmod() function in the __builtin__
module, may cause other modules using the new syntax to break. It
is expected that this is very uncommon.
Code that expects a TypeError exception when calling divmod() with
anything but two arguments will break. This is also expected to
be very uncommon.
No other issues regarding backwards compatibility are known.
Reference Implementation
Not finished yet, but it seems a rather straightforward
new implementation of the function builtin_divmod() in
Python/bltinmodule.c
Copyright
This document has been placed in the public domain.
--
Thomas Bellman, Lysator Computer Club, Linköping University, Sweden
"Adde parvum parvo magnus acervus erit" ! bellman @ lysator.liu.se
(From The Mythical Man-Month) ! Make Love -- Nicht Wahr!
"Martin v. Löwis"
> This PEP proposes extending divmod() to accept multiple divisors.
> Please give your comments. It can also be read on the web at
> <URL: http://www.python.org/peps/pep-0303.html>.
I like it; it looks like a straight-forward extension to me (although
the description is confusing to read - it is not immediately clear why
starting with the right-most divisor is the right thing).
Regards,
Martin
Thomas Bellman
> I like it; it looks like a straight-forward extension to me (although
> the description is confusing to read - it is not immediately clear why
> starting with the right-most divisor is the right thing).
Thanks. I agree that the description is a bit dense and difficult
to follow. If anyone have suggestions on how to describe it more
clearly, I am eager to hear them.
I was hoping that the reason for the order of the divisors was
made clear in the Rationale section. Basically, the order just
*felt* right when using it. divmod(seconds, 7, 24, 60, 60)
came more naturaly to me than divmod(seconds, 60, 60, 24, 7).
--
Thomas Bellman, Lysator Computer Club, Linköping University, Sweden
"Don't worry about the world coming to an end ! bellman @ lysator.liu.se
today. It's already tomorrow in Australia." ! Make Love -- Nicht Wahr!
Andrew Dalke
> I was hoping that the reason for the order of the divisors was
> made clear in the Rationale section. Basically, the order just
> *felt* right when using it. divmod(seconds, 7, 24, 60, 60)
> came more naturaly to me than divmod(seconds, 60, 60, 24, 7).
I agree with Martin, I have a preference for the order to be
the other way. It comes from thinking about "okay, divide by
seconds then minutes then hours then days then weeks" like I
would if I was using divmod by hand.
OTOH, I think your preference comes from the way you want
the output to read, since it's easier to think of the larger
terms before the smaller ones, as with
w, d, h, m, s = divmod(seconds, 7, 24, 60, 60)
compare that to the alternates of
s, m, h, d, w = divmod(seconds, 60, 60, 24, 7)
w, d, h, m, s = divmod(seconds, 60, 60, 24, 7)
Looking at the standard library, I see use case for chained
divmods which may help, since it doesn't bias matters
by using well-known variable names or values
a, x = divmod(a, 30268)
a, y = divmod(a, 30306)
a, z = divmod(a, 30322)
self._seed = int(x)+1, int(y)+1, int(z)+1
The way I would expect to see it rewritten is
x, y, z, a = divmod(a, 30268, 30306, 30322)
However, you would want it rewritten
a, z, y, x = divmod(a, 30322, 30306, 30268)
This seems backwards to me.
>>> start = 123654789555
>>> a = start
>>> a, x = divmod(a, 30268)
>>> a, y = divmod(a, 30306)
>>> a, z = divmod(a, 30322)
>>> x, y, z, a
(21115L, 24326L, 134L, 0L)
>>> def new_divmod(dividend, *divisors):
... modulos = ()
... q = dividend
... while divisors:
... q,r = q.__divmod__(divisors[-1])
... modulos = (r,) + modulos
... divisors = divisors[:-1]
... return (q,) + modulos
...
>>> new_divmod(start, 30268, 30306, 30322)
(0L, 134L, 17051L, 5845L)
>>> new_divmod(start, 30322, 30306, 30268)
(0L, 134L, 24326L, 21115L)
>>>
Andrew
da...@dalkescientific.com
Bjorn Pettersen
> Martin v. Löwis <mar...@v.loewis.de> wrote:
>
> > I like it; it looks like a straight-forward extension to me (although
> > the description is confusing to read
>
> I was hoping that the reason for the order of the divisors
> was made clear in the Rationale section. Basically, the order just
> *felt* right when using it. divmod(seconds, 7, 24, 60, 60)
> came more naturaly to me than divmod(seconds, 60, 60, 24, 7).
I'm having problems understanding the description too... Maybe you could explore _why_ it feels right to you -- as it stands I'd probably have to look up the order every time I wanted to use it...
-- bjorn
"Martin v. Löwis"
> I agree with Martin, I have a preference for the order to be
> the other way. It comes from thinking about "okay, divide by
> seconds then minutes then hours then days then weeks" like I
> would if I was using divmod by hand.
I didn't really mean that the order is wrong: I do agree with Thomas
that performing the division starting from the right end is fine.
I was merely complaining about the words that explain this.
Of course, since Guido considers the entire feature as bloat, changing
it might not be useful, anymore.
Regards,
Martin
"Martin v. Löwis"
> I'm having problems understanding the description too... Maybe you could explore
> _why_ it feels right to you -- as it stands I'd probably have to look up the
> order every time I wanted to use it...
The use case for this feature will yield values in some (irregular)
positioning system (e.g. days, hours, minutes, seconds). It is common to
list such values with the most significant digit (days) first, and it is
(IMO) intuitive if the bases are listed in the same order (i.e. 24, 60,
60). The computation will start from the right end, just as it does in a
regular positioning system (445 decimal in base 16: divmod(445, 16) =>
(27, 13), so the last digit is 13; divmod(27, 16) => (1, 11)
-> 445 == 0x1BD).
Regards,
Martin
Andrew Dalke
> The use case for this feature will yield values in some (irregular)
> positioning system (e.g. days, hours, minutes, seconds). It is common to
> list such values with the most significant digit (days) first, and it is
> (IMO) intuitive if the bases are listed in the same order (i.e. 24, 60,
> 60).
Looking at my local installation, I found three places
with chained divmod calls.
random.py
a, x = divmod(a, 30268)
a, y = divmod(a, 30306)
a, z = divmod(a, 30322)
whrandom.py
t, x = divmod(t, 256)
t, y = divmod(t, 256)
t, z = divmod(t, 256)
ZEO/simul.py
mm, ss = divmod(secs, 60)
hh, mm = divmod(mm, 60)
What surprised me is that mxDateTime does *not* use chained
divmods. That is, the program which I expect would need this
feature the most, doesn't need it.
Instead, it has
year = int((1.0 * absdate) / 365.2425)
(plus some twiddling to get it right)
...
inttime = int(abstime)
hour = inttime / 3600
minute = (inttime % 3600) / 60
second = abstime - 1.0 * (hour*3600 + minute*60)
None of my code uses divmod -- I usually forgot about it
and go for the /% solution too. ;)
Andrew
da...@dalkescientific.com
Erik Max Francis
> Abstract
>
> This PEP describes an extension to the built-in divmod() function,
> allowing it to take multiple divisors, chaining several calls to
> divmod() into one.
Provided backward compatibility is strictly maintained, sounds fine with
me.
...
> Rationale
>
> The idea comes from APL, which has an operator that does this. (I
> don't remember what the operator looks like, and it would probably
> be impossible to render in ASCII anyway.)
Oh boy oh boy! I actually know this one. It's an operator called
encode, which looks like a stylized T (you know, in the same way that
the "for every" symbol looks like a stylized inverted A). (The decode
operator, which does the reverse operation, looks like an inverted T.)
I don't know what the equivalent operator is in J, but no doubt there is
one.
> The APL operator takes a list as its second operand, ...
Actually, the APL operator takes the list of moduli as the left
argument.
I knew that reading that APL book (a language I am almost certain never
to use in the real world in my entire life) last month would pay off!
Now I'll be rich and famous!
--
Erik Max Francis / m...@alcyone.com / http://www.alcyone.com/max/
__ San Jose, CA, USA / 37 20 N 121 53 W / &tSftDotIotE
/ \ All your slick moves / They were once innocent moves
\__/ Sade
Bosskey.net: Quake III Arena / http://www.bosskey.net/q3a/
A personal guide to Quake III Arena.
John Roth
"Thomas Bellman" <bellman+p...@lysator.liu.se> wrote in message
news:ausiq8$egi$1...@news.island.liu.se...
> This PEP proposes extending divmod() to accept multiple divisors.
> Please give your comments. It can also be read on the web at
> <URL: http://www.python.org/peps/pep-0303.html>.
I want to object to this one strongly, on the basis that it is
a special case of something that, if it's useful at all, should
be generalized to include all of the operators.
Erik Mac Francis' comment about the APL encode operator
sounds about right, although I'd much prefer that thinking
go in the direction of functional languages.
I don't find the use cases very compelling. Sure, they exist,
but how many of us actually use chained division for those
conversions in every day life rather than use a library
module? And how many of those uses are actually
the performance bottleneck in the system?
As far as the nuts and bolts go, the operand should be
a sequence, not simply strung out as operands. There are
several reasons for this, but the major one is consistency:
if the result is a list, then the input operand should also be
a list.
John Roth
Paul Rubin
> I want to object to this one strongly, on the basis that it is
> a special case of something that, if it's useful at all, should
> be generalized to include all of the operators.
Not a bad idea. There's no reason for operator.plus(3,4,5) to
throw an exception instead of returning 12.
> Erik Mac Francis' comment about the APL encode operator
> sounds about right, although I'd much prefer that thinking
> go in the direction of functional languages.
> As far as the nuts and bolts go, the operand should be
> a sequence, not simply strung out as operands. There are
> several reasons for this, but the major one is consistency:
> if the result is a list, then the input operand should also be
> a list.
That makes no sense. Imagine a function that returns the
factorization of a number, e.g. the factors of 30 are 2, 3, and 5.
It's natural and obvious for factor(30) to return the list (3,4,5).
Why on earth should its argument be a list?
John Roth
"Paul Rubin" <phr-n...@NOSPAMnightsong.com> wrote in message
news:7xwulpu...@ruckus.brouhaha.com...
Ah, but that's a different situation. For a factorization, you've
got a single number going in. For the suggested usage, you've
got a 1 to 1 correspondance between the input numbers and
the output numbers: each divisor produces one element of the
output list (with a possible final remainder.)
I wouldn't expect a factor function to have a list input.
John Roth
>
Anton Vredegoor
<bellman+p...@lysator.liu.se> wrote:
> A Python implementation of the new divmod() behaviour could look
> like:
>
> def divmod(dividend, *divisors):
> modulos = ()
> q = dividend
> while divisors:
> q,r = q.__divmod__(divisors[-1])
> modulos = (r,) + modulos
> divisors = divisors[:-1]
> return (q,) + modulos
>
This would make a short permutation algorithm possible. Very
seductive. Maybe it's too good and we shouldn't do it? :-)
I have experimented with divmod too, and turned it into a kind of
generalized threshold index finder.
The divisors argument would become a function that would generate a
sequence. Divmod would return the index of the element just before the
element that is bigger than dividend, and the difference between this
element and dividend.
If the sequence would consist of a list of numbers that increases by a
constant amount, the original divmod would be mimicked.
I think that what is proposed in PEP 303 has the merit of being very
useful at a short term. In the long term it might become a hindrance
to other interpretations of what a divmod really should be. It seems
not to preclude the generalization described above because the ideas
are orthogonal. I am in favor of this PEP.
+1
Regards,
Anton.
Here's the short permutation algorithm for PEP 303:
def perm(i,s):
L = list(s)
return "".join([L.pop(x) for x in\
divmod(i,*range(len(L)-1,0,-1))])
def test():
for i in range(24):
print perm (i,"abcd")
if __name__=='__main__':
test()
Anders J. Munch
> Here's the short permutation algorithm for PEP 303:
>
> def perm(i,s):
> L = list(s)
> return "".join([L.pop(x) for x in\
> divmod(i,*range(len(L)-1,0,-1))])
<Cognitive overload. Core dumped.>
-0.1 on PEP303.
It's a pure and elegant extension, but it suspect it will be so rarely
used that it will effectively become an obfuscation device ;-).
- Anders
Thomas Bellman
> OTOH, I think your preference comes from the way you want
> the output to read, since it's easier to think of the larger
> terms before the smaller ones, as with
> w, d, h, m, s = divmod(seconds, 7, 24, 60, 60)
> compare that to the alternates of
> s, m, h, d, w = divmod(seconds, 60, 60, 24, 7)
> w, d, h, m, s = divmod(seconds, 60, 60, 24, 7)
Correct, I think the first version is easiest to think of and to
read. The last version I think would be quite awkward to read,
since the result comes in the opposite order from the parameters:
you specify the number of days per week last, but the weeks and
days come out first.
There is also the matter of backward compatibility: divmod
currently returns the quotient first, and the remainder second.
For the sake of consistensy, one absolutely wants the quotient to
come first regardless of the number of divisors; doing otherwise
would be quite awful. That rules out using the order
s, m, h, d, w = divmod(seconds, 60, 60, 24, 7)
That actually leaves us with another alternative, which you
didn't suggest:
w, s, m, h, d = divmod(seconds, 60, 60, 24, 7)
But that also feels weird to read.
> a, x = divmod(a, 30268)
> a, y = divmod(a, 30306)
> a, z = divmod(a, 30322)
> self._seed = int(x)+1, int(y)+1, int(z)+1
> The way I would expect to see it rewritten is
> x, y, z, a = divmod(a, 30268, 30306, 30322)
> However, you would want it rewritten
> a, z, y, x = divmod(a, 30322, 30306, 30268)
> This seems backwards to me.
Yes, it might feel backwards. However, reading more of the
code from the WhichmanHill generator in random.py, I get the
impression that there is no inherent meaning in the incoming
value a. And the final value of a, after the three divmod()
calls, is just thrown away.
But yes, rewriting that code to use a generalized divmod() is
slightly less straightforward.
--
Thomas Bellman, Lysator Computer Club, Linköping University, Sweden
"God is real, but Jesus is an integer." ! bellman @ lysator.liu.se
Thomas Bellman
> Thomas Bellman wrote:
>> The idea comes from APL, which has an operator that does this. (I
>> don't remember what the operator looks like, and it would probably
>> be impossible to render in ASCII anyway.)
> Oh boy oh boy! I actually know this one. It's an operator called
> encode, which looks like a stylized T (you know, in the same way that
Hmm, on python-dev I have got someone saying it's called 'base',
and someone else thinks it's called 'radix'.
> Actually, the APL operator takes the list of moduli as the left
> argument.
> I knew that reading that APL book (a language I am almost certain never
> to use in the real world in my entire life) last month would pay off!
Ah, I see. It was about a decade ago that I read a book on APL,
so my memory is a bit hazy with the details. :-)
--
Thomas Bellman, Lysator Computer Club, Linköping University, Sweden
"I don't think [that word] means what you ! bellman @ lysator.liu.se
think it means." -- The Princess Bride ! Make Love -- Nicht Wahr!
Thomas Bellman
> I want to object to this one strongly, on the basis that it is
> a special case of something that, if it's useful at all, should
> be generalized to include all of the operators.
Yes, I have had thoughts about that too. However, divmod differs
from the other operators in one important aspect: it returns
*two* values. The other operators can easily be chained by using
reduce(); divmod can't (easily).
And there is actually another aspect that is different: divmod
isn't an operator, but a function. :-)
> I don't find the use cases very compelling. Sure, they exist,
> but how many of us actually use chained division for those
> conversions in every day life rather than use a library
> module?
I do. :-) And more importantly, I think that even library code
should be allowed to read well.
> And how many of those uses are actually
> the performance bottleneck in the system?
The motivation for this extension is clarity, not speed.
> As far as the nuts and bolts go, the operand should be
> a sequence, not simply strung out as operands. There are
> several reasons for this, but the major one is consistency:
> if the result is a list, then the input operand should also be
> a list.
If I was suggesting a new function, I would probably agree with
you. However, I'm proposing to extend an existing function, and
the API for a single divisor is already set in stone. I think it
would be a very bad idea for divmod to change its behaviour based
on whether the second argument was a sequence or not.
--
Thomas Bellman, Lysator Computer Club, Linköping University, Sweden
"You cannot achieve the impossible without ! bellman @ lysator.liu.se
attempting the absurd." ! Make Love -- Nicht Wahr!
Erik Max Francis
> Hmm, on python-dev I have got someone saying it's called 'base',
> and someone else thinks it's called 'radix'.
According to the book I used (_APL: An Interactive Approach_) it's also
called "base value." I'm not really sure if APL operators really have
any official names beyond their symbols, so it might all be academic
anyway.
--
Erik Max Francis / m...@alcyone.com / http://www.alcyone.com/max/
__ San Jose, CA, USA / 37 20 N 121 53 W / &tSftDotIotE
/ \ A man can stand a lot as long as he can stand himself.
\__/ Axel Munthe
Lsystem / http://www.alcyone.com/pyos/lsystem/
A Lindenmayer systems explorer in Python.