Re: [Tutor] OverflowError in lucky numbers script
Shreesh bhat wrote: Thank you all for helping me understand the overflow error. I m a newbie on mailing lists.I apologize for my errors. Program: [snip code] The program is executing correctly but it has to execute 16 seconds for the constraints. I have optimized the way i sum up digits and used consult-table approach. Still the program doesn't reach the 16 seconds target. How to achieve this target? What is the exact dataset for which you are trying to reach that execution time limit? Please give the values for start and end numbers. How far off is your current solution, i. e. how many seconds does it need to finish? I am asking because if you are almost there it makes sense to try and optimise your current script a little more, but if you are orders of magnitude away from your goal you may need a completely different approach. ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] OverflowError in lucky numbers script
On 23/01/12 06:10, Shreesh bhat wrote:
def sieve(maxi):
primes = range(2,maxi+1)
You can reduce the size of primes by only storing the odd numbers.
range takes a third parameter that sets the stepsize, you cxan
use that to skip evens...
for i in primes:
j = 2
you can then start here with j=3...
while i * j = primes[-1]:
if i * j in primes:
primes.remove(i*j)
I'm not sure which is faster but I suspect list comprehensions
could be used here too at the expense of consuming more memory.
primes = [num for num in primes if i*j in primes]
but the while loop stops earlier so it's hard to be sure which
is more efficient unless you try it.
j += 1
return primes
maxi=(10**2)*18 #Generating the table till the largest possible prime
tab=sieve(maxi)
table={}
for i in tab:
table[i]=0
def isprime(n):
return table.has_key(n)
count=0
def islucky(n): # modified islucky function
global count
sum1=0
sum2=0
for letter in str(n):
tmp=ord(letter)-48
sum1+=tmp
sum2+=tmp**2
if isprime(sum1):
if isprime(sum2):
count+=1
This last should be marginally faster if you use an and test:
if isprime(sum1) and isprime(sum2):
count+=1
number=raw_input() # Number of test cases.Its constraint (1,1)
Put the description as the prompt - make life easier for your user, even
if it is only you! Learn good habits early.
number=raw_input(Number of test cases(1-1).)
def execute():
global count
for i in range(int(number)):
inp=raw_input()# startnumber and endnumber pair. Its
constraint (1,10**18)
Same here:
inp=raw_input(startnumber and endnumber pair(1-10**18))
a=inp.split()
startnum=int(a[0])
endnum=int(a[1])
count=0
while startnum != endnum:
!= is a risky strategy, it can lead to accidental infinite loops. Better
to use
while startnum endnum:
and while we are at it, do you really mean not to test endnum?
islucky(startnum)
startnum+=1
print count
execute()
The program is executing correctly but it has to execute 16 seconds for
the constraints.
So how close are you? That gives us a clue on how much farther we need
to optimise...
HTH
--
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] OverflowError in lucky numbers script
I tried optimizing everything all things you guys pointed out and still its orders of magnitude away from the expected result. The program should check the islucky condition between range of (1,10**18) numbers and iterate over that 10**5 times. This program slows down more than 16 secs at (1,10**8) and 1 time. Which approach should i follow? ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] OverflowError in lucky numbers script
Shreesh bhat wrote: I tried optimizing everything all things you guys pointed out and still its orders of magnitude away from the expected result. The program should check the islucky condition between range of (1,10**18) numbers and iterate over that 10**5 times. This program slows down more than 16 secs at (1,10**8) and 1 time. Which approach should i follow? Consult the person who gave you this task -- there is no way python can even count to 10**18 in 16 seconds. ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] OverflowError in lucky numbers script
On Mon, Jan 23, 2012 at 06:43:50PM +0530, Shreesh bhat wrote: The program should check the islucky condition between range of (1,10**18) numbers and iterate over that 10**5 times. How is the islucky condition defined? The only version I have found is based on something quite similar to primes, where you start by writing all the numbers down: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ... Then delete every second number: 1 3 5 7 911131517... Now the next lowest number is 3, so delete every third number: 1 3 7 9 1315 ... The next survivor is 7, so delete every seventh number, and so on. The first few lucky numbers by this definition are: 1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, 87, 93, 99, ... (sequence A000959 in OEIS). (See also the Wikipedia article on Lucky Numbers.) Is this the same definition of lucky number that your puzzle uses? If so, you will need to think about a clever way to test which numbers are lucky. Quite frankly, if this is the definition of lucky numbers you are supposed to use, the only possible way you can calculate all the lucky numbers between 1 and 10**18, not once, but 10**5 times, in sixteen seconds, is to find some incredibly clever algorithm. Given the straight-forward algorithm above, I don't believe any supercomputer on earth could solve the problem as given. Perhaps I have misunderstood the problem. Is it explained on some website? -- Steven ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] OverflowError in lucky numbers script
On 23/01/12 13:13, Shreesh bhat wrote: I tried optimizing everything all things you guys pointed out and still its orders of magnitude away from the expected result. That's what I suspected. It means the fundamental approach of testing every number can probably never work. Which approach should I follow? You will need to go back to the math. Find a better algorithm than testing all numbers. Maybe you can find a way to generate the numbers rather than eliminate them? This may be a problem somebody else has solved so a Google/Wikipedia search may turn up some useful algorithms? Since it seems to be a homework type assignment it would be normal for it to be related to your classwork. So what have you been studying recently that might help? One thing that might help is to generate all the primes you need in advance? For example if the max number is 10**18 that implies 18 digits, so the the max of the squares sum can only be 18*(9*9)=1458. Rather than checking for primeness it might be faster to calculate all primes up to that value and test for inclusion in that set. Similarly the primes for addition are max 18*9 = 162, a very small set of primes... Just a random thought, I have no idea how much that would help, if at all!... -- Alan G Author of the Learn to Program web site http://www.alan-g.me.uk/ ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] OverflowError in lucky numbers script
On 01/23/2012 01:20 PM, Alan Gauld wrote: On 23/01/12 13:13, Shreesh bhat wrote: I tried optimizing everything all things you guys pointed out and still its orders of magnitude away from the expected result. That's what I suspected. It means the fundamental approach of testing every number can probably never work. Which approach should I follow? You will need to go back to the math. Find a better algorithm than testing all numbers. Maybe you can find a way to generate the numbers rather than eliminate them? This may be a problem somebody else has solved so a Google/Wikipedia search may turn up some useful algorithms? Since it seems to be a homework type assignment it would be normal for it to be related to your classwork. So what have you been studying recently that might help? One thing that might help is to generate all the primes you need in advance? For example if the max number is 10**18 that implies 18 digits, so the the max of the squares sum can only be 18*(9*9)=1458. Rather than checking for primeness it might be faster to calculate all primes up to that value and test for inclusion in that set. Similarly the primes for addition are max 18*9 = 162, a very small set of primes... Just a random thought, I have no idea how much that would help, if at all!... I already suggested that, and he already implemented it. Although it was inefficient, it was good enough and not the bottleneck. -- DaveA ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] OverflowError in lucky numbers script
On 01/23/2012 08:13 AM, Shreesh bhat wrote: I tried optimizing everything all things you guys pointed out and still its orders of magnitude away from the expected result. The program should check the islucky condition between range of (1,10**18) numbers and iterate over that 10**5 times. This program slows down more than 16 secs at (1,10**8) and 1 time. Which approach should i follow? You said the two end points of the range were less than 10**18, but I didn't realize you really wanted to do the entire range, meaning first number is 1 and last is 10**18. To do that 100,000 times in 10 secs would mean you have to process 10**12 items per CPU clock cycle. That's so far beyond possible that it's clear another approach is necessary. If you're literally going to do all the possible 18 digit numbers, then perhaps you should be doing a combinational approach. For example, once you know whether 38 is lucky, you also know whether 83, 380, 38000, and 80030 are lucky. So you test all possible ordered strings the way you're doing it now, and multiply each (0 or 1) by the number of ways those digits could be permuted in an 18 digit space (adding zeroes in various places, and of course reordering numbers). So we're looking for a bunch of lists of 18 ints, where each of the int is between 0 and 9, and with a further constraint that the digits increase in a non-strict monatonic way. You could do that with an 18 level nested for-loop, or you could do it with recursion. Anyway, the number of total loops changes from 10**18 to something more manageable, basically a time roughty factorial complexity. Once you've written that set of loops (prob. done with recursion, so it can do a variable-sized list), you need a function that tests is-lucky and another that calculates the number of permutations of that particular combinations of terms. DaveA -- DaveA ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] OverflowError in lucky numbers script
I have given the definition of lucky numbers and constraints involved at the starting of the thread. when a number's sum of digits and square of sum of digits is prime,it is called lucky. I already tried generating prime numbers using sieve of atkin algorithm rather than doing primality test. Efficiency improved a lot but still couldnt reach 16 sec target. The large numbers are the only hindrance to the speed. Since i m new to Python.I dont know all its recipes and tricks inlvolved to charm-the-snake. So can i improve the islucky method more than what i mentioned before? Can i work around that way in python or should i come up with a new algorithm? ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] OverflowError in lucky numbers script
On Mon, Jan 23, 2012 at 10:51 AM, Shreesh bhat shreeshbha...@gmail.comwrote: I have given the definition of lucky numbers and constraints involved at the starting of the thread. when a number's sum of digits and square of sum of digits is prime,it is called lucky. Just to clarify: do you mean (sum of digits) + (sum of digits)^2? If so, the ONLY lucky numbers are those whose digits add up to 1... because x + x^2 is always even (for real integers), and 2 is the only even prime number. So, if I understood your definition, here are the lucky numbers up to 10^18: 1 10 100 1000 ... 1 10 100 It seems to me that the problem can't possibly be that simple, so I must have misunderstood your definition. Please explain! ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] OverflowError in lucky numbers script
On Mon, Jan 23, 2012 at 11:42 AM, Marc Tompkins marc.tompk...@gmail.comwrote: On Mon, Jan 23, 2012 at 10:51 AM, Shreesh bhat shreeshbha...@gmail.comwrote: I have given the definition of lucky numbers and constraints involved at the starting of the thread. when a number's sum of digits and square of sum of digits is prime,it is called lucky. I suspect, however, you might have meant THESE lucky numbers: http://en.wikipedia.org/wiki/Lucky_number ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] OverflowError in lucky numbers script
No,i meant sum of digits is prime and also sum of square of digits is prime. E.g: 23 is lucky cos 2+3=5 (prime) 2**2+3**2 = 4+9 = 13 (prime) ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] OverflowError in lucky numbers script
On 23/01/12 18:51, Shreesh bhat wrote: Since i m new to Python.I dont know all its recipes and tricks inlvolved to charm-the-snake. So can i improve the islucky method more than what i mentioned before? Not by enough to meet your constraints. Just to be clear this has nothing to do with Python. It doesn't matter what programming language you choose there is not a PC on Earth that can do what you want using the technique you are using in 16 seconds. Can i work around that way in python or should i come up with a new algorithm? You definitely need a fundamentally different algorithm. -- Alan G Author of the Learn to Program web site http://www.alan-g.me.uk/ ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] OverflowError in lucky numbers script
On Mon, Jan 23, 2012 at 10:01:33PM +, Alan Gauld wrote: Just to be clear this has nothing to do with Python. It doesn't matter what programming language you choose there is not a PC on Earth that can do what you want using the technique you are using in 16 seconds. I don't believe that you could do it with the fastest supercomputer on earth. If you have to test 10**18 numbers in 16/10**5 seconds, that gives you less than 0.2 nanoseconds per test. This isn't a question of tweaking the code to make it run faster, you need a fundamentally different approach to the problem, as Alan says. Either that, or we have completely misunderstood the constraints of the puzzle. Can i work around that way in python or should i come up with a new algorithm? You definitely need a fundamentally different algorithm. I expect that this is some question from one of those annoying websites that offer extremely advanced mathematics puzzles disguised as a programming challenge. (Well I find them annoying. The answer almost always turns out to be something which took a genius of the level of Euler or Gauss to discover, and they expect you to come up with the answer on your own.) -- Steven ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] OverflowError in lucky numbers script
Hi On 23 January 2012 22:55, Steven D'Aprano st...@pearwood.info wrote: Can i work around that way in python or should i come up with a new algorithm? You definitely need a fundamentally different algorithm. I expect that this is some question from one of those annoying websites that offer extremely advanced mathematics puzzles disguised as a programming challenge. (Well I find them annoying. The answer almost always turns out to be something which took a genius of the level of Euler or Gauss to discover, and they expect you to come up with the answer on your own.) The OP previously posted the question, and having reread it I think perhaps he's too fixated on the maximum possible range in the spec/question which gives rise to an practically impossible computational burden. To be precise, I think trying to feed A=1 and B=10^18 seems to me to be asinine given that the the example test cases given in the problem statement uses values of A and B that are a) relatively small and b) quite close together. That therefore gives me the impression that being able to calculate all the answers for the whole 1...10^18 range is rather not expected. (The very fact that you need to specify a sub-range within which to calculate the lucky numbers in, implies that it's not expected, actually.) Anyway, for reference I post the original question again: *Lucky Numbers* A number is called lucky if the sum of its digits, as well as the sum of the squares of its digits is a prime number. How many numbers between A and B are lucky? Input: The first line contains the number of test cases T. Each of the next T lines contains two integers, A and B. Output: Output T lines, one for each case containing the required answer for the corresponding case. Constraints: 1 = T = 1 1 = A = B = 10^18 Sample Input: 2 1 20 120 130 Sample Output: 4 1 Explanation: For the first case, the lucky numbers are 11, 12, 14, 16. For the second case, the only lucky number is 120. Walter ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] OverflowError in lucky numbers script
On Mon, Jan 23, 2012 at 12:08 PM, Shreesh bhat shreeshbha...@gmail.comwrote: No,i meant sum of digits is prime and also sum of square of digits is prime. E.g: 23 is lucky cos 2+3=5 (prime) 2**2+3**2 = 4+9 = 13 (prime) Thanks for the clarification - or I should say correction, since sum of square of digits and square of sum of digits are NOT equivalent! ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] OverflowError in lucky numbers script
On 01/23/2012 10:31 PM, Marc Tompkins wrote: On Mon, Jan 23, 2012 at 12:08 PM, Shreesh bhatshreeshbha...@gmail.comwrote: No,i meant sum of digits is prime and also sum of square of digits is prime. E.g: 23 is lucky cos 2+3=5 (prime) 2**2+3**2 = 4+9 = 13 (prime) Thanks for the clarification - or I should say correction, since sum of square of digits and square of sum of digits are NOT equivalent! But Shreesh' original wording was: A number is called lucky if the sum of its digits, as well as the sum of the squares of its digits is a prime number. How many numbers between A and B are lucky? in a message 1/22/12 at 1:11, subject: Re: [Tutor] Tutor Digest, Vol 95, Issue 55 That thread soon got renamed to OverflowError in lucky numbers script -- DaveA ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] OverflowError in lucky numbers script
On Mon, Jan 23, 2012 at 8:03 PM, Dave Angel d...@davea.name wrote: On 01/23/2012 10:31 PM, Marc Tompkins wrote: On Mon, Jan 23, 2012 at 12:08 PM, Shreesh bhatshreeshbha...@gmail.com** wrote: No,i meant sum of digits is prime and also sum of square of digits is prime. E.g: 23 is lucky cos 2+3=5 (prime) 2**2+3**2 = 4+9 = 13 (prime) Thanks for the clarification - or I should say correction, since sum of square of digits and square of sum of digits are NOT equivalent! But Shreesh' original wording was: A number is called lucky if the sum of its digits, as well as the sum of the squares of its digits is a prime number. How many numbers between A and B are lucky? in a message 1/22/12 at 1:11, subject: Re: [Tutor] Tutor Digest, Vol 95, Issue 55 That thread soon got renamed to OverflowError in lucky numbers script Yes, but I - and apparently others - missed that thread; someone (Steven D'Aprano?) asked for a re-statement of the problem; the re-statement (which was the first time I'd seen the problem definition) was confusing. Sorry for starting a false trail; sorry for jumping in late. ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] OverflowError in lucky numbers script
On 01/23/2012 05:55 PM, Steven D'Aprano wrote: On Mon, Jan 23, 2012 at 10:01:33PM +, Alan Gauld wrote: Just to be clear this has nothing to do with Python. It doesn't matter what programming language you choose there is not a PC on Earth that can do what you want using the technique you are using in 16 seconds. I don't believe that you could do it with the fastest supercomputer on earth. If you have to test 10**18 numbers in 16/10**5 seconds, that gives you less than 0.2 nanoseconds per test. This isn't a question of tweaking the code to make it run faster, you need a fundamentally different approach to the problem, as Alan says. Either that, or we have completely misunderstood the constraints of the puzzle. I gave such an example approach, at 1:42 (actually, much earlier, but I forgot to change my send-from field, so Tutor bounced my message). You can search for the message using the string to do all the possible 18 digit numbers. I can solve the problem of finding how many lucky numbers in the entire range 1 through 10**18 in a reasonable time. I haven't coded the entire algorithm, but most of it exists, and takes 97 seconds for generating and testing for luckiness the 4,686,824 possible distinct sets of digits. Thus my outer loop goes around 4.6 million times, rather than 10**18 times. Incidentally, I made the 18 an argument to main(), so it's easy to test on smaller values. What I generate are all possible lists of digits, all of length 18, in which the digits are in sorted order. All that remains is multiplying the 1 or 0 for each of these 4.7 million lists by a number-of-permutations figure, which shouldn't be too hard to get. It would trivially be 18 factorial, except that there are variable numbers of duplicates among those 18 digits. Anyway, I claim that it won't add more than a few percent to finish the task. Call it 100 seconds. lots more than the 16 seconds originally specified for doing it 10,000 times. There are undoubtedly ways to optimize my code; I made no real attempt to be optimal. I just was worried about the algorithm. Only catch is that we might not want all 10**18 numbers. If we want a few million of them, all around 10**17, the original approach will work fine. And if we want them all, my approach will work. I haven't come up with a way to generalize either for things like solve it for the range 1234567890123456 through twice that value. -- DaveA ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
[Tutor] OverflowError in lucky numbers script, was Re: Tutor Digest, Vol 95, Issue 55
Shreesh bhat wrote: *Lucky Numbers* A number is called lucky if the sum of its digits, as well as the sum of the squares of its digits is a prime number. How many numbers between A and B are lucky? Input: The first line contains the number of test cases T. Each of the next T lines contains two integers, A and B. Output: Output T lines, one for each case containing the required answer for the corresponding case. Constraints: 1 = T = 1 1 = A = B = 10^18 Sample Input: 2 1 20 120 130 Sample Output: 4 1 Explanation: For the first case, the lucky numbers are 11, 12, 14, 16. For the second case, the only lucky number is 120. --- My solution: def isprime(n): n=abs(int(n)) if n2: return False if n==2: return True if not n 1: return False for x in range(3,int(n**0.5)+1,2): if n % x == 0: return False return True def islucky(n): sum1=0 sum2=0 while n!=0: r=n%10 sum1+=r sum2+=r*r n=n/10 if isprime(sum1) isprime(sum2): return True return False Don't use '' here, you're not bit-twiddling and the idiomatic code is return isprime(sum1) and isprime(sum2) which also has the advantage that it short-ciruits, i. e. isprime(sum2) is only evaluated if isprime(sum1) is true. number=raw_input() for i in range(int(number)): inp=raw_input() a=inp.split() startnum=int(a[0]) endnum=int(a[1]) li=map(islucky,xrange(startnum, endnum)) count=0 for j in li: if j: count+=1 print count --- Traceback (most recent call last): File /run-1327085301-1965755690/solution.py, line 35, in li=map(islucky,xrange(startnum, endnum)) OverflowError: Python int too large to convert to C long --- It shows this error for very large numbers or slows down with large numbers. I m using Ubuntu 32-bit. The arguments of xrange() are limited to C integers, they cannot be larger than sys.maxint (2**31-1 on a 32-bit system or 2**63-1 on a 64-bit system). range() can handle larger numbers, but you'll always see a slowdown -- larger numbers have more digits and (on average) larger sums, and thus take longer to test. ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
[Tutor] OverflowError in lucky numbers script
I m using Python 2.7 Steven wrote: Scale your numbers from time to time, to avoid them getting too big What does this mean? inp refers to the sample input test case I have given at first.Its a string containing two numbers, The program has to handle large numbers till 10**18 and also has to execute considerably fast (within 16 CPU time). Using xrange() causes the OveflowError,Whereas using range() causes too many items Is writing my own generator only solution? Or is there another way in which i can generate big numbers and in considerably fast manner? ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] OverflowError in lucky numbers script
Shreesh bhat wrote: I m using Python 2.7 Steven wrote: Scale your numbers from time to time, to avoid them getting too big What does this mean? inp refers to the sample input test case I have given at first.Its a string containing two numbers, The program has to handle large numbers till 10**18 and also has to execute considerably fast (within 16 CPU time). Using xrange() causes the OveflowError,Whereas using range() causes too many items Is writing my own generator only solution? Or is there another way in which i can generate big numbers and in considerably fast manner? If you look at the numbers $ python -m timeit -s'from lucky_number import islucky; start=10**10; stop=10**10+1000' 'i = start' 'while i stop:' ' islucky(i); i += 1' 100 loops, best of 3: 10.8 msec per loop $ python -m timeit -s'from lucky_number import islucky; start=10**10; stop=10**10+1000' 'i = start' 'while i stop:' ' i += 1' 1 loops, best of 3: 145 usec per loop you'll see that counting even with a primitive while loop takes less than two percent of the total time spent. This means you don't have to worry about that part of your script until you have come up with a luckiness test that is much faster than your current one. ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] OverflowError in lucky numbers script
On 01/22/2012 06:37 AM, Shreesh bhat wrote: I m using Python 2.7 Steven wrote: Scale your numbers from time to time, to avoid them getting too big What does this mean? inp refers to the sample input test case I have given at first.Its a string containing two numbers, The program has to handle large numbers till 10**18 and also has to execute considerably fast (within 16 CPU time). Using xrange() causes the OveflowError,Whereas using range() causes too many items Is writing my own generator only solution? Or is there another way in which i can generate big numbers and in considerably fast manner? Without knowing any constraints on the range (other than the limits are each less than 10**18), you either have to write your own generator or do a while loop. That's not your problem. Write one of them, and make sure your program now gets correct answers. Now you're apparently adding a new constraint execute considerably fast (within 16 CPU time). No idea what that means, but perhaps you left out the unit. Do you mean 16 minutes? When a program is correct, but too slow, you may need faster functions (like xrange is usually faster than range, and both are faster than one your wrote by hand). Or you may need a better algorithm. For each individual number, I think you would find that the bulk of the time is spent checking isprime(). There are functions that are much faster than the way you're doing, but I expect the time problem doesn't occur till you're checking lots of such numbers. When you have slow functions called lots of times, you can either speed up the function, or reduce the number of times its called. What I would do is figure out what the largest sum might be (9 * 19, more or less). Calculate the isprime(n) and isprime(n*n) for each of those, and save them in a table. Now your main loop can just sum the digits and consult the table. If that's not fast enough, optimize the way you sum the digits. -- DaveA ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] OverflowError in lucky numbers script
On 22/01/12 11:37, Shreesh bhat wrote:
Steven wrote:
Scale your numbers from time to time, to avoid them getting too big
What does this mean?
It could be done in various ways but one simple example is,
low = 100
hi = 110
for n in range(low,hi):
... code uses n ...
could also be written
span = hi-low
for n in range(span) # ie. range(10)
val = low + n
code uses val ...
Now the value given to range is a very small number...
Of course if low is zero and hi is large you need to think
again, so maybe you can break the range into chunks (eg. what
about using the square root?)? And process each chunk as above?
As I say there are lots of ways to do it, you need to think of one that
works for your data.
inp refers to the sample input test case I have given at first.Its a
string containing two numbers,
ok, so it contains the lo-hi pair?
Why not call it lo_hi
lo_hi = raw_input('Enter the low and high numbers')
Can you see how the combination of variable name and prompt string tells
the reader what is going on?
The program has to handle large numbers till 10**18 and also has to
execute considerably fast (within 16 CPU time).
I can promise you it will never run in 16 clock cycles...
Is writing my own generator only solution? Or is there another way in
which i can generate big numbers and in considerably fast manner?
Your problem is to avoid generating very big numbers wherever possible.
Construct them for output as needed but do the processing using smaller
ones. Just because Python supports arbitrarily large integers does not
mean you should use them in every case...
HTH,
--
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] OverflowError in lucky numbers script
You sent me this message privately, instead of on the list (use
Reply-All in most mail programs). Two problems with that: 1) nobody
else gets to help 2) I don't give private help, except as a contractor.
On 01/22/2012 12:44 PM, Shreesh bhat wrote:
*Lucky numbers:*
def sieve(maxi):
primes = range(2,maxi+1)
for i in primes:
j = 2
while i * j= primes[-1]:
if i * j in primes:
primes.remove(i*j)
j += 1
return primes
maxi=(9**2)*19
tab=sieve(maxi)
table={}
for i in tab:
table[i]=0
def isprime(n):
return table.has_key(n)
count=0
def islucky(n):
global count
sum1=0
sum2=0
for letter in str(n):
tmp=ord(letter)-48
sum1+=tmp
sum2+=tmp**2
if isprime(sum1):
if isprime(sum2):
count+=1
number=raw_input()
def execute():
global count
for i in range(int(number)):
inp=raw_input()
a=inp.split()
startnum=int(a[0])
endnum=int(a[1])
count=0
while startnum != endnum:
islucky(startnum)
startnum+=1
print count
execute()
Hi Sir,
The program still doesn't work with consult-table approach.
Define doesn't work. If you give a specific trace-back message,
somebody is bound to recognize the problem. Or if it doesn't give an
exception, describe in what way the answer is wrong. Or if it's
completely correct, but simply too slow, then say so.
I have also optimised digit's sum method.
Can you please tell me another method to work around it to get more
execution speed?
What part is slow? Calculating the table, or looping through your while
loop?
--
DaveA
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] OverflowError in lucky numbers script
Calculating the table is fast. I think either my luckiness test (where i find the sum of all digits and sum of squares of all digits of a large number) or generating numbers is slow. ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
[Tutor] OverflowError in lucky numbers script
Thank you all for helping me understand the overflow error.
I m a newbie on mailing lists.I apologize for my errors.
Program:
def sieve(maxi):
primes = range(2,maxi+1)
for i in primes:
j = 2
while i * j = primes[-1]:
if i * j in primes:
primes.remove(i*j)
j += 1
return primes
maxi=(10**2)*18 #Generating the table till the largest possible prime
tab=sieve(maxi)
table={}
for i in tab:
table[i]=0
def isprime(n):
return table.has_key(n)
count=0
def islucky(n): # modified islucky function
global count
sum1=0
sum2=0
for letter in str(n):
tmp=ord(letter)-48
sum1+=tmp
sum2+=tmp**2
if isprime(sum1):
if isprime(sum2):
count+=1
number=raw_input() # Number of test cases.Its constraint (1,1)
def execute():
global count
for i in range(int(number)):
inp=raw_input()# startnumber and endnumber pair. Its constraint
(1,10**18)
a=inp.split()
startnum=int(a[0])
endnum=int(a[1])
count=0
while startnum != endnum:
islucky(startnum)
startnum+=1
print count
execute()
The program is executing correctly but it has to execute 16 seconds for the
constraints.
I have optimized the way i sum up digits and used consult-table approach.
Still the program doesn't reach the 16 seconds target.
How to achieve this target?
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] OverflowError in lucky numbers script
On 23/01/2012 06:15, Shreesh bhat wrote: Calculating the table is fast. I think either my luckiness test (where i find the sum of all digits and sum of squares of all digits of a large number) or generating numbers is slow. Don't think, know :) Tools like the profile or timeit modules are there for a purpose so use them. Cheers. Mark Lawrence. ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
