Infinite Prime Number Generator In Python

October 18th 2010

I was looking at this article (The Genuine Sieve of Eratosthenes / PDF) about a common functional prime number generator that is mistakenly called the Sieve of Eratosthenes.

It is quite complicated, section 2 deals with the performance of the naive algorithm and 3 implements the sieve properly. I could not quite grok the Haskell but the following quote helped me know what was going on

Whereas the original algorithm crosses off all multiples of a prime at once, we perform these “crossings off” in a lazier way: crossing off just-in-time. For this purpose, we will store a table in which, for each prime p that we have discovered so far, there is an “iterator” holding the next multiple of p to cross off. Thus, instead of crossing off all the multiples of, say, 17, at once (impossible, since there are infinitely many for our limit-free algorithm), we will store the first one (at 17 × 17; i.e., 289) in our table of upcoming composite numbers. When we come to consider whether 289 is prime, we will check our composites table and discover that it is a known composite with 17 as a factor, remove 289 from the table, and insert 306 (i.e., 289+17). In essence, we are storing “iterators” in a table keyed by the current value of each iterator.

Here it is using a dictionary for each composite number with a list of increments it was reached by:

```from itertools import count

def gen_primes():
yield 2
def update_composites(number,increment):
try:
composites[number] += [increment]
except:
composites[number] = [increment]

composites = {4:[2]}

c = count(3)
while 1:
#print composites
next = c.next()
smallest = min(composites.keys())
incs = composites[smallest]
del composites[smallest]
for inc in incs:
update_composites(smallest+inc,inc)
if next < smallest:
yield next
c.next()
update_composites(next**2,next)

g=gen_primes()

for i in range(100):
print g.next()
```

(On Github)

They mention a speedup moving to a heapqueue as the data structure (as we just take the lowest each lookup) so I implemented that too, here is the code

```
from itertools import count
from heapq import heappush,heappop

def gen_primes():
yield 2

def update_composites(number,increment):
heappush(composites,(number,increment))
composites = [(4,2)]

c = count(3)

while 1:
#print composites
smallest,increment = heappop(composites)
update_composites(smallest+increment,increment)
if composites[0][0] == smallest:
continue
next = c.next()
if next < smallest:
yield next
c.next()
update_composites(next**2,next)

g=gen_primes()

for i in range(100):
print g.next()
```

(On github)

Posted by tom under euler & Mathematics & Python | No Comments »

Learning Ruby: methods vs procs (or Ruby vs Python?)

October 4th 2010

I have been meaning to learn ruby for a while and the place I am working now uses a lot so I had another look at it. I read Learn To Program, a simple but good book and found the bit on blocks and procs etc pretty good and wanted to see if I could do the stuff in Python as well. Python has anonymous “lambda” functions but they are limited to one line a subset of the syntax which is a bit annoying sometimes. My worry with methods in Ruby is that they are not first class, I think because you can omit parenthesis and so you have no way of referring to them without invoking them.

I remembered this while reading the SICP book, the question was about the difference between this program in applicative and normal order evaluation

```(define (p) (p))

(define (test x y)
(if (= x 0)
0
y))```

It rang a bell as (define (p) p) does not go into an infinite loop if you invoke p. In lisp (p) calls the procedure p with no arguments whereas p is just a reference to the function. In python someinstance.method refers to the method, someinstance.method() calls it, Ruby seems to need Proc objects to get around this (IMHO as a beginner!, see the end for John Leach’s lovely response via email at the time)

I redid all the examples from the book in Python

Eg 1
Ruby

```def maybe_do some_proc
if rand(2) == 0
some_proc.call
end
end

def twice_do some_proc
some_proc.call
some_proc.call
end

wink = Proc.new do
puts '<wink>'
end

glance = Proc.new do
puts '<glance>'
end
```

Python

```import random

def maybe_do(some_proc):
if random.choice(range(2)) == 0:
some_proc()

def twice_do(some_proc):
some_proc()
some_proc()

def wink():
print 'wink'

def glance():
print 'glance'

for i in range(5):
print 'running for i=',i
maybe_do(wink)
```

Eg2
Ruby

```def do_until_false first_input, some_proc
input = first_input
output = first_input
while output
input = output
output = some_proc.call input
end
input
end

build_array_of_squares = Proc.new do |array|
last_number = array.last
if last_number <= 0
false
else
# Take off the last number...
array.pop
# ...and replace it with its square...
array.push last_number*last_number
# ...followed by the next smaller number.
array.push last_number-1
end
end

always_false = Proc.new do |just_ignore_me|
false
end

puts do_until_false([5], build_array_of_squares).inspect

yum = 'lemonade with a hint of orange blossom water'
puts do_until_false(yum, always_false)
```

Python

