Re: division by 7 efficiently ???
Roel Schroeven schreef: > [EMAIL PROTECTED] schreef: >> I had considered this, but to halve, you need to divide by 2. Using >> random, while potentially increasing the number of iterations, removes >> the dependency of language tricks and division. > > It's possible to use Fibonacci numbers instead of halving each time; > that requires only addition and subtraction. Unfortunately I forgot > exactly how that works, and I don't have the time to look it up or to > try to reproduce it now. Maybe later. > > AFAIK that method is not commonly used since binary computers are very > good at dividing numbers by two, but it would be a good method on > ternary or decimal computers. Responding to myself since I found an explanation in the obvious place: http://en.wikipedia.org/wiki/Fibonacci_search_technique It is meant for search in ordered arrays though; I don't think it can be adapted for searching in mathematic intervals. -- If I have been able to see further, it was only because I stood on the shoulders of giants. -- Isaac Newton Roel Schroeven -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
[EMAIL PROTECTED] schreef: > On Feb 6, 4:54 pm, "John Machin" <[EMAIL PROTECTED]> wrote: >> Recursive? Bzzzt! >> Might it not be better to halve the interval at each iteration instead >> of calling a random number function? mid = (lo + hi) >> 1 looks >> permitted and cheap to me. Also you don't run the risk of it taking a >> very high number of iterations to get a result. > > I had considered this, but to halve, you need to divide by 2. Using > random, while potentially increasing the number of iterations, removes > the dependency of language tricks and division. It's possible to use Fibonacci numbers instead of halving each time; that requires only addition and subtraction. Unfortunately I forgot exactly how that works, and I don't have the time to look it up or to try to reproduce it now. Maybe later. AFAIK that method is not commonly used since binary computers are very good at dividing numbers by two, but it would be a good method on ternary or decimal computers. -- If I have been able to see further, it was only because I stood on the shoulders of giants. -- Isaac Newton Roel Schroeven -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
On Feb 7, 11:05 am, [EMAIL PROTECTED] wrote: > On Feb 6, 4:54 pm, "John Machin" <[EMAIL PROTECTED]> wrote: > > > Recursive? Bzzzt! > > I woudl be happy to hear your alternative, which doesn't depend on > language specific tricks. Thus far, all you have suggested is using an > alternative form of the division function, Huh? Thus far (in this post) all I've said is (in effect) that IMHO mentioning recursion is just cause for termination of job interview. > which I would consider to > be outside the spirit of the question (though I have been wrong many > times before). > > > Might it not be better to halve the interval at each iteration instead > > of calling a random number function? mid = (lo + hi) >> 1 looks > > permitted and cheap to me. Also you don't run the risk of it taking a > > very high number of iterations to get a result. > > I had considered this, but to halve, you need to divide by 2. Using > random, while potentially increasing the number of iterations, removes > the dependency of language tricks and division. "Potentially increases the number of iterations"? Sorry, the interview for marketing manager is across the hall. For example if your N must fit in 16 bits, you could end up with O(2**16) iterations. This may not show up in acceptance testing. And each iteration involves calling a random number function. A binary search has a guaranteed upper limit of O(16). Let's get this in contect: the traditional "long division" approach takes 16 iterations! Shifting to divide by a power of 2 is not a "language trick". In any case any compiler that deserves to be used will replace division by a power of 2 with a shift. > > > Did you notice the important word *efficiently* in line 1 of the spec? > > Even after ripping out recursion and random numbers, your proposed > > solution is still way off the pace. > > Again, I look forward to reading your solution. > Respectfully, read my other posts in this thread. The correct answer IMHO is "Semi-decent compilers like gcc will do a good-enough job of dividing an integer by a constant. Only in situations like a very high-use library routine where the N is known to be much smaller than 2**wordsize might it be worthwhile to see if a bit-bashing approach could generate faster code". Cheers, John -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
On Feb 6, 4:54 pm, "John Machin" <[EMAIL PROTECTED]> wrote: > Recursive? Bzzzt! I woudl be happy to hear your alternative, which doesn't depend on language specific tricks. Thus far, all you have suggested is using an alternative form of the division function, which I would consider to be outside the spirit of the question (though I have been wrong many times before). > Might it not be better to halve the interval at each iteration instead > of calling a random number function? mid = (lo + hi) >> 1 looks > permitted and cheap to me. Also you don't run the risk of it taking a > very high number of iterations to get a result. I had considered this, but to halve, you need to divide by 2. Using random, while potentially increasing the number of iterations, removes the dependency of language tricks and division. > Did you notice the important word *efficiently* in line 1 of the spec? > Even after ripping out recursion and random numbers, your proposed > solution is still way off the pace. Again, I look forward to reading your solution. Respectfully, G. -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
On Feb 7, 2:29 am, [EMAIL PROTECTED] wrote: > On Feb 1, 8:25 pm, "Krypto" <[EMAIL PROTECTED]> wrote: > > > The correct answer as told to me by a person is > > (N>>3) + ((N-7*(N>>3))>>3) > > The above term always gives division by 7 > > Does anybody else notice that this breaks the spirit of the problem > (regardless of it's accuracy)? 'N-7' uses the subtraction operator, > and is thus an invalid solution for the original question. > > Build a recursive function, which uses two arbitrary numbers, say 1 > and 100. Recursive? Bzzzt! > Check each, times 7, and make sure that your target number, > N, is between them. Increase or decrease your arbitrary numbers as > appropriate. Now pick a random number between those two numbers, and > check it. Figure out which two the answer is between, and then check a > random number in that subset Might it not be better to halve the interval at each iteration instead of calling a random number function? mid = (lo + hi) >> 1 looks permitted and cheap to me. Also you don't run the risk of it taking a very high number of iterations to get a result. >. Continue this, and you will drill down > to the correct answer, by using only *, +, >, and <. > > I'll bet money that since this was a programming interview, that it > wasn't a check of your knowledge of obscure formulas, but rather a > check of your lateral thinking and knowledge of programming. > > ~G Did you notice the important word *efficiently* in line 1 of the spec? Even after ripping out recursion and random numbers, your proposed solution is still way off the pace. Cheers, John -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
On Feb 6, 3:29 pm, [EMAIL PROTECTED] wrote: > On Feb 1, 8:25 pm, "Krypto" <[EMAIL PROTECTED]> wrote: > > > The correct answer as told to me by a person is > > (N>>3) + ((N-7*(N>>3))>>3) > > The above term always gives division by 7 > > Does anybody else notice that this breaks the spirit of the problem > (regardless of it's accuracy)? 'N-7' uses the subtraction operator, > and is thus an invalid solution for the original question. > [snip] Instead of subtraction you can use complement-and-add: N + ~7 + 1 (that's a tilde '~' not a minus '-'). -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
On Feb 1, 8:25 pm, "Krypto" <[EMAIL PROTECTED]> wrote: > The correct answer as told to me by a person is > (N>>3) + ((N-7*(N>>3))>>3) > The above term always gives division by 7 Does anybody else notice that this breaks the spirit of the problem (regardless of it's accuracy)? 'N-7' uses the subtraction operator, and is thus an invalid solution for the original question. Build a recursive function, which uses two arbitrary numbers, say 1 and 100. Check each, times 7, and make sure that your target number, N, is between them. Increase or decrease your arbitrary numbers as appropriate. Now pick a random number between those two numbers, and check it. Figure out which two the answer is between, and then check a random number in that subset. Continue this, and you will drill down to the correct answer, by using only *, +, >, and <. I'll bet money that since this was a programming interview, that it wasn't a check of your knowledge of obscure formulas, but rather a check of your lateral thinking and knowledge of programming. ~G -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
>How to divide a number by 7 efficiently without using - or / operator. >We can use the bit operators. I was thinking about bit shift operator >but I don't know the correct answer. It may not be efficient, but the easiest solution (without using tricks from a particular languages) is to increment a value within a while loop which checks it against the target value. More efficient may be to pick an arbitrary value, and check for greater than or less than, modifying the range based off your results (much like a recursive search). However, having done a tour with EA, I would have to say that you're probably better off not making it. Though they're getting better. =) Garrick M. Peterson Quality Assurance Analyst Zoot Enterprises, Inc. Copyright © 2007 Zoot Enterprises, Inc. and its affiliates. All rights reserved. This email, including any attachments, is confidential and may not be redistributed without permission. If you are not an intended recipient, you have received this message in error; please notify us immediately by replying to this message and deleting it from your computer. Thank you. -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
On Feb 1, 8:25 pm, "Krypto" <[EMAIL PROTECTED]> wrote: > The correct answer as told to me by a person is > > (N>>3) + ((N-7*(N>>3))>>3) > > The above term always gives division by 7 No it doesn't. The above term tends towards N * (9/64), with some significant rounding errors. 9/64 is a fairly poor (6 bit) approximation of 1/7 but the principle is the same as the solution I proposed above. Nicko -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
On Feb 2, 4:21 pm, "Bart Ogryczak" <[EMAIL PROTECTED]> wrote: > On Feb 1, 2:00 pm, "Nicko" <[EMAIL PROTECTED]> wrote: > > > precision and the answer that they were looking for was: > > a = (b * 045L) >> 32 > > Note that the constant there is in octal. > > 045L? Shouldn´t it be 044? > Or more generally, > const = (1< a = (b * const)>>bitPrecision It's to do with rounding. What you actually need is ceiling((1
Re: division by 7 efficiently ???
On Feb 1, 2:00 pm, "Nicko" <[EMAIL PROTECTED]> wrote: > precision and the answer that they were looking for was: > a = (b * 045L) >> 32 > Note that the constant there is in octal. 045L? Shouldn´t it be 044? Or more generally, const = (1<>bitPrecision -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
On Feb 3, 2:31 am, "Jesse Chounard" <[EMAIL PROTECTED]> wrote: > On 31 Jan 2007 19:13:14 -0800, [EMAIL PROTECTED] > > <[EMAIL PROTECTED]> wrote: > > Its not an homework. I appeared for EA sports interview last month. I > > was asked this question and I got it wrong. I have already fidlled > > around with the answer but I don't know the correct reasoning behind > > it. > > I think this works: You think wrongly. Inspection reveals that it is obviously incorrect for N == 0. Trivial testing reveals that it is wrong for about 6 out of every 7 cases. > > >>> def div7 (N): > > ... return ((N * 9362) >> 16) + 1 > ...>>> div7(7) > 1 > >>> div7(14) > 2 > >>> div7(700) > 100 > >>> div7(7) > > 1 > > The coolest part about that (whether it works or not) is that it's my > first Python program. I wrote it in C first and had to figure out how > to convert it. :) Try testing algorithms with a pencil on the back of an envelope first. The uncoolest part about that is that your test data is horribly deficient: >>> for N in xrange(0, 23): ... a = ((N * 9362) >> 16) + 1 ... e = N // 7 ... print N, a, e, a == e ... 0 1 0 False 1 1 0 False 2 1 0 False 3 1 0 False 4 1 0 False 5 1 0 False 6 1 0 False 7 1 1 True 8 2 1 False 9 2 1 False 10 2 1 False 11 2 1 False 12 2 1 False 13 2 1 False 14 2 2 True 15 3 2 False 16 3 2 False 17 3 2 False 18 3 2 False 19 3 2 False 20 3 2 False 21 3 3 True 22 4 3 False HTH, John -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
On Feb 2, 11:03 pm, "Bart Ogryczak" <[EMAIL PROTECTED]> wrote: > On Feb 1, 3:42 am, [EMAIL PROTECTED] wrote: > > > How to divide a number by 7 efficiently without using - or / operator. > > We can use the bit operators. I was thinking about bit shift operator > > but I don't know the correct answer. > > It´s quiet simple. x == 8*(x/8) + x%8, so x == 7*(x/8) + (x/8 + x%8) > x/8 == x>>3, x%8 == x&7 > And there you have it, function rounds upwards for numbers not > divisible by 7. Gotta change int(x>0) to int(x>3) to round normally, > or int(x>6) to round downwards. > > def d7(x): > if(x>>3 == 0): return int(x>0) > return (x>>3)+d7((x>>3)+(x&7)) I doubt that a recursive function call (even a tail-recursive one) comes near what the OP and his interrogators mean by "efficiently". Nicko has already given the answer for the case where a 31-bit non- negative dividend is required. Here are some examples of the technique for cases where smaller numbers are found e.g. in date arithmetic. def div7a(N): assert 0 <= N <= 684 r = (N << 3) + N r = (r << 3) + N r = (r << 2) + N r >>= 11 return r def div7b(N): assert 0 <= N <= 13109 r = (N << 3) + N r = (r << 3) + N r = (r << 3) + N r = (r << 3) + N r = (r << 1) + N r >>= 16 return r What's going on there? Well, using the first example, (2 ** 11) // 7 and rounded to the higher integer is 293. So 293 / 2048 is an approximation to 1 / 7. Dividing by 2048 is a doddle. The shift-left- add stuff is doing the multiplication by 293, unrolled loop, one cycle per line when implemented as a SHLnADD instruction from the HP PA-RISC architecture. Unsigned division otherwise would take 32 DS (divide step) instructions. FWIW, gcc emits code for the Intel IA32 architecture that gloriously "misuses" the LEAL instruction to get the same reg1 = (reg2 << n) + reg3 effect. Any relevance to this newsgroup? Yes, there's a lot of pre-computation involved there. Python is an excellent language for debugging such stuff and generating include files for a production code. Cheers, John -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
On 31 Jan 2007 19:13:14 -0800, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote: > Its not an homework. I appeared for EA sports interview last month. I > was asked this question and I got it wrong. I have already fidlled > around with the answer but I don't know the correct reasoning behind > it. I think this works: >>> def div7 (N): ... return ((N * 9362) >> 16) + 1 ... >>> div7(7) 1 >>> div7(14) 2 >>> div7(700) 100 >>> div7(7) 1 The coolest part about that (whether it works or not) is that it's my first Python program. I wrote it in C first and had to figure out how to convert it. :) Jesse -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
On 2007-02-01, Michael Yanowitz <[EMAIL PROTECTED]> wrote: > I think it is off by 1 in small numbers, off by a little more with large > numbers: def div7 (N): > ...return (N>>3) + ((N-7*(N>>3))>>3) > ... div7 (70) > 9 div7 (77) > 10 div7 (700) > 98 div7 (7) > 0 div7 (10) > 1 div7 (14) > 1 div7 (21) > 2 div7 (700) > 98 div7 (7000) > 984 > Heh, heh. That's reminding of the "fabulous" O(n) Dropsort algorithm I saw linked from Effbot's blog. -- Neil Cerutti I'm tired of hearing about money, money, money, money, money. I just want to play the game, drink Pepsi, wear Reebok. --Shaquille O'Neal -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
On Feb 1, 3:42 am, [EMAIL PROTECTED] wrote: > How to divide a number by 7 efficiently without using - or / operator. > We can use the bit operators. I was thinking about bit shift operator > but I don't know the correct answer. It´s quiet simple. x == 8*(x/8) + x%8, so x == 7*(x/8) + (x/8 + x%8) x/8 == x>>3, x%8 == x&7 And there you have it, function rounds upwards for numbers not divisible by 7. Gotta change int(x>0) to int(x>3) to round normally, or int(x>6) to round downwards. def d7(x): if(x>>3 == 0): return int(x>0) return (x>>3)+d7((x>>3)+(x&7)) -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
In <[EMAIL PROTECTED]>, Krypto wrote: > The correct answer as told to me by a person is > > (N>>3) + ((N-7*(N>>3))>>3) How could it be correct if it uses `-`? You ruled out `-` and `/` in your first post. Ciao, Marc 'BlackJack' Rintsch -- http://mail.python.org/mailman/listinfo/python-list
RE: division by 7 efficiently ???
Michael> I think it is off by 1 in small numbers, off by a little more Michael> with large numbers: ... Sorta makes you think using the DIV instruction in the CPU is the way to go. ;-) Skip -- http://mail.python.org/mailman/listinfo/python-list
RE: division by 7 efficiently ???
I think it is off by 1 in small numbers, off by a little more with large numbers: >>> def div7 (N): ...return (N>>3) + ((N-7*(N>>3))>>3) ... >>> div7 (70) 9 >>> div7 (77) 10 >>> div7 (700) 98 >>> div7 (7) 0 >>> div7 (10) 1 >>> div7 (14) 1 >>> div7 (21) 2 >>> div7 (700) 98 >>> div7 (7000) 984 Michael Yanowitz -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Behalf Of Krypto Sent: Thursday, February 01, 2007 3:25 PM To: python-list@python.org Subject: Re: division by 7 efficiently ??? The correct answer as told to me by a person is (N>>3) + ((N-7*(N>>3))>>3) The above term always gives division by 7 -- http://mail.python.org/mailman/listinfo/python-list -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
"Krypto" <[EMAIL PROTECTED]> writes: > The correct answer as told to me by a person is > > (N>>3) + ((N-7*(N>>3))>>3) > > > The above term always gives division by 7 Well, not exactly: [GCC 3.4.2 20041017 (Red Hat 3.4.2-6.fc3)] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> def f(N): return (N>>3) + ((N-7*(N>>3))>>3) ... >>> f(7) 0 >>> f(70) 9 >>> f(700) 98 -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
The correct answer as told to me by a person is (N>>3) + ((N-7*(N>>3))>>3) The above term always gives division by 7 -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
On Feb 1, 3:13 am, [EMAIL PROTECTED] wrote: > Its not an homework. I appeared for EA sports interview last month. I > was asked this question and I got it wrong. I have already fidlled > around with the answer but I don't know the correct reasoning behind > it. In that case, observer that a/b == a * (1/b), and if b is constant you can compute (1/b) in advance. Since the problem was set by game programmers I'd hazard that they are OK with relatively limited precision and the answer that they were looking for was: a = (b * 045L) >> 32 Note that the constant there is in octal. Nicko -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
This is maybe not so efficient :) but it implements integer division by 7 for positive integers without - and /. def div2(num): return num >> 1 def div4(num): return num >> 2 def div8(num): return num >> 3 def mul2(num): return num << 1 def mul4(num): return num << 2 def mul7(num): return mul4(num) + mul2(num) + num def div7_help(num, lo, hi): avg = div2(lo + hi) if avg == lo or avg == hi: if mul7(hi) == num: return hi return lo avg7 = mul7(avg) if avg7 > num: return div7_help(num, lo, avg) elif avg7 < num: return div7_help(num, avg, hi) return avg def div7(num): lo = div8(num) hi = div4(num) return div7_help(num, lo, hi) for nr in range(0, 2): #print "%d // 7 = %d" % (nr, nr // 7) #print "div7(%d) = %d" % (nr, div7(nr)) assert nr // 7 == div7(nr) A somewhat better approach is to convert the recursion to an interative method. But that is.. um.. left as an exercise. -- mvh Björn -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
In <[EMAIL PROTECTED]>, Paul McGuire wrote: > On Jan 31, 11:36 pm, "Paddy" <[EMAIL PROTECTED]> wrote: >> On Feb 1, 2:42 am, [EMAIL PROTECTED] wrote: >> >> > How to divide a number by 7 efficiently without using - or / operator. >> > We can use the bit operators. I was thinking about bit shift operator >> > but I don't know the correct answer. >> >>> int.__div__(14,2) >> 7 >> >> Not a minus or division operator in sight ;-) >> >> - Paddy. > > Now I'm confused - was the OP trying to divide by 7 or 2? I read it as divide by 7. And the `int.__div__()` Method limits this somehow -- a more polymorphic approach would be:: import operator operator.div(14, 7) :-) Ciao, Marc 'BlackJack' Rintsch -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
On Feb 1, 2:36 pm, John Nagle <[EMAIL PROTECTED]> wrote: > [EMAIL PROTECTED] wrote: > > Its not an homework. I appeared for EA sports interview last month. I > > was asked this question and I got it wrong. I have already fidlled > > around with the answer but I don't know the correct reasoning behind > > it. > > The answer to that question is that the fastest way to divide > by 7 is to use the divide instruction. You'd have to go down > to a really old 8-bit microprocessor like the Intel 8051 to > find something where bit-twiddling like that pays off. Perhaps not that far back. Google "Granlund Montgomery". The technique got built into gcc. > And no way would this be a win in Python, which is > interpreted. Agreed. -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
On Jan 31, 11:36 pm, "Paddy" <[EMAIL PROTECTED]> wrote: > On Feb 1, 2:42 am, [EMAIL PROTECTED] wrote: > > > > > How to divide a number by 7 efficiently without using - or / operator. > > We can use the bit operators. I was thinking about bit shift operator > > but I don't know the correct answer. > >>> int.__div__(14,2) > 7 > > Not a minus or division operator in sight ;-) > > - Paddy. Now I'm confused - was the OP trying to divide by 7 or 2? -- Paul -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
"Paddy" <[EMAIL PROTECTED]> writes: > On Feb 1, 2:42 am, [EMAIL PROTECTED] wrote: > > How to divide a number by 7 efficiently without using - or / operator. > > >>> int.__div__(14,2) > 7 > >>> > > Not a minus or division operator in sight ;-) I salute you, sir. That's the perfect answer to the boneheaded constraints of the problem :-) -- \ "What I resent is that the range of your vision should be the | `\ limit of my action." -- Henry James | _o__) | Ben Finney -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
On Feb 1, 2:42 am, [EMAIL PROTECTED] wrote: > How to divide a number by 7 efficiently without using - or / operator. > We can use the bit operators. I was thinking about bit shift operator > but I don't know the correct answer. >>> int.__div__(14,2) 7 >>> Not a minus or division operator in sight ;-) - Paddy. -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
[EMAIL PROTECTED] wrote: > Its not an homework. I appeared for EA sports interview last month. I > was asked this question and I got it wrong. I have already fidlled > around with the answer but I don't know the correct reasoning behind > it. The answer to that question is that the fastest way to divide by 7 is to use the divide instruction. You'd have to go down to a really old 8-bit microprocessor like the Intel 8051 to find something where bit-twiddling like that pays off. And no way would this be a win in Python, which is interpreted. John Nagle -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
Its not an homework. I appeared for EA sports interview last month. I was asked this question and I got it wrong. I have already fidlled around with the answer but I don't know the correct reasoning behind it. Thanks, On Jan 31, 10:01 pm, Ben Finney <[EMAIL PROTECTED]> wrote: > [EMAIL PROTECTED] writes: > > How to divide a number by 7 efficiently without using - or / > > operator. We can use the bit operators. I was thinking about bit > > shift operator but I don't know the correct answer. > > I think you are asking for help on a homework assignment in violation > of collusion and plagiarism rules of your educational institution, and > I claim my ten zorkmids. > > Please use the resources made available to you in your course of > study; this almost certainly does not include having people on > discussion forums answer the homework for you. > > -- > \ "I like to go to art museums and name the untitled paintings. | > `\ 'Boy With Pail'. 'Kitten On Fire'." -- Steven Wright | > _o__) | > Ben Finney -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
On Wed, 31 Jan 2007 18:42:54 -0800, krypto.wizard wrote:
> How to divide a number by 7 efficiently without using - or / operator.
> We can use the bit operators. I was thinking about bit shift operator
> but I don't know the correct answer.
I'd be surprised if there was a trick for dividing by seven efficiently...
it is one of the "difficult" cases. See:
http://www.bitwisemag.com/copy/wilf/wilf5.html
for a discussion.
But even if there is some nifty algorithm for efficiently dividing by
seven using bit operators, I don't expect it will work efficiently in
Python. The overhead of using objects will probably outweigh any saving
you might get by using magic tricks, so you should just use division.
It is like using the XOR trick for swapping integers: there's just no
point in doing it in Python except as a trick, because it is slower than
just swapping them:
>>> timeit.Timer("x = x^y; y = x^y; x= x^y", "x, y = 1, 2").repeat()
[0.88827300071716309, 0.85192012786865234, 0.81278204917907715]
>>> timeit.Timer("x, y = y, x", "x, y = 1, 2").repeat()
[0.71292495727539062, 0.65545105934143066, 0.68413901329040527]
--
Steven D'Aprano
--
http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
[EMAIL PROTECTED] writes: > How to divide a number by 7 efficiently without using - or / > operator. We can use the bit operators. I was thinking about bit > shift operator but I don't know the correct answer. I think you are asking for help on a homework assignment in violation of collusion and plagiarism rules of your educational institution, and I claim my ten zorkmids. Please use the resources made available to you in your course of study; this almost certainly does not include having people on discussion forums answer the homework for you. -- \ "I like to go to art museums and name the untitled paintings. | `\ 'Boy With Pail'. 'Kitten On Fire'." -- Steven Wright | _o__) | Ben Finney -- http://mail.python.org/mailman/listinfo/python-list
Re: division by 7 efficiently ???
[EMAIL PROTECTED] writes: > How to divide a number by 7 efficiently without using - or / operator. > We can use the bit operators. I was thinking about bit shift operator > but I don't know the correct answer. Erm, sounds like a homework problem... suggestion: think of how many input bits you have, then check the accuracy of the obvious approximations until you reach one that's precise enough. -- http://mail.python.org/mailman/listinfo/python-list
division by 7 efficiently ???
How to divide a number by 7 efficiently without using - or / operator. We can use the bit operators. I was thinking about bit shift operator but I don't know the correct answer. -- http://mail.python.org/mailman/listinfo/python-list
