Re: Remarkable results with psyco and sieve of Eratosthenes
> BTW, can this code be made any more efficient? I'm not sure, but the following code takes around 6 seconds on my 1.2Ghz iBook. How does it run on your machine? def smallPrimes(n): """Given an integer n, compute a list of the primes < n""" if n <= 2: return [] sieve = range(3, n, 2) top = len(sieve) for si in sieve: if si: bottom = (si*si - 3)//2 if bottom >= top: break sieve[bottom::si] = [0] * -((bottom-top)//si) return [2]+filter(None, sieve) smallPrimes(10**7) > > > > #!/usr/bin/python -OO > import math > import sys > import psyco > > psyco.full() > > def primes(): > primes=[3] > for x in xrange(5,1000,2): > maxfact = int(math.sqrt(x)) > flag=True > for y in primes: > if y > maxfact: > break > if x%y == 0: > flag=False > break > if flag == True: > primes.append(x) > primes() -- http://mail.python.org/mailman/listinfo/python-list
Re: Remarkable results with psyco and sieve of Eratosthenes
On Nov 29, 6:59 pm, "Steve Bergman" <[EMAIL PROTECTED]> wrote: > [EMAIL PROTECTED] wrote: > > > BTW, can this code be made any more efficient? > > > I'm not sure, but the following code takes around 6 seconds on my > > 1.2Ghz iBook. How does it run on your machine? > > Hmm. Come to think of it, my algorithm isn't the sieve. Right. I guess the point of the sieve is that you don't have to spend any time finding that a given odd integer is not divisible by a given prime; all the multiplies are done up front, so you save all the operations corresponding to the case when x % y != 0 in your code. Or something. > Anyway, this is indeed fast as long as you have enough memory to handle > it for the range supplied. The sieve can be segmented, so that the intermediate space requirement for computing the primes up to n is O(sqrt(n)). (Of course you'll still need O(n/log n) space to store the eventual list of primes.)Then there are all sorts of bells and whistles (not to mention wheels) that you can add to improve the running time, most of which would considerably complicate the code. The book by Crandall and Pomerance (Primes: A Computational Perspective) goes into plenty of detail on all of this. Mark Dickinson -- http://mail.python.org/mailman/listinfo/python-list
Re: Mirror imaging binary numbers
On Dec 6, 6:01 pm, "Craig" <[EMAIL PROTECTED]> wrote: > Thanks so much for the response. I have an array of individual bytes > which will eventually make up a binary bitmap image that is loaded onto > an LCD screen (1 = black dot, 0 = white dot). At the moment each byte > is reversed to what it should be (completely reverse the bit order): > e.g 0001 should be 1000, 11001100 should be 00110011, etc. It > is not an int problem as such, it is more a bit level swap if you get > what I mean. If you could help that would be great. Yet another solution: def flipbits(x): """reverse bits in a byte""" x1 = x << 4 | x >> 4 x2 = (x1 & 51) << 2 | (x1 & 204) >> 2 return (x2 & 85) << 1 | (x2 & 170) >> 1 The idea is to first swap the two nybbles, then swap bits 0, 1, 5, 6 with 2, 3, 6, 7 respectively, and finally swap bits 0, 2, 4, 6 with bits 1, 3, 5, 7 respectively. Mark -- http://mail.python.org/mailman/listinfo/python-list
Re: Mirror imaging binary numbers
On Dec 6, 7:20 pm, Grant Edwards <[EMAIL PROTECTED]> wrote: > It's a little less obtuse if you spell it this way: > > def flipbits(x): > """reverse bits in a byte""" > x1 = x << 4 | x >> 4 > x2 = (x1 & 0x33) << 2 | (x1 & 0xcc) >> 2 > return (x2 & 0x55) << 1 | (x2 & 0xaa) >> 1 > Granted. And a little more obtuse this way: def flipbits(x): """reverse bits in a byte""" x += 255*(x & 15) x += 15*(x & 816) x += 3*(x & 5440) return x >> 7 I apologise---it's the end of a long day and I'm feeling more than a little contrary. Mark -- http://mail.python.org/mailman/listinfo/python-list
Re: Shortest prime number program
swisscheese wrote: > > r=range(2,99) > m=[x*y for x in r for y in r] > [x for x in r if not x in m] How about: [2]+[x for x in range(1,99) if 2**x%x==2] Mark -- http://mail.python.org/mailman/listinfo/python-list
Conflicting needs for __init__ method
Here's an example of a problem that I've recently come up against for the umpteenth time. It's not difficult to solve, but my previous solutions have never seemed quite right, so I'm writing to ask whether others have encountered this problem, and if so what solutions they've come up with. Suppose you're writing a class "Rational" for rational numbers. The __init__ function of such a class has two quite different roles to play. First, it's supposed to allow users of the class to create Rational instances; in this role, __init__ is quite a complex beast. It needs to allow arguments of various types---a pair of integers, a single integer, another Rational instance, and perhaps floats, Decimal instances, and suitably formatted strings. It has to validate the input and/or make sure that suitable exceptions are raised on invalid input. And when initializing from a pair of integers---a numerator and denominator---it makes sense to normalize: divide both the numerator and denominator by their greatest common divisor and make sure that the denominator is positive. But __init__ also plays another role: it's going to be used by the other Rational arithmetic methods, like __add__ and __mul__, to return new Rational instances. For this use, there's essentially no need for any of the above complications: it's easy and natural to arrange that the input to __init__ is always a valid, normalized pair of integers. (You could include the normalization in __init__, but that's wasteful when gcd computations are relatively expensive and some operations, like negation or raising to a positive integer power, aren't going to require it.) So for this use __init__ can be as simple as: def __init__(self, numerator, denominator): self.numerator = numerator self.denominator = denominator So the question is: (how) do people reconcile these two quite different needs in one function? I have two possible solutions, but neither seems particularly satisfactory, and I wonder whether I'm missing an obvious third way. The first solution is to add an optional keyword argument "internal = False" to the __init__ routine, and have all internal uses specify "internal = True"; then the __init__ function can do the all the complicated stuff when internal is False, and just the quick initialization otherwise. But this seems rather messy. The other solution is to ask the users of the class not to use Rational() to instantiate, but to use some other function (createRational(), say) instead. Then __init__ is just the simple method above, and createRational does all the complicated stuff to figure out what the numerator and denominator should be and eventually calls Rational(numerator, denomiator) to create the instance. But asking users not to call Rational() seems unnatural. Perhaps with some metaclass magic one can ensure that "external" calls to Rational() actually go through createRational() instead? Of course, none of this really has anything to do with rational numbers. There must be many examples of classes for which internal calls to __init__, from other methods of the same class, require minimal argument processing, while external calls require heavier and possibly computationally expensive processing. What's the usual way to solve this sort of problem? Mark -- http://mail.python.org/mailman/listinfo/python-list
Re: random number including 1 - i.e. [0,1]
Esmail wrote: > Hi, > > random.random() will generate a random value in the range [0, 1). > > Is there an easy way to generate random values in the range [0, 1]? > I.e., including 1? > > [...] Here are three recipes, each more pedantic than the last. They all assume that Python floats are IEEE 754 binary64 format (which they almost certainly are on your machine), and that randrange generates all values with equal likelihood (which it almost certainly doesn't, but the assumption should be good enough for government work). import random def random1(): """Random float in [0, 1]. Generates all floats of the form n/2**53, 0 <= n <= 2**53, with equal probability. """ return random.randrange(2**53+1)/2.**53 def random2(): """Random float in [0, 1]. Generates all floats of the forn n/2**53, 0 <= n <= 2**53, with values in (0.0, 1.0) equally likely, and the endpoints 0.0 and 1.0 occuring with half the probability of any other value. This is equivalent to generating a random real number uniformly on the closed interval [0, 1] and then rounding that real number to the nearest float of the form n/2**53. """ return (random.randrange(2**54)+1)//2/2.**53 def random3(): """Random float in [0, 1]. Generates *all* floats in the interval [0.0, 1.0] (including 0.0 and 1.0, but excluding -0.0). Each float is generated with a probability corresponding to the size of the subinterval of [0, 1] that rounds to the given float under round-to-nearest. This is equivalent to generating a random real number uniformly on the closed interval [0, 1] and then rounding that real number to the nearest representable floating-point number. """ m = (random.randrange(2**53)+1)//2 e = 1022 while random.randrange(2) and e: e -= 1 return (m+2**52) * 2.**(e-1075) if e else m*2.**-1074 -- Mark Dickinson -- http://mail.python.org/mailman/listinfo/python-list