```def do_untill_false(first_input, some_proc):
input = first_input
output = first_input
while output:
input = output
output = some_proc(input)
return input

def build_array_of_squares(array):
last_number = array.pop()
if last_number <= 0:
return False
else:
array.append(last_number * last_number)
array.append(last_number - 1)
return array

def always_false(just_ignore_me):
return False

def just_ignore_me():
pass

print do_untill_false([5], build_array_of_squares)
yum = 'lemonade with a hint of orange blossom water'
print do_untill_false(yum, always_false)
```

Eg3
Ruby

```def compose proc1, proc2
Proc.new do |x|
proc2.call(proc1.call(x))
end
end

square_it = Proc.new do |x|
x*x
end

double_it = Proc.new do |x|
x+x
end

double_then_square = compose double_it, square_it

square_then_double = compose square_it, double_it

puts double_then_square.call(5) puts square_then_double.call(5)
```

Python

```def compose(proc1,proc2):
def composed(x):
return proc2(proc1(x))
return composed

def square_it(x):
return x**2

def double_it(x):
return x*2

double_then_square = compose(double_it,square_it)
square_then_double = compose(square_it,double_it)

print double_then_square(5)
print square_then_double(5)
```

Eg4

```class Array
def each_even(&was_a_block__now_a_proc)
is_even = true
self.each do |object|
if is_even
was_a_block__now_a_proc.call object
end
# Toggle from even to odd, or odd to even.
is_even = !is_even
end
end
end

fruits = ['apple', 'bad apple', 'cherry', 'durian']
fruits.each_even do |fruit|
puts "Yum! I just love #{fruit} pies, don't you?"
end

[1, 2, 3, 4, 5].each_even do |odd_ball|
puts "#{odd_ball} is NOT an even number!"
end
```

Python

```class MyArray(list):
def each_even(self):
for i in range(len(self)):
if i % 2 == 0:
yield self[i]

fruits = MyArray(['apple', 'bad apple', 'cherry', 'durian'])

for fruit in fruits.each_even():
print 'yum! I love %s pies, dont you?' % fruit

for odd_ball in MyArray([1,2,3,4,5]).each_even():
print '%s is NOT an even number' % odd_ball
```

Eg5
Ruby

```def profile block_description, &block
start_time = Time.new
block.call
duration = Time.new - start_time
puts "#{block_description}: #{duration} seconds"
end

profile '25000 doublings' do
number = 1
25000.times do
number = number + number
end

puts "#{number.to_s.length} digits"
# That's the number of digits in this HUGE number.
end

profile 'count to a million' do
number = 0 1000000.times do
number = number + 1
end
end
```

Python

```def profile(description, function):
import time
start_time = time.time()
function()
duration = time.time() - start_time
print '%s: %s seconds' % (description, duration)
print function.__name__
print 'see, "function.__name__" can be used in place of description in python'

def count_to_a_million():
number = 0
for i in range(1000000):
number = number+1

profile('count to a million', count_to_a_million)

def profiled(function):
def new_function(*args, **kwargs):
import time
start_time = time.time()
result = function(*args, **kwargs)
print function.__name__, 'took', time.time() - start_time, 'secs'
return result
return new_function

@profiled
def count_to_a_million_again():
number = 0
for i in range(1000000):
number = number + 1

count_to_a_million_again()
```

This uses decorators, a nice Python feature that uses higher order functions (and the fact functions are first class in python).

In Conclusion
IMHO, at this point in my experience of Ruby, with all the disclaimers about my non expert status etc.
Like:

• No restriction on complexity of anonymous functions

Dont Like:

• Methods being different from Procs/Blocs, non-uniform syntax
• Leaving out parenthesis (though I await DSL goodness later!)
• “end” everywhere (I know the indentation thing in python is contentious!)

John Leach’s thought provoking tuppence

Young padawan, you look but you do not see, you will learn

or rather

Yeah, but blocks are closures Tom

Tom goes to google and comes back with http://www.artima.com/intv/closures2.html
Matz

I think it’s not that useful in the daily lives of programmers. It doesn’t matter that much.

Then john came back with

`I can think of one example in Rails right away where it's useful, transactions:`

```r = Record.new params[:record]

Record.transaction do
r.save
RecordLog.create(:text => "created a new record")
end
```

``` that code takes some input from a browser (in params), instantiates a new Record object, then writes it and a RecordLog entry to the database atomically. All the Record.transaction does is sends a BEGIN to the db server, executes the block, and sends a COMMIT (or a ROLLBACK if the block errors for any reason). The block needs access to the r object. We could have created that inside the block, but then it'd need access to the params object. So without real closure support, Record.transaction would have had to support passing in arbitrary variables. Remember, that interview with Matz was in 2003 - more people are using Ruby for more things nowadays, for uses beyond the imagination of it's creator I'm sure ```

Final Thoughts
I am waiting to be blown away by Ruby and Rails

Posted by tom under Python & Ruby | No Comments »

Project Euler 39

