Build a Collatz conjecture solver with Python and ZeroMQ

Connecting computers is so difficult that software and services to do this is a multi-billion dollar business. So today we’re still connecting applications using raw UDP and TCP, proprietary protocols, HTTP, Websockets. It remains painful, slow, hard to scale, and essentially centralized.

To fix the world, we needed to do two things. One, to solve the general problem of “how to connect any code to any code, anywhere”. Two, to wrap that up in the simplest possible building blocks that people could understand and use easily. It sounds ridiculously simple. And maybe it is. That’s kind of the whole point. Zero MQ comes to rescue us from the problem.With averge hardware configuration, we can handle 2.5-8 Million messages/second using ZeroMQ.

What is ZMQ?

ZeroMQ is a library used to implement messaging and communication systems between applications and processes – fast and asynchronously.It is faster like a bullet train.You can use it for multiple purposes.Like the things listed below.

* Networking and concurrency library

* Asynchronous messaging

* Brokerless communication

* Multiple transport

* Cross-platform and open-source

Why a message queue is required in the distributed applications and how ZeroMQ can be used as the best communication practise between applciations will be explained in few minutes.

Selection_001

I guess you captured the logic from above pic.Instead of hitting the server directly for each request  we can push it into a message queue and process it by workers , then route it to appropriate location. Ok, now context switch to collatz conjecture.

What is Collatz conjecture?

This is the 3n+1 mathematical problem (or Collatz conjecture). Collatz conjecture states that for any number n, the following function f(n) will always boil down to 1 as  result, if you keep feeding the previous result to the function over and over again.
  f(n) = {
           3n+1, if n is odd,
           n/2, if n is even
           1, if n is 1
        }
Eg: if n = 20, then:
           f(20) = 20/2 = 10
           f(10) = 10/2 = 5
           f(5)  = 3*5+1 = 16
           f(16) = 16/2 = 8
           f(8)  = 8/2 = 4
           f(4)  = 4/2 = 2
           f(2)  = 1
The term cycle count refers to the length of the sequence of numbers generated. In the above case, cycle count for f(20) is 9.
We are going to build a collatz conjecture cycle finding server using Python and ZeroMQ. complete code of this project is available at this location

Beauty of collatz conjecture

All numbers leads to one. It is the philosophy of collatz conjecture. visit this site to visually see the construction of collatz numbers for orbital length of 18.
1011-collatz-graph.v01

Let us build a Collatz Conjecture Cycle Server

Now come to the coding part.Our aim is to construct the server that takes a number from client and calculates longest collatz cycle from 1 to that number and returns it back. For ex. If we give input of 1000 our server should calculate collatz cycles for 1,2,3,……..,1000 seperately and return the longest cycle of all.

Ingredients

  • Python
  • ZeroMQ
  • Gevent

we can build the same server with Python and Gevent alone , but that setup is vulnerable after 10K connections. For scaling it to millions ,we should use the power of ZeroMQ.

Requirements

  • Install  ZeroMQ4.1.2 ( http://zeromq.org/intro:get-the-software ) .Below process shows step wise installation procedure.
$ sudo apt-get install uuid uuid-dev uuid-runtime
$ sudo apt-get install libzmq-dbg libzmq-dev libzmq1
$ sudo apt-get install build-essential gcc
$ cd tmp/ && wget http://download.zeromq.org/zeromq-4.1.2.tar.gz
$ tar -xvf zeromq-4.1.2.tar.gz && cd ./zeromq-4.1.2.tar.gz
$ ./configure && make
$ sudo make install
$ sudo ldconfig
  • Install pyzmq
$ sudo apt-get install python-dev
$ sudo pip install pyzmq
  • Install gevent
$ sudo pip install gevent

Please be aware that ZeroMQ installation will fail if all deapendecies are not installed. pyzmq installation will fail if python-dev library deapendency is not fulfilled. I hope now you are ready with the required set up on a Ubuntu 14.04 machine.

This ZeroMQ server is used to serve requests through a TCP port to which a zmq socket is attached. Server collects data from that bound socket. let us first design function for returning maximum collatz cycle for a given inupt range. That algorithm would look like below

Collatz Conjecture Algorithm

import gevent
from gevent import monkey

monkey.patch_all()

#Algorithm for finding collatz conjecture longest cycle.
#Returns max cycle from cycles calculated from 1 to n.
def do_collatz(n):
    def collatz(n,cycle=''):
        while True:
            if n == 1:
                cycle += str(n)
                break
            else:
                if n % 2 == 1:
                    n = ( 3 * n ) + 1
                    cycle += str(n)
                else:
                    n = n/2
                    cycle += str(n)
       return len(cycle)
    #This Gevent code is for speeding up the calculation of cycles
    jobs = [ gevent.spawn(collatz, x) for x in range(1,n) ]
    gevent.joinall(jobs)
    return max([g.value for g in jobs])

Now let us use this function in our ZeroMQ server that we are going to write below. It just recieves a number from client and calls this do_collatz function and returns the longest cycle back to the client.

ZeroMQ Collatz Server

#zmq_collatz_server.py

import time
import zmq
import gevent
from gevent import monkey

monkey.patch_all()

#Create context
context = zmq.Context()

#Set type of socket
socket = context.socket(zmq.REP)

#Bind socket to port 5555
socket.bind("tcp://*:5555")

#Algorithm for finding collatz conjecture
def do_collatz(n):
    def collatz(n,cycle=''):
        while True:
            if n == 1:
                cycle += str(n)
                break
            else:
                if n % 2 == 1:
                    n = ( 3 * n ) + 1
                    cycle += str(n)
                else:
                    n = n/2
                    cycle += str(n)
       return len(cycle)
    #This Gevent code is for speeding up the calculation of cycles 
    jobs = [ gevent.spawn(collatz, x) for x in range(1,n) ]
    gevent.joinall(jobs)
    return max([g.value for g in jobs])

#Create a loop and listen for clients to send requests 
while True:
    # Wait for next request from client
    number = int(socket.recv())
    print("Received request for finding max collatz cycle between 1.....%s" % number)
    # Send reply back collatz conjecture maximum cycle to client
    num = str(do_collatz(number))
    socket.send(num)

 

Now we have a server ready to serve any no of clients.Let us build a ZeroMQ client to send request to above server and recieves the maximum collatz cycle for a given no.

ZeroMQ Collatz Client

#zmq_collatz_client.py

import zmq
context = zmq.Context()

# Socket to talk to server
print 'Connecting to hello world server'

socket = context.socket(zmq.REQ)
socket.connect("tcp://localhost:5555")

number = raw_input("please give a no to calculate collatz conjecture max cycle: ")
print 'Sending request %s ' % number
#Send number to server
socket.send(number)
#Wait and print result
message = socket.recv()
print 'Collatz Conjecture max cycle of %s is <[ %s ]>' % (number, message)

That’s it. Our client is ready too. Now open the terminal with three tabs. One for server and other two for two clients to send the request. The output looks like this on my Ubuntu  14.04 machine.

Next try to give input 1000 from one client and 7000 from another client. Server instantly return maximum collatz cycle back to the client. It looks like this.

Selection_003

So it is clearly visible that our ZeroMQ server is working perfectly for serving the clients and solves collatz conjecture problem. This is called Request-Reply pattern of implementation of ZeroMQ. Here communication is acheived through TCP rather than HTTP. There are three more patterns can be implemented using ZeroMQ. They are:

  • Publish/Subscribe Pattern: Used for distributing data from a single process (e.g. publisher) to multiple recipients (e.g. subscribers).
  • Pipeline Pattern: Used for distributing data to connected nodes.
  • Exclusive Pair Pattern: Used for connecting two peers together, forming a pair.

So ZeroMQ has a lot of scope. It is a good scalability solution for current distributed application architectures. All code for above collatz-cycle is availlable at below github link.

https://github.com/narenaryan/collatz-cycle-server

References:

https://www.digitalocean.com/community/tutorials/how-to-work-with-the-zeromq-messaging-library

http://zeromq.org/intro:read-the-manual

https://speakerd.s3.amazonaws.com/presentations/8035a1002fcd013209132673290742c6/ZeroMQ.pdf

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s