This is a Python 3.6.0 client and server. The client will pass a number n to the server and the server will then compute the nth Fibonacci number and return it to the client.
$ ./runserver.sh &
$ python3 socket_client.py 10
55
$ python3 socket_client.py 100
354224848179261915075
This is a coding exercise for a pretty cool job :)
Requirements:
- Python 3.6.0
- Bash shell
This is built with Python 3.6.0 and uses only standard modules from it; it should not require any extra modules installed.
- First, make sure Python 3.6.0 is downloaded and installed.
- Check git is also installed
- git clone https://github.com/cmavromichalis/PythonFibb.git
- cd PythonFibb/
- ./runserver.sh &
- python3 socket_client.py 10000
The server will listen for connections on port 8080 and expects to receive in bytes an unsigned integer
The algoirthm is:
- a = 0
- b = 1
- loop
- old_b = b
- b += a
- a = old_b
- old_b = b
Using a 2.5Ghz Intel Core i7 with 16GB of ram here were my calculation times and digits:
| n digits | time to compute (in seconds) |
|---|---|
| 1 | 0.000 |
| 10 | 3.099 * 10^-6 |
| 100 | 1.215 * 10^-5 |
| 1,000 | 1.268 * 10^-4 |
| 10,000 | 2.831 * 10^-3 |
| 100,000 | 1.103 |
| 1,000,000 | 10.534 |
| 10,000,000 | 981.280 |
| 11,000,000 | 1167.472 |
| 12,000,000 | 1386.853 |
| 13,000,000 | 1634.921 |
| 14,000,000 | 1904.276 |
| 15,000,000 | 2185.392 |
The max nth number you can request is limited to 2,468 digits long. The time it takes is dependent on how long you want to wait. With my timings from above, calculation time grows linearly with 10 million digits taking 16 minutes + time to transmit; about 20 minutes.
To run tests test.sh is included which will test:
- Fibonacci numbers are correct using known good values
- Bad parameters are not accepted
- That the server responds asynchronously
Some desired optimizations to have in this would be:
- A faster algorithm, I'm sure that there are better ones than this simple one
- Fast transmitting of data, when the numbers get huge it takes time to transfer them. Maybe this can be accomplished quicker.
- Memory thrashing, trying to compute 1,000,000,000 digits takes a really long time. It never finished for me. I think because the numebrs get so bug that memory thrashes.
MIT