April 12th 2008

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.
{20,48,52}, {24,45,51}, {30,40,50}
For which value of p < 1000, is the number of solutions maximised?

WARNING: CONTAINS MATHEMATICS

Posted by tom under euler & Mathematics & Python | 2 Comments »

Python talk for WYLUG, Ruby envy, Haskell Joy.

December 27th 2007

I am just getting a talk ready for WYLUG on python.

I sent Dave the following blurb:

Why I love Python:

A talk on the programming language Python, in 3 parts (feel free to
leave in the interludes if you have had enough)

Part 1: Past, Present, Future.
A bit of history and the design of the language, a look at all the
implementations available today, quick tour of built-in and commonly
used modules and future plans.

Part 2: Language overview
A quick tour of the language: builtin types, control structures, using
modules etc

Part 3: Recent Magic.
Some relatively recent changes that make programming Python even more
pleasurable.
Decorators, Generators, List comprehensions, Iterators, Functools and
anything else I can fit in.
Again a whirlwind tour, but you should be impressed and want to read
up on these some more

I have been revisiting some of the Python talks I have watched over the last few years for ideas and will update my ComSci page with links.

I stumbled across some excellent video from RubyConf, particularly the Rubinius one. Rubinius is a ruby VM partially written in Ruby, taking some lessons from Python and Smalltalk. Some of the stuff he bigs up (compiling to bytecode automatically comes to mind) Python has had for ages, but the self hosting aspect is cool (not as cool as PyPy though). Rubinius seems to be doing what Avi Bryant suggested here, learn from the Smalltalk guys and the papers from the Self team that Sun spun off and later bought back to do the hotspot VM for Java. Interesting times for dynamic languages, target the JVM, CLR, self host and generate code in other languages while always writing in the same fun language. I say Ruby envy only because I think the Ruby community does a better job of looking cool and exciting people than the Python one.

Now Haskell joy. After describing working through Yet Another Haskell Tutorial to the 2 friends doing it with me as “not an obviously pleasurable experience” I had a great moment on the train the other day looking at partial application.
`(\y -> y*3)`
is Haskell for the anonymous function that takes y and multiplies it by 3 (I wish I had LaTeX here to draw the lamda calculus). What I like is that you can also write that as
`(*3)`
While this example is trivial, what is happening is interesting. The compiler knows * is an infix operator that takes 2 arguments and that is has been supplied one and “partially applies” the function, making (*3) (a function that takes one argument). One more thing is changing prefix and infix operators around using ( _ ) and ` _ ` , for example:
```3 * 5 (*) 3 5 ```
```map (*2) [1,2,3] (*2) `map` [1,2,3] ```
I hope this second example is clear, map usually is a prefix function that takes a function and a list and returns a list with the result of applying the function to each element (the return value here would be [2,4,6]). This flexibility is neat and is starting to make Haskell a joy to hack in.

Merry Christmas,

Posted by tom under haskell & Python & Ruby | No Comments »

Second Python User Group meeting

December 7th 2007

I gave a talk at the second python user group in leeds on Wednesday. It was called “Anatomy Of A Python Program – How Much Can You Do In 0.1 KLOC?”. It is based on Peter Norvigs Sudoku solver. I had been thinking about doing it for WYLUG, possibly as a second talk after an intro to python. The slides were the same, but instead of looking at cool features of python that make the code so concise we critiqued it a bit and spoke about the style and possible speedups. The slides for the talk is here, but as I did not add any notes, you would be better off just reading Norvigs article (though the Javascript slideshow is cool, press t to toggle views)

The slideshow was made using rst2s5 and I am amazed how well it works. Restructuredtext is from Pythons Docutils and is a simple markup language designed to be readable as plain text, see here for details. Below is part of the code for my presentation

Posted by tom under Python | No Comments »

RubyQuiz 148 – Postfix to Infix

December 1st 2007

I have been meaning for some time to tackle the RubyQuiz problems in Python.

The one from yesterday (#148) is quite interesting, taking postfix notated expressions and returning an infix version.

For example
2 3 5 + * -> 2 * (3 + 5)

I spoilt it a bit by reading Reverse Polish Notation on Wikipedia, which gave away how to evaluate the postfix expressions.

Here is my python code to evaluate postfix expressions

Posted by tom under Python & RubyQuiz | 1 Comment »

Tommys Project

November 15th 2007

I posted last time about TeXmacs and remembered the plugins for using it to display output from some of the superb free maths packages (which sometimes lack a nice display).

The one I am excited about most is for SAGE. SAGE is written in python and leverages the hard work of the other projects (its motto is Building the Car Instead of Reinventing the Wheel). See the TeXmacs plugin here and some screenshots of SAGE here.

I will take a look at the code and see if I can contribute anything, it will be nice to get involved in a big project.

Posted by tom under Mathematics & Python | No Comments »