recursion depth problem
hello, i have a small function which mimics binary counting. it runs fine as long as the input is not too long, but if i give it input longer than 8 characters it gives RuntimeError: maximum recursion depth exceeded in cmp i'm not too sure what i am doing improperly. is there really a lot of recursion in this code? == import sys def ch4(item, n=0): if n < len(item): if item[n] == '0': item[n] = '1' print ''.join(item) ch4(item) elif item[n] == '1': item[n] = '0' ch4(item, n+1) ch4(list(sys.argv[1])) == this function expects input in the form of a string of zeros, like this: python test-bin.py and is expected to output a list of permutations like this: $ python test-bin.py 1000 0100 1100 0010 1010 0110 1110 0001 1001 0101 1101 0011 1011 0111 thanks for all help! sincerely, proctor -- http://mail.python.org/mailman/listinfo/python-list
Re: recursion depth problem
On Apr 22, 2007, at 1:49 PM, proctor wrote: > i have a small function which mimics binary counting. it runs fine as > long as the input is not too long, but if i give it input longer than > 8 characters it gives > > RuntimeError: maximum recursion depth exceeded in cmp > > i'm not too sure what i am doing improperly. is there really a lot of > recursion in this code? > > == > > import sys > > def ch4(item, n=0): > if n < len(item): > if item[n] == '0': > item[n] = '1' > print ''.join(item) > ch4(item) > elif item[n] == '1': > item[n] = '0' > ch4(item, n+1) > > ch4(list(sys.argv[1])) > > == Yes. There really is *that* much recursion in that code. 502 levels with input length of 8 characters, 1013 with 9 characters, 2035 with 10 characters... There's a pattern there ;-) -- http://mail.python.org/mailman/listinfo/python-list
Re: recursion depth problem
On Apr 22, 1:24 pm, Michael Bentley <[EMAIL PROTECTED]> wrote: > On Apr 22, 2007, at 1:49 PM, proctor wrote: > > > > > i have a small function which mimics binary counting. it runs fine as > > long as the input is not too long, but if i give it input longer than > > 8 characters it gives > > > RuntimeError: maximum recursion depth exceeded in cmp > > > i'm not too sure what i am doing improperly. is there really a lot of > > recursion in this code? > > > == > > > import sys > > > def ch4(item, n=0): > >if n < len(item): > >if item[n] == '0': > >item[n] = '1' > >print ''.join(item) > >ch4(item) > >elif item[n] == '1': > >item[n] = '0' > >ch4(item, n+1) > > > ch4(list(sys.argv[1])) > > > == > > Yes. There really is *that* much recursion in that code. 502 levels > with input length of 8 characters, 1013 with 9 characters, 2035 with > 10 characters... There's a pattern there ;-) ok, thanks michael! is there a way to avoid it here? how could i write this better, (if at all)? proctor. -- http://mail.python.org/mailman/listinfo/python-list
Re: recursion depth problem
proctor wrote:
> On Apr 22, 1:24 pm, Michael Bentley <[EMAIL PROTECTED]> wrote:
>> On Apr 22, 2007, at 1:49 PM, proctor wrote:
>>
>>
>>
>>> i have a small function which mimics binary counting. it runs fine as
>>> long as the input is not too long, but if i give it input longer than
>>> 8 characters it gives
>>> RuntimeError: maximum recursion depth exceeded in cmp
>>> i'm not too sure what i am doing improperly. is there really a lot of
>>> recursion in this code?
>>> ==
>>> import sys
>>> def ch4(item, n=0):
>>>if n < len(item):
>>>if item[n] == '0':
>>>item[n] = '1'
>>>print ''.join(item)
>>>ch4(item)
>>>elif item[n] == '1':
>>>item[n] = '0'
>>>ch4(item, n+1)
>>> ch4(list(sys.argv[1]))
>>> ==
>> Yes. There really is *that* much recursion in that code. 502 levels
>> with input length of 8 characters, 1013 with 9 characters, 2035 with
>> 10 characters... There's a pattern there ;-)
>
> ok, thanks michael!
>
> is there a way to avoid it here? how could i write this better, (if
> at all)?
Google for permutation-like recipies:
http://www.google.com/search?q=Python+permutations
Use the code from the first hit::
>>> for x in xselections('01', 8):
... print ''.join(x)
...
0001
0010
...
1101
1110
Explaining to your teacher why your code uses generators when you
haven't been taught them yet is left as an exercise to the reader. ;-)
STeVe
--
http://mail.python.org/mailman/listinfo/python-list
Re: recursion depth problem
On Apr 22, 11:49 am, proctor <[EMAIL PROTECTED]> wrote: > hello, > > i have a small function which mimics binary counting. it runs fine as > long as the input is not too long, but if i give it input longer than > 8 characters it gives > > RuntimeError: maximum recursion depth exceeded in cmp > > i'm not too sure what i am doing improperly. is there really a lot of > recursion in this code? > > == > > import sys > > def ch4(item, n=0): > if n < len(item): > if item[n] == '0': > item[n] = '1' > print ''.join(item) > ch4(item) > elif item[n] == '1': > item[n] = '0' > ch4(item, n+1) > > ch4(list(sys.argv[1])) > > == > > this function expects input in the form of a string of zeros, like > this: > > python test-bin.py > > and is expected to output a list of permutations like this: > > $ python test-bin.py > 1000 > 0100 > 1100 > 0010 > 1010 > 0110 > 1110 > 0001 > 1001 > 0101 > 1101 > 0011 > 1011 > 0111 > > > thanks for all help! > > sincerely, > proctor If you just want to make it work as ischeck sys.setrecursionlimit() ~Sean -- http://mail.python.org/mailman/listinfo/python-list
Re: recursion depth problem
On Apr 22, 2:55 pm, [EMAIL PROTECTED] wrote: > On Apr 22, 11:49 am, proctor <[EMAIL PROTECTED]> wrote: > > > > > hello, > > > i have a small function which mimics binary counting. it runs fine as > > long as the input is not too long, but if i give it input longer than > > 8 characters it gives > > > RuntimeError: maximum recursion depth exceeded in cmp > > > i'm not too sure what i am doing improperly. is there really a lot of > > recursion in this code? > > > == > > > import sys > > > def ch4(item, n=0): > > if n < len(item): > > if item[n] == '0': > > item[n] = '1' > > print ''.join(item) > > ch4(item) > > elif item[n] == '1': > > item[n] = '0' > > ch4(item, n+1) > > > ch4(list(sys.argv[1])) > > > == > > > this function expects input in the form of a string of zeros, like > > this: > > > python test-bin.py > > > and is expected to output a list of permutations like this: > > > $ python test-bin.py > > 1000 > > 0100 > > 1100 > > 0010 > > 1010 > > 0110 > > 1110 > > 0001 > > 1001 > > 0101 > > 1101 > > 0011 > > 1011 > > 0111 > > > > > thanks for all help! > > > sincerely, > > proctor > > If you just want to make it work as ischeck > > sys.setrecursionlimit() > > ~Sean very nice. thanks sean. so is the structure of my original code unrescuable? i cannot rearrange it to bypass the recursion? proctor. -- http://mail.python.org/mailman/listinfo/python-list
Re: recursion depth problem
On Apr 22, 2:06 pm, Steven Bethard <[EMAIL PROTECTED]> wrote:
> proctor wrote:
> > On Apr 22, 1:24 pm, Michael Bentley <[EMAIL PROTECTED]> wrote:
> >> On Apr 22, 2007, at 1:49 PM, proctor wrote:
>
> >>> i have a small function which mimics binary counting. it runs fine as
> >>> long as the input is not too long, but if i give it input longer than
> >>> 8 characters it gives
> >>> RuntimeError: maximum recursion depth exceeded in cmp
> >>> i'm not too sure what i am doing improperly. is there really a lot of
> >>> recursion in this code?
> >>> ==
> >>> import sys
> >>> def ch4(item, n=0):
> >>>if n < len(item):
> >>>if item[n] == '0':
> >>>item[n] = '1'
> >>>print ''.join(item)
> >>>ch4(item)
> >>>elif item[n] == '1':
> >>>item[n] = '0'
> >>>ch4(item, n+1)
> >>> ch4(list(sys.argv[1]))
> >>> ==
> >> Yes. There really is *that* much recursion in that code. 502 levels
> >> with input length of 8 characters, 1013 with 9 characters, 2035 with
> >> 10 characters... There's a pattern there ;-)
>
> > ok, thanks michael!
>
> > is there a way to avoid it here? how could i write this better, (if
> > at all)?
>
> Google for permutation-like recipies:
>
> http://www.google.com/search?q=Python+permutations
>
> Use the code from the first hit::
>
> >>> for x in xselections('01', 8):
> ... print ''.join(x)
> ...
>
> 0001
> 0010
> ...
> 1101
> 1110
>
>
> Explaining to your teacher why your code uses generators when you
> haven't been taught them yet is left as an exercise to the reader. ;-)
>
> STeVe
this is really nice, thanks steve. much slicker than my code.
for interest sake: is my method unredeemable?
thanks very much!
sincerely,
proctor
--
http://mail.python.org/mailman/listinfo/python-list
Re: recursion depth problem
On Apr 22, 2007, at 4:08 PM, proctor wrote: > On Apr 22, 2:55 pm, [EMAIL PROTECTED] wrote: >> On Apr 22, 11:49 am, proctor <[EMAIL PROTECTED]> wrote: >> >> >> >>> hello, >> >>> i have a small function which mimics binary counting. it runs >>> fine as >>> long as the input is not too long, but if i give it input longer >>> than >>> 8 characters it gives >> >>> RuntimeError: maximum recursion depth exceeded in cmp >> >>> i'm not too sure what i am doing improperly. is there really a >>> lot of >>> recursion in this code? >> >>> == >> >>> import sys >> >>> def ch4(item, n=0): >>> if n < len(item): >>> if item[n] == '0': >>> item[n] = '1' >>> print ''.join(item) >>> ch4(item) >>> elif item[n] == '1': >>> item[n] = '0' >>> ch4(item, n+1) >> >>> ch4(list(sys.argv[1])) >> >>> == >> >>> this function expects input in the form of a string of zeros, like >>> this: >> >>> python test-bin.py >> >>> and is expected to output a list of permutations like this: >> >>> $ python test-bin.py >>> 1000 >>> 0100 >>> 1100 >>> 0010 >>> 1010 >>> 0110 >>> 1110 >>> 0001 >>> 1001 >>> 0101 >>> 1101 >>> 0011 >>> 1011 >>> 0111 >>> >> >>> thanks for all help! >> >>> sincerely, >>> proctor >> >> If you just want to make it work as ischeck >> >> sys.setrecursionlimit() >> >> ~Sean > > very nice. thanks sean. so is the structure of my original code > unrescuable? i cannot rearrange it to bypass the recursion? > Anything that can be done with recursion can be done without recursion. If you really wanted to mimic a binary counter, why not write a function that converts a number to binary? Then you could just count up from 0, printing the return from your binary conversion function... And the binary converter would be pretty easy too: just think of it as making change -- for a given number you just divide the number by each of [2 ** x for x in range(len(sys.argv[1]), 0, -1)] and append the string representations of the answers to a list and if the answer is 1, subtract that much from the number... -- http://mail.python.org/mailman/listinfo/python-list
Re: recursion depth problem
On Apr 22, 4:37 pm, Michael Bentley <[EMAIL PROTECTED]> wrote: > On Apr 22, 2007, at 4:08 PM, proctor wrote: > > > > > On Apr 22, 2:55 pm, [EMAIL PROTECTED] wrote: > >> On Apr 22, 11:49 am, proctor <[EMAIL PROTECTED]> wrote: > > >>> hello, > > >>> i have a small function which mimics binary counting. it runs > >>> fine as > >>> long as the input is not too long, but if i give it input longer > >>> than > >>> 8 characters it gives > > >>> RuntimeError: maximum recursion depth exceeded in cmp > > >>> i'm not too sure what i am doing improperly. is there really a > >>> lot of > >>> recursion in this code? > > >>> == > > >>> import sys > > >>> def ch4(item, n=0): > >>> if n < len(item): > >>> if item[n] == '0': > >>> item[n] = '1' > >>> print ''.join(item) > >>> ch4(item) > >>> elif item[n] == '1': > >>> item[n] = '0' > >>> ch4(item, n+1) > > >>> ch4(list(sys.argv[1])) > > >>> == > > >>> this function expects input in the form of a string of zeros, like > >>> this: > > >>> python test-bin.py > > >>> and is expected to output a list of permutations like this: > > >>> $ python test-bin.py > >>> 1000 > >>> 0100 > >>> 1100 > >>> 0010 > >>> 1010 > >>> 0110 > >>> 1110 > >>> 0001 > >>> 1001 > >>> 0101 > >>> 1101 > >>> 0011 > >>> 1011 > >>> 0111 > >>> > > >>> thanks for all help! > > >>> sincerely, > >>> proctor > > >> If you just want to make it work as ischeck > > >> sys.setrecursionlimit() > > >> ~Sean > > > very nice. thanks sean. so is the structure of my original code > > unrescuable? i cannot rearrange it to bypass the recursion? > > Anything that can be done with recursion can be done without > recursion. If you really wanted to mimic a binary counter, why not > write a function that converts a number to binary? > > Then you could just count up from 0, printing the return from your > binary conversion function... > > And the binary converter would be pretty easy too: just think of it > as making change -- for a given number you just divide the number by > each of [2 ** x for x in range(len(sys.argv[1]), 0, -1)] and append > the string representations of the answers to a list and if the answer > is 1, subtract that much from the number... cool... i'm going to have to think about this one... :-) proctor -- http://mail.python.org/mailman/listinfo/python-list
Re: recursion depth problem
Yes, you should use a for loop in this situation. Certain functional languages, such as Scheme and various LISP dialects allow for what is called "tail recursion" which effectively eliminates this problem by internally converting recursion to iteration. Python isn't really cut out for heavy recursive work, and the "Pythonic" way of doing things is through the lovely for loop. -- http://mail.python.org/mailman/listinfo/python-list
Re: recursion depth problem
On Apr 22, 5:05 pm, tac-tics <[EMAIL PROTECTED]> wrote: > Yes, you should use a for loop in this situation. > > Certain functional languages, such as Scheme and various LISP dialects > allow for what is called "tail recursion" which effectively eliminates > this problem by internally converting recursion to iteration. Python > isn't really cut out for heavy recursive work, and the "Pythonic" way > of doing things is through the lovely for loop. hi tac-tics, by using a for loop, do you mean in the same sense that the "xselections" function uses a for loop on the page: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/190465 ? or are you referring to a different technique for this? thanks for your help. i really appreciate it. proctor. -- http://mail.python.org/mailman/listinfo/python-list
Re: recursion depth problem
On Apr 22, 2007, at 5:47 PM, proctor wrote: > On Apr 22, 4:37 pm, Michael Bentley <[EMAIL PROTECTED]> wrote: >> On Apr 22, 2007, at 4:08 PM, proctor wrote: >> >> >> >>> On Apr 22, 2:55 pm, [EMAIL PROTECTED] wrote: On Apr 22, 11:49 am, proctor <[EMAIL PROTECTED]> wrote: >> > hello, >> > i have a small function which mimics binary counting. it runs > fine as > long as the input is not too long, but if i give it input longer > than > 8 characters it gives >> > RuntimeError: maximum recursion depth exceeded in cmp >> > i'm not too sure what i am doing improperly. is there really a > lot of > recursion in this code? >> > == >> > import sys >> > def ch4(item, n=0): > if n < len(item): > if item[n] == '0': > item[n] = '1' > print ''.join(item) > ch4(item) > elif item[n] == '1': > item[n] = '0' > ch4(item, n+1) >> > ch4(list(sys.argv[1])) >> > == >> > this function expects input in the form of a string of zeros, like > this: >> > python test-bin.py >> > and is expected to output a list of permutations like this: >> > $ python test-bin.py > 1000 > 0100 > 1100 > 0010 > 1010 > 0110 > 1110 > 0001 > 1001 > 0101 > 1101 > 0011 > 1011 > 0111 > >> > thanks for all help! >> > sincerely, > proctor >> If you just want to make it work as ischeck >> sys.setrecursionlimit() >> ~Sean >> >>> very nice. thanks sean. so is the structure of my original code >>> unrescuable? i cannot rearrange it to bypass the recursion? >> >> Anything that can be done with recursion can be done without >> recursion. If you really wanted to mimic a binary counter, why not >> write a function that converts a number to binary? >> >> Then you could just count up from 0, printing the return from your >> binary conversion function... >> >> And the binary converter would be pretty easy too: just think of it >> as making change -- for a given number you just divide the number by >> each of [2 ** x for x in range(len(sys.argv[1]), 0, -1)] and append >> the string representations of the answers to a list and if the answer >> is 1, subtract that much from the number... > > cool... i'm going to have to think about this one... :-) > he he... Run this snippet and see if it makes more sense: def binary(val, width): print '%10s = the sum of' % val for i in [2 ** x for x in range(width, 0, -1)]: a = val / i print ' ' * 13 + '%s * (2 ** %s)' % (a, i) val -= i * a binary(333, 8) -- http://mail.python.org/mailman/listinfo/python-list
Re: recursion depth problem
Oops! Note to self: *ALWAYS* try code before posting to a public forum :-( def binary(val, width): print '%10s = the sum of' % val for i in [2 ** x for x in range(width - 1, -1, -1)]: a = val / i print ' ' * 13 + '%s * (2 ** %s)' % (a, width) val -= i * a width -= 1 binary(233, 8) -- http://mail.python.org/mailman/listinfo/python-list
Re: recursion depth problem
On Apr 22, 5:51 pm, Michael Bentley <[EMAIL PROTECTED]> wrote: > Oops! Note to self: *ALWAYS* try code before posting to a public > forum :-( > > def binary(val, width): > print '%10s = the sum of' % val > for i in [2 ** x for x in range(width - 1, -1, -1)]: > a = val / i > print ' ' * 13 + '%s * (2 ** %s)' % (a, width) > val -= i * a > width -= 1 > > binary(233, 8) very cool. thanks a lot michael. very interesting. proctor. -- http://mail.python.org/mailman/listinfo/python-list
Re: recursion depth problem
On Apr 22, 5:51 pm, Dennis Lee Bieber <[EMAIL PROTECTED]> wrote:
> On Sun, 22 Apr 2007 17:37:05 -0500, Michael Bentley
> <[EMAIL PROTECTED]> declaimed the following in comp.lang.python:
>
> > Anything that can be done with recursion can be done without
> > recursion. If you really wanted to mimic a binary counter, why not
> > write a function that converts a number to binary?
>
> > Then you could just count up from 0, printing the return from your
> > binary conversion function...
>
> > And the binary converter would be pretty easy too: just think of it
> > as making change -- for a given number you just divide the number by
> > each of [2 ** x for x in range(len(sys.argv[1]), 0, -1)] and append
> > the string representations of the answers to a list and if the answer
> > is 1, subtract that much from the number...
>
> Or a simple lookup dictionary to convert from hex to binary, and use
> string interpolation to produce the hex...
>
> Might also make it more natural -- the original recursive loop is
> producing output with LSB on the left, most folks expect the MSB on the
> left (where, in this case, B is "bit").
>
> Of course, if I were to be masochistic, I'd write a binary adder()
> composed of bit adders with carry... Such as {I hope this was just a
> personal learning experience and not a homework project}...
>
> -=-=-=-=-=-=-
> """
> masochistic exercise in generating a binary adder
> """
> import sys
>
> def badd(b1, b2, c=0):
> """
> badd(b1, b2, c) => (carry, sum)
> """
> if b1 and b2:
> # 1 + 1 + c => carry out, and 0/1 from carry in
> return (1, c)
> elif (b1 and c) or (b2 and c):
> # either b1 or b2 is set, and carry in is set
> return (1, 0)
> else:
> # only one of carry in, b1, or b2 is set
> return (0, b1 + b2 + c)
>
> def adder(w1, w2):
> """
> adder(w1, w2) => w3
> where w1, w2, w3 are lists of 0s and 1s
> """
> #equalize list lengths
> if len(w1) > len(w2):
> w2 = [0] * (len(w1) - len(w2)) + w2
> elif len(w1) < len(w2):
> w1 = [0] * (len(w2) - len(w1)) + w1
>
> w3 = [0] * len(w1)
>
> carry = 0 #initialize
> end = len(w3) - 1
> for i in range(end + 1):
> (carry, w3[end-i]) = badd(w1[end-i], w2[end-i], carry)
>
> if carry:
> return "OVERFLOW" #should be an exception
>
> return w3
>
> if __name__ == "__main__":
> #sloppy conversion from character to binary
> binary = [ {True:1, False:0}[c == "1"] for c in sys.argv[1] ]
>
> #simple counter
>
> while binary != "OVERFLOW":
> print "".join(["%1s" % b for b in binary])
> binary = adder(binary, [ 1 ]) #need to supply a list
>
> print "Overflow must have occurred"
>
> binary1 = [ {True:1, False:0}[c == "1"] for c in sys.argv[2] ]
> binary2 = [ {True:1, False:0}[c == "1"] for c in sys.argv[3] ]
>
> print "".join(["%1s" % b for b in adder(binary1, binary2)])
>
> -=-=-=-=-=- (watch out for line wrap on the command line
> E:\UserData\Dennis Lee Bieber\My Documents\Python Progs>python binadd.py
> 0010 111
>
>
> 0001
> 0010
> 0011
> 0100
> 0101
> 0110
> 0111
> 1000
> 1001
> 1010
> 1011
> 1100
> 1101
> 1110
>
> Overflow must have occurred
> 1001
>
> E:\UserData\Dennis Lee Bieber\My Documents\Python Progs>
> E:\UserData\Dennis Lee Bieber\My Documents\Python Progs>python binadd.py
> 010 001 0
>
> 010
> 011
> 100
> 101
> 110
> 111
> Overflow must have occurred
> 1
>
> E:\UserData\Dennis Lee Bieber\My Documents\Python Progs>
> E:\UserData\Dennis Lee Bieber\My Documents\Python Progs>python binadd.py
> 00 1 1
>
> 00
> 01
> 10
> 11
> Overflow must have occurred
> OVERFLOW
>
> E:\UserData\Dennis Lee Bieber\My Documents\Python Progs>
>
> --
> WulfraedDennis Lee Bieber KD6MOG
> [EMAIL PROTECTED] [EMAIL PROTECTED]
> HTTP://wlfraed.home.netcom.com/
> (Bestiaria Support Staff: [EMAIL PROTECTED])
> HTTP://www.bestiaria.com/
thank you. you guys are keeping me busy!
ps. no, i'm not in school. not in the traditional sense anyway :-)
just books, practice, and forums like this.
--
http://mail.python.org/mailman/listinfo/python-list
Re: recursion depth problem
proctor wrote:
> On Apr 22, 2:06 pm, Steven Bethard <[EMAIL PROTECTED]> wrote:
>> proctor wrote:
>>> On Apr 22, 1:24 pm, Michael Bentley <[EMAIL PROTECTED]> wrote:
On Apr 22, 2007, at 1:49 PM, proctor wrote:
> i have a small function which mimics binary counting. it runs fine as
> long as the input is not too long, but if i give it input longer than
> 8 characters it gives
> RuntimeError: maximum recursion depth exceeded in cmp
> i'm not too sure what i am doing improperly. is there really a lot of
> recursion in this code?
> ==
> import sys
> def ch4(item, n=0):
>if n < len(item):
>if item[n] == '0':
>item[n] = '1'
>print ''.join(item)
>ch4(item)
>elif item[n] == '1':
>item[n] = '0'
>ch4(item, n+1)
> ch4(list(sys.argv[1]))
> ==
Yes. There really is *that* much recursion in that code. 502 levels
with input length of 8 characters, 1013 with 9 characters, 2035 with
10 characters... There's a pattern there ;-)
>>> ok, thanks michael!
>>> is there a way to avoid it here? how could i write this better, (if
>>> at all)?
>> Google for permutation-like recipies:
>>
>> http://www.google.com/search?q=Python+permutations
>>
>> Use the code from the first hit::
>>
>> >>> for x in xselections('01', 8):
>> ... print ''.join(x)
>> ...
>>
>> 0001
>> 0010
>> ...
>> 1101
>> 1110
>>
>>
>> Explaining to your teacher why your code uses generators when you
>> haven't been taught them yet is left as an exercise to the reader. ;-)
>>
>> STeVe
>
> this is really nice, thanks steve. much slicker than my code.
>
> for interest sake: is my method unredeemable?
Let's just say that I don't currently see an obvious way of redeeming
it. ;-)
STeVe
--
http://mail.python.org/mailman/listinfo/python-list
Re: recursion depth problem
On Apr 22, 7:10 pm, Dennis Lee Bieber <[EMAIL PROTECTED]> wrote: > On 22 Apr 2007 17:06:18 -0700, proctor <[EMAIL PROTECTED]> declaimed the > following in comp.lang.python: > > > > else: > > > # only one of carry in, b1, or b2 is set > > #or none is set! Missed the 0,0,0 condition > > > > return (0, b1 + b2 + c) > > > thank you. you guys are keeping me busy! > > Heh... I'm sure what I scratched together could be optimized more > (make functions out of the input/output conversions; add some error > checking on input data, allow for non-list arguments in adder()...) > > After all, if one wants a binary counter, one should implement a > binary addition operation, and basic digital has ways... Unfortunately, > Python now has a Boolean type, so boolean AND/OR doesn't give the > desired results... And using bitwise seems wasteful However... > replace the badd() with the following obscure thing if you really want > to get close to hardware emulation... > > def badd(b1, b2, ci=0): > """ > badd(b1, b2, ci) => (co, sum) > """ > (co1, hs1) = (b1 & b2, b1 ^ b2) > (co2, hs2) = (ci & hs1, ci ^ hs1) > return (co1 | co2, hs2) > > A pair of "half-adders"; and the extra bit to make a "full-adder". > It wouldn't be efficient to do it as one long return, just due to > duplicated (b1 ^ b2) sub-terms > > return ( (b1 & b2) | (ci & (b1 ^ b2)), (ci ^ (b1 ^ b2))) > > but it does work > -- > WulfraedDennis Lee Bieber KD6MOG > [EMAIL PROTECTED] [EMAIL PROTECTED] > HTTP://wlfraed.home.netcom.com/ > (Bestiaria Support Staff: [EMAIL PROTECTED]) > HTTP://www.bestiaria.com/ :-) this is good stuff. for learning especially! thank you again! proctor. -- http://mail.python.org/mailman/listinfo/python-list
Re: recursion depth problem
On Apr 22, 7:34 pm, Steven Bethard <[EMAIL PROTECTED]> wrote:
> proctor wrote:
> > On Apr 22, 2:06 pm, Steven Bethard <[EMAIL PROTECTED]> wrote:
> >> proctor wrote:
> >>> On Apr 22, 1:24 pm, Michael Bentley <[EMAIL PROTECTED]> wrote:
> On Apr 22, 2007, at 1:49 PM, proctor wrote:
> > i have a small function which mimics binary counting. it runs fine as
> > long as the input is not too long, but if i give it input longer than
> > 8 characters it gives
> > RuntimeError: maximum recursion depth exceeded in cmp
> > i'm not too sure what i am doing improperly. is there really a lot of
> > recursion in this code?
> > ==
> > import sys
> > def ch4(item, n=0):
> >if n < len(item):
> >if item[n] == '0':
> >item[n] = '1'
> >print ''.join(item)
> >ch4(item)
> >elif item[n] == '1':
> >item[n] = '0'
> >ch4(item, n+1)
> > ch4(list(sys.argv[1]))
> > ==
> Yes. There really is *that* much recursion in that code. 502 levels
> with input length of 8 characters, 1013 with 9 characters, 2035 with
> 10 characters... There's a pattern there ;-)
> >>> ok, thanks michael!
> >>> is there a way to avoid it here? how could i write this better, (if
> >>> at all)?
> >> Google for permutation-like recipies:
>
> >> http://www.google.com/search?q=Python+permutations
>
> >> Use the code from the first hit::
>
> >> >>> for x in xselections('01', 8):
> >> ... print ''.join(x)
> >> ...
> >>
> >> 0001
> >> 0010
> >> ...
> >> 1101
> >> 1110
> >>
>
> >> Explaining to your teacher why your code uses generators when you
> >> haven't been taught them yet is left as an exercise to the reader. ;-)
>
> >> STeVe
>
> > this is really nice, thanks steve. much slicker than my code.
>
> > for interest sake: is my method unredeemable?
>
> Let's just say that I don't currently see an obvious way of redeeming
> it. ;-)
>
> STeVe
lol. okay.
proctor.
--
http://mail.python.org/mailman/listinfo/python-list
Re: recursion depth problem
Steven Bethard <[EMAIL PROTECTED]> wrote: ... > > import sys > > def ch4(item, n=0): > >if n < len(item): > >if item[n] == '0': > >item[n] = '1' > >print ''.join(item) > >ch4(item) > >elif item[n] == '1': > >item[n] = '0' > >ch4(item, n+1) > > ch4(list(sys.argv[1])) ... > > for interest sake: is my method unredeemable? > > Let's just say that I don't currently see an obvious way of redeeming > it. ;-) Change the outer if into a while, and the recursive calls into proper assignments to n. They're both tail-recursive calls, so this won't change the semantics, as it happens. Alex -- http://mail.python.org/mailman/listinfo/python-list
Re: recursion depth problem
Alex Martelli wrote:
> Steven Bethard <[EMAIL PROTECTED]> wrote:
>...
>>> import sys
>>> def ch4(item, n=0):
>>>if n < len(item):
>>>if item[n] == '0':
>>>item[n] = '1'
>>>print ''.join(item)
>>>ch4(item)
>>>elif item[n] == '1':
>>>item[n] = '0'
>>>ch4(item, n+1)
>>> ch4(list(sys.argv[1]))
>...
>>> for interest sake: is my method unredeemable?
>> Let's just say that I don't currently see an obvious way of redeeming
>> it. ;-)
>
> Change the outer if into a while, and the recursive calls into proper
> assignments to n. They're both tail-recursive calls, so this won't
> change the semantics, as it happens.
Thanks!
>>> def f(chars):
... n = 0
... while n < len(chars):
... if chars[n] == '0':
... chars[n] = '1'
... n = 0
... print ''.join(chars)
... elif chars[n] == '1':
... chars[n] = '0'
... n += 1
...
>>> f(list(''))
1000
0100
1100
...
1011
0111
Looks good.
STeVe
--
http://mail.python.org/mailman/listinfo/python-list
Re: recursion depth problem
On Apr 22, 9:13�pm, proctor <[EMAIL PROTECTED]> wrote: > On Apr 22, 7:10 pm, Dennis Lee Bieber <[EMAIL PROTECTED]> wrote: > > > > > > > On 22 Apr 2007 17:06:18 -0700, proctor <[EMAIL PROTECTED]> declaimed the > > following in comp.lang.python: > > > > > � � else: > > > > � � � � # only one of carry in, b1, or b2 is set > > > � � � � � � � � � � � � #or none is set! Missed the 0,0,0 condition > > > > > � � � � return (0, b1 + b2 + c) > > > > thank you. �you guys are keeping me busy! > > > � � � � Heh... I'm sure what I scratched together could be optimized more > > (make functions out of the input/output conversions; add some error > > checking on input data, allow for non-list arguments in adder()...) > > > � � � � After all, if one wants a binary counter, one should implement a > > binary addition operation, and basic digital has ways... Unfortunately, > > Python now has a Boolean type, so boolean AND/OR doesn't give the > > desired results... And using bitwise seems wasteful However... > > replace the badd() with the following obscure thing if you really want > > to get close to hardware emulation... > > > def badd(b1, b2, ci=0): > > � � """ > > � � � � badd(b1, b2, ci) => (co, sum) > > � � """ > > � � (co1, hs1) = (b1 & b2, b1 ^ b2) > > � � (co2, hs2) = (ci & hs1, ci ^ hs1) > > � � return (co1 | co2, hs2) > > > � � � � A pair of "half-adders"; and the extra bit to make a "full-adder". > > It wouldn't be efficient to do it as one long return, just due to > > duplicated (b1 ^ b2) sub-terms > > > return ( (b1 & b2) | (ci & (b1 ^ b2)), (ci ^ (b1 ^ b2))) > > > but it does work > > -- > > � � � � Wulfraed � � � �Dennis Lee Bieber � � � � � � � KD6MOG > > � � � � [EMAIL PROTECTED] � � � � � � [EMAIL PROTECTED] > > � � � � � � � � HTTP://wlfraed.home.netcom.com/ > > � � � � (Bestiaria Support Staff: � � � � � � � [EMAIL PROTECTED]) > > � � � � � � � � HTTP://www.bestiaria.com/ > > :-) > > this is good stuff. �for learning especially! �thank you again! I once made a complete full adder in perl with strings so that I could have unlimited precision (this is before I found out about Big Arithmetic libraries). Since I was only doing the Collatz Conjecture, all I needed was to multiply by 3 (shift left by appending '0' to string and adding to original string using the full adder), dividing by two (shift right by slicing off rightmost character from string) and incrementing (pre-set the carry bit to '1'). It worked perfectly. But it was slower than snake shit. > > proctor -- http://mail.python.org/mailman/listinfo/python-list
Re: recursion depth problem
On Apr 22, 9:28 pm, Dennis Lee Bieber <[EMAIL PROTECTED]> wrote: > On 22 Apr 2007 19:13:31 -0700, proctor <[EMAIL PROTECTED]> declaimed the > following in comp.lang.python: > > > > > :-) > > > this is good stuff. for learning especially! thank you again! > > Took me some time to find... My 30year old BugBooks* are in storage, > along with all the other raw comp-sci texts. > > What you see above is a Python implementation of a 2 1-bit input, > 1-bit sum and 1-bit carry output, full-adder from basic AND/OR/XOR gates > -- you can build the hardware equivalent (except for the variable > length) using old-fashioned 74xx chips (are 74xx TTL chips still made, > or will one need to use the 74Cxx CMOS variants ) [heck; is the > multi-function ALU chip still made?] > > * The Virginia Tech shootings were just a blip on my radar until I > read that this was Blacksburg -- as I once had most of the Blacksburg > BugBooks > -- > WulfraedDennis Lee Bieber KD6MOG > [EMAIL PROTECTED] [EMAIL PROTECTED] > HTTP://wlfraed.home.netcom.com/ > (Bestiaria Support Staff: [EMAIL PROTECTED]) > HTTP://www.bestiaria.com/ well i'm going to make it a project to understand properly this program. proctor. -- http://mail.python.org/mailman/listinfo/python-list
Re: recursion depth problem
On Apr 22, 8:23 pm, [EMAIL PROTECTED] (Alex Martelli) wrote: > Steven Bethard <[EMAIL PROTECTED]> wrote: > >... > > > > > > import sys > > > def ch4(item, n=0): > > >if n < len(item): > > >if item[n] == '0': > > >item[n] = '1' > > >print ''.join(item) > > >ch4(item) > > >elif item[n] == '1': > > >item[n] = '0' > > >ch4(item, n+1) > > > ch4(list(sys.argv[1])) >... > > > for interest sake: is my method unredeemable? > > > Let's just say that I don't currently see an obvious way of redeeming > > it. ;-) > > Change the outer if into a while, and the recursive calls into proper > assignments to n. They're both tail-recursive calls, so this won't > change the semantics, as it happens. > > Alex really helpful! thank you very much! proctor. -- http://mail.python.org/mailman/listinfo/python-list
Re: recursion depth problem
On Apr 22, 5:51 pm, Michael Bentley <[EMAIL PROTECTED]> wrote: > Oops! Note to self: *ALWAYS* try code before posting to a public > forum :-( > > def binary(val, width): > print '%10s = the sum of' % val > for i in [2 ** x for x in range(width - 1, -1, -1)]: > a = val / i > print ' ' * 13 + '%s * (2 ** %s)' % (a, width) > val -= i * a > width -= 1 > > binary(233, 8) hi michael, just a quick clarification... it seems to me that the self-documenting part of the code should be more like this: print ' ' * 13 + '%s * (2 ** %s)' % (a, width-1) instead of print ' ' * 13 + '%s * (2 ** %s)' % (a, width) is this correct, or am i mixed? sincerely, proctor -- http://mail.python.org/mailman/listinfo/python-list
Re: recursion depth problem
On Apr 23, 2007, at 1:57 AM, proctor wrote: > On Apr 22, 5:51 pm, Michael Bentley <[EMAIL PROTECTED]> wrote: >> Oops! Note to self: *ALWAYS* try code before posting to a public >> forum :-( >> >> def binary(val, width): >> print '%10s = the sum of' % val >> for i in [2 ** x for x in range(width - 1, -1, -1)]: >> a = val / i >> print ' ' * 13 + '%s * (2 ** %s)' % (a, width) >> val -= i * a >> width -= 1 >> >> binary(233, 8) > > hi michael, > > just a quick clarification... > > it seems to me that the self-documenting part of the code should be > more like this: > > print ' ' * 13 + '%s * (2 ** %s)' % (a, width-1) > > instead of > > print ' ' * 13 + '%s * (2 ** %s)' % (a, width) > > is this correct, or am i mixed? > No, you're right -- actually I ended up decrementing width after the print instead of before it -- but didn't feel like posting yet another correction. Your correction works though! -- http://mail.python.org/mailman/listinfo/python-list
