06/18/13

The Speed of Multiplication

For the most part, all of us take for granted that the cpu can do multiplication in a timely matter. However, there are some systems that do not have multiplication. Furthermore, how is multiplication actually done? Multiplication is nothing more than repeated applications of additions. For example, if we want to compute 5 x 4 we can add 5 4 times or add 4 5 times and keep track of the sum. Let’s take a look how this might look like in Python 2.7.


import sys

def main(argv):

if len(argv) != 2:
sys.exit('Usage: simple_multi.py <a> <b>')

a = int(sys.argv[1])
b = int(sys.argv[2])
sum = 0

for i in range(a):
sum += b

print "The result of " + str(a) + " times " + str(b) + " is: " + str(sum)

if __name__ == "__main__":
main(sys.argv[1:])

And the output:

Sweet. Now for most of you this will be it. Trust me, for me the multiplication symbol is it. I never thought I will have to code multiplication. That is until it came up. I have a friend who happens to be a mathematician with a particular fascination to numbers and counting. So he came up to me claiming that he has this fast way to do multiplication that has to do with the ten’s places and basic multiplication. Basic multiplication being the 10 x 10 grid (or 12 x 12) we all had to memorize at some point. So I decided to put him up for the test, I wrote his algorithm in Python as well as the one above and Russian Multiplication. I won’t spend time trying to explain the algorithms. If you want to, you will find the link helpful enough to explain Russian Multiplication. If you want to find out more about my friend’s Ten’s Multipication, send him a message on his blog DeadEndMath. All in python, running on the same computer with the same Linux time command measuring their performance. Before we get to the data, let’s take a look at the code:

Ten’s Multiplication:


import sys

def main(argv):

if len(argv) != 2:
sys.exit('Usage: tens_multi.py <a> <b>')

a = sys.argv[1]
b = sys.argv[2]
sum = 0;
c = len(a) - 1;

for i in a:
d = len(b) - 1;
for j in b:
sum += int(i)*int(j)*(10**c)*(10**d);
d -= 1;
c -= 1;

print "The result of " + a + " times " + b + " is: " + str(sum)

if __name__ == "__main__":
main(sys.argv[1:])

And the output for verification:

Well, at least we got the same results. Let us look at the Russian Multiplication in Python:


import sys

def main(argv):

if len(argv) != 2:
sys.exit('Usage: russian_multi.py <a> <b>')

a = int(sys.argv[1])
b = int(sys.argv[2])

sum = 0;

if a == 0 or b == 0:
print 0;
exit();

if b%2 == 1:
sum += a;

while b != 1:
a = a*2;
b = b/2;
if b%2 == 1:
sum += a;

print "The result of " + str(a) + " times " + str(b) + " is: " + str(sum)

if __name__ == "__main__":
main(sys.argv[1:])

The output:

Again, good thing we got the same results. Now we know we have all three versions of multiplication and they are all computing products of 2 numbers correctly. Now let us look at their time compression. I have organized the data in a table for convince:

	Simple	Ten's	Russian
4 x 5	0.013	0.013	0.014
22 x 54	0.014	0.014	0.014
5142 x 9810	0.014	0.014	0.014
716234 x 847263	0.040	0.014	0.014
817263548 x 827461930	NaN	0.014	0.014

So what can we see? Well first of all the data gathered is from the linux time command. When execute any program in a Linux shell, you can add the command time before the program. This will return you with an output similar to the one below after the command is complete. the times shown are subjective to your computer specifications and current status (i.e. running programs). Here is an example of a Linux time output:

So what does all this mean? The real time is total execution time. The user time is how long it took the user to key in the input. The sys time is the time your command was running on the cpu. In the table above, the time was taken from the sys value of execution of each command. You will notice that simple multiplication gets more cpu consuming as the length of the input increases, while the time for Ten’s and Russian Multiplication remained constant. This means that either algorithm could work as a substitute to multiplication if you happen to work in an environment that does not support multiplication natively. As a final note let me add that even a basic multiplication in Python operates within the same time as Ten’s and Russian multiplication, if not a second faster.

06/7/13

How To Do Math

How math is done

06/6/13

The Game of Hangman in Python

Computer games and python are like a perfect match, it just works. Python is simple enough and powerful to provide game designer and programers a common ground for them to meet up and create awesome stuff. In fact, Python has the PyGame library that is dedicated to creating games. There are many games for Python, buy I thought it would be beneficial to start off with a simple version of Hangman. As before, we will be using Python 2.7 for our examples.

Before we take off with it, let us agree to the rules of the game:

The computer will randomly chose a secret word.
For each user guess, all occurrences of the same letter in the word will be revealed to the player.
The computer will draw the “hangman digram” as outlined bellow for each turn.
The user may guess letters at each turn until the word is completed or the “hangman digram” is complete.
We can assume that all user input and word letters are lowercase alpha numeric without errors.

The last one is made to simplify the code and the constrains for the problem. In reality we should always account for errors, but I am going to et this one slide. For now. Let us first look and the “hangman digram”. Some people think this is the hardest thing, but it is actually the easiest. Here are the 7 possibilities of the board in ASCII art form.

  +---+
  |   |
      |
      |
      |
      |
=========

  +---+
  |   |
  0   |
  |   |
      |
      |
=========

  +---+
  |   |
  0   |
 /|   |
      |
      |
=========

  +---+
  |   |
  0   |
 /|\  |
      |
      |
=========

  +---+
  |   |
  0   |
 /|\  |
 /    |
      |
=========

  +---+
  |   |
  0   |
 /|\  |
 / \  |
      |
=========

This was generated by this short Python code:


board = [
'  +---+   \n  |   |   \n      |   \n      |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n      |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n  |   |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n /|   |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n /|\\  |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n /|\\  |   \n /    |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n /|\\  |   \n / \\  |   \n      |   \n========= \n'
]

for i in range(len(borad)):
	print board[i]

This will take care of any of the board configurations. All we need to worry about is how many letters the user has got wrong and we can immediately print out the corresponding “hangman diagram”. Let us make it a little more nice and wrap it in a class. Classes are objects in Python, very similar to Objects in Java. We can encapsulate the board configuration, word to be guessed, missed letters and guessed letters in 1 object. Lets take a look:


board = [
'  +---+   \n  |   |   \n      |   \n      |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n      |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n  |   |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n /|   |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n /|\\  |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n /|\\  |   \n /    |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n /|\\  |   \n / \\  |   \n      |   \n========= \n'
]

class Hangman:
	def __init__(self,word):
		self.word = word
		self.missed_letters = []
		self.guessed_letters = []

Sweet. Let us move on and create a print function. Print functions are useful for debugging and will take care of our user interface. When we want to print our Hangman object, we really want to know all the information, how the board looks like (or how much of the diagram is complete), the letter we missed, the blank splits for the words and letters we already found. Let us take a look:


def print_game_status(self):
		print board[len(self.missed_letters)]
		print 'Word: ' + self.hide_word()
		print 'Letters Missed: ',
		for letter in self.missed_letters:
			print letter,
		print
		print 'Letters Guessed: ',
		for letter in self.guessed_letters:
			print letter,
		print

And the output for an empty board:

Upon close inspection, you will notice that there is another method I am calling name hide_word(). By the concatenation with the string before, you can assume the function is defined and returns a string. What we really need, is a function that can take a word and print out only the letters the user has already guessed. Let’s take a look:


def hide_word(self):
		rtn = ''
		for letter in self.word:
			if letter not in self.guessed_letters:
				rtn += '_'
			else:
				rtn += letter
		return rtn

That seems good enough. Before we can move on to the game play and logic, we need a method in the Hangman object to update a current guess. That is straight forward and looks like so:


def guess(self,letter):
		if letter in self.word and letter not in self.guessed_letters:
			self.guessed_letters.append(letter)
		elif letter not in self.word and letter not in self.missed_letters:
			self.missed_letters.append(letter)
		else:
			return False
		return True

So if the letter is in the word we are trying to guess and we haven’t tried to guess it before, we are going to mark it and return 1 for successful update or if the letter is not in our word, but has not been asked again. If either of these conditions is a failure, we have a repeat input we have already accounted for and we will return 0 to notify the game handler of a problem. The last method we are really missing is to check for win condition. Here is how we can check for hangman win condition in our case:


def hangman_won(self):
		if '_' not in self.hide_word():
			return True
		return False

Notice that we are reusing methods we already have, making things simple. Now our Hangman game object is complete. You will think that we are over, but there is one more method we are missing for the game to be complete. We have a method to check if the game has been won, but we do not have a method to check if the game is over. What happens when the “hangman digram” is complete? For this we will add just a one liner method:


def hangman_over(self):
		return self.hangman_won() or len(self.missed_letters) == 7

Sweet. Now all we need is a main driver and some helper function and we are all done. Our main method can look like this:


def main():

	game = Hangman(rand_word())
	while not game.hangman_over():
		game.print_game_status()
		user_input = raw_input('\nEnter a letter: ')
		game.guess(user_input)

	game.print_game_status()
	if game.hangman_won():
		print '\nCongratulations! You are the winner of Hangman!'
	else:
		print '\nSorry, you have lost in the game of Hangman...'
		print 'The word was ' + game.word

	print '\nGoodbye!\n'

You will be now notice that we are almost done, just 1 more function and we are clear, the rand_word() function. Now you can get very fancy with this, read from a file and randomly choose and such. However, I want to keep things simple, so I limited the word bank into a small list from which I randomly choose 1 word. Check it out:


def rand_word():

	bank = ['the','living','pearl','.com','captain','deadbones']
	return bank[random.randint(0,len(bank))]

That’s all folks. That is the simple way you can get a game started in python. Now you might think this is very complex. If you are looking for a more simple approach, there is a whole chapter about hangman in python I recommend you check out. The reason we set it up like this is so we can add some GUI events or make it more complex without a lot of hassle. You can download the Python code for Hangman or code it yourself. I hope this gave you some flavor to how games and python could work together. What game can you come up with?

Here are some output screen shots:

06/4/13

The Visual History of Programming Langagues

wpid-History-Of-Programming-Languages-Veracode-2013-06-4-09-11.jpg

06/3/13

Caesar Ciphers in Python

Today I want to talk to you about ciphers, more in particular Caesar Ciphers. Encryption and Decryption of secret messages date back a long time before computers. Countless Nations have utilized ciphers to communicate secrets across distances. For example, lets say I have soldier on the other side of the planet and I am relaying them a message that might put their life at risk. Do we want that message falling into the wrong hands? No. So what can we do? Well, the simple answer is to encrypt the message. Today almost every message is encrypted and packet into protocols several of times. For example, your computer encrypts packets it sends back and forth with your WiFi router all the time. Computers, for better or worse, require us to come up with new encryption methods on a daily basis. However, everyone has to start somewhere. Before you can plunge in and understand things like AES and RSA encryption, we need to start in something basic, like Caesar Ciphers.

Caesar Cipher is pretty simple. It is a substitution cipher that people like to think was user by Julius Caesar. In this cipher we follow a formula to encrypt a message and another to decrypt. Let us take a look at what that means mathematically.

Here is our encryption formula:

And here is decryption:

And thats it folks. Wait, what does this actually mean? Well, lets first start with out assumptions:

The alphabet we are working with contains 26 letters (English)
n is is a number less than or equal to 25.

These assumptions can be modified for any alphabet language of you choosing. If the alphabet contains m letters, than n has to be less than or equal to m-1. As long as you keep both conditions, you will be fine. Here is a general outline and picture of how the algorithm works. You should be aware that normally n is set to 3, but it will work with any number.

Assign numeric values to each letter in the alphabet.
Encrypt:
- for each letter in plain_text
  - new letter is letter_numeric_value + n
Decrypt:
- for each letter in cipher
  - plain_text_letter is letter_numeric_value - n

For it to make some sense, here is a visual picture from Wikipedia:

So the letter E in our message (plain text) is 5 and n=3, so our encrypted value of E is B. Now that we have some background and a simple example, let us implement it in Python. Like always, we will use Python 2.7. Here is how Caesar Cipher looks like in Python:

First lets look at a simple encryption module:


import sys

def main(argv):
	if (len(sys.argv) != 2):
		sys.exit('Usage: sub.py <k>')
		
	plaintext = list(raw_input('Enter message: '))
	alphabet = list('abcdefghijklmnopqrstuvwxyz')
	k = int(sys.argv[1])
	cipher = ''
		
	for c in plaintext:
		if c in alphabet:
			cipher += alphabet[(alphabet.index(c)+k)%(len(alphabet))]
		
	print 'Your encrypted message is: ' + cipher
	

if __name__ == "__main__":
	main(sys.argv[1:])

In this example we define the alphabet and make use of Python List and Indexing. We ask the user to pass in a key of length k and preform the substation. Here is an example run:

Now let us up the stakes to something more complex. After all, this is an encryption that people used to do by hand all the time. Take a look at this program:


import sys 

def encrypt(k):
	plaintext = raw_input('Enter plain text message: ')
	cipher = ''
	
	for each in plaintext:
		c = (ord(each)+k) % 126
		
		if c < 32: 
			c+=31
			
		cipher += chr(c)
		
	print 'Your encrypted message is: ' + cipher

def decrypt(k):
	cipher = raw_input('Enter encrypted message: ')
	plaintext = ''
	
	for each in cipher:
		p = (ord(each)-k) % 126
	
		if p < 32:
			p+=95
						
		plaintext += chr(p)
		
	print 'Your plain text message is: ' + plaintext

def main(argv):
	if (len(sys.argv) != 3):
		sys.exit('Usage: ceaser.py <k> <mode>')
		
	if sys.argv[2] == 'e':
		encrypt(int(sys.argv[1]))
	elif sys.argv[2] == 'd':
		decrypt(int(sys.argv[1]))
	else:
		sys.exit('Error in mode type')


if __name__ == "__main__":
	main(sys.argv[1:])

The first question you might ask is why is the mod 126? Well, this version of Caesar Cipher was adapted to take full use of the ASCII Printable Character map, minus the first 32 characters that are not printable. With this program, we can chose a larger n and create a “harder” to break ciphers. You will also notice that now we can do Encryption and Decryption in the same program. Let us try to decrypt ‘khoor’ and see what we get:

Sweet. Now let’s try to encrypt something a little longer with a different key.

And Decryption:

Caesar ciphers are nice to play around with and to learn basic concepts, but is really impractical. The number of combination you can get is really small compared to what the computer can generate. Brute force attacks can always crack the code with very little human intervention. Consider a 26 letter alphabet. There are only 25 options for selecting a unique n. That means that if I can generate all the 25 permutations, 1 of them has to be the correct plain text. Let us look brute force braking using the following script:


import sys 

def decrypt(k,cipher):
	plaintext = ''
	
	for each in cipher:
		p = (ord(each)-k) % 126
	
		if p < 32:
			p+=95
						
		plaintext += chr(p)
		
	print plaintext

def main(argv):
	if (len(sys.argv) != 1):
		sys.exit('Usage: brute_ceaser.py')
		
	cipher = raw_input('Enter message: ')
		
	for i in range(1,95,1):
		decrypt(i,cipher)

if __name__ == "__main__":
	main(sys.argv[1:])

I will spare you the entire 94 lines that got printed out, here are a few. Can you guess what the message originally was?

Here is another one:

I will let you come to your own conclusions as to how “hard” it is to brake Caesar Ciphers. Personally, I wouldn’t use them for anything simple. Than again, I do not know how many people would check if you used it. I hoped you gain some understanding to how cipher works, substitution ciphers in particular. Next time I might dig a little farther into security algorithms and play around with another step up in encryption-decryption algorithms.

Happy Hacking
Captain DeadBones

05/31/13

Virtual Reality to Change Future Gaming Experience

Video games have been around since the 50’s and are in an ongoing state of ”evolution”. Gaming players and developers are constantly on the lookout to incorporate new technologies into gaming, hardware and software. Today, there are many tools available to enhance user interaction and capture human movement. Yet, most of the systems are expensive, require high maintenance and are somewhat unnatural. Gaming consoles today include a full range of motion capture devices, yet gaming popularity among motion capture games is not as high compared to ”regular” gaming. The question at hand is weather any of the Virtual Reality (VR) systems could be incorporated into gaming in the near or far future and weather such act will revolutionize gaming to another level.

In order to address this question appropriately let us divide gaming into 3 sub-categories: video games, simulation and specialize devices. We can consider video games as the mass end-user, home, gamers. These are the games that do not primely intend to simulate a real environment (although they may) but to entrain and amuse the user(s). Let us name simulation to such games (although they might be in the first category as well) that primarily intend to simulate an environment without too much external devices. This might include some motion capture device, but mostly the affordable and low-end commercial ones. The third category are the large, cave like, simulators that intend to be inline with Ivan Sutherland’s Ultimate Display. If you have not read that little short article, I highly suggest you do it now. This is the category that in my mind will not become home ”friendly” and will mostly remain as specific devices that are built for specific uses. Such uses include therapy, military training, etc.

In the category of video games, I do not see any VR system that can really revolutionize gaming experience anytime in the near future. In terms of hardware there might be small improvements, curved displays, better controllers (if possible), 3D technology and other similar hardware will come to the market very soon and will reduce to reasonable price at some point. However, system such as the data glove, Oculus rift, motion trackers and similar motion capture and output devices. They all have been around, some for a while, and yet none has taken off in a direction of being mass produced or gaming related. Although some home improved recently and cost has gone done significantly, they have yet to emerge as a new gaming experience. In addition, they require high maintenance and would fail in ”real world” living room gaming experience. I do not think any gamer would spend an hour prior to gaming calibrating a system or/and getting into full body gear. More so if after an hour of calibration the wires get tangled or the batteries need to be recharged.

Skipping to the last category I think specialize VR systems have improved tremendously over the past years and will continue to do so. With the increase use of simulation in the military and therapy environment, cave like rooms, or spheres will get more accurate and truly will come close to The Ultimate Display. The reason this large scale devices will ”grow” is because in the long run they save money and life. For military use, the ability to virtualize war like scenario will yield better soldiers and better prepare them for real world scenario. In therapy full room simulation might help in ways we simply can not today. Farther more, full room simulations have endless uses in many more fields that I wish to consider for this paper.

Simulation, to my opinion, will benefit and advance the most in the near and far future. This includes hardware such as the Wii Remote, Microsoft Kinect and the PlayStation Move. I think more and more games will come to utilize the hardware. However the greatest advancement in my mind will come from mobile gaming and augment reality. The growing gaming community at the moment is the mobile devices, namely mobile smart phones and tablets. Furthermore, there is a great niche that augment reality can fill. Bringing games outside of the virtual space and interacting with real life objects will revolutionize gaming. Using generic object, such as a box, table, wall and etc. Using augment reality can enhance an environment to a new frontier. This will require light and cheap HMD with hours of battery life time. ”Smart glasses” if it may, will be the next leap in computation and gaming. That will be a point in which we meet the Virtual and Reality, somewhere in the middle.

Now one knows what the future will truly bring. Microsoft and Sony have just lunched their new top of the line systems, but are they really that much different? Have we seen anything “new”? Sadly, no. We are looking at improvements on well built past. The future of gaming might be close, but it is not really here. At least not for me. What do you think? Is the future already here?

05/29/13

Wi-Fi Security Breaches: Escape the Void

Google was fined €145,000 ($189,000) by German officials on April 22 because it violated German citizens’ privacy rights while developing the Street View mapping service. Google illegally acquired personal information from public and private Wi-Fi networks, including emails, photographs and other unencrypted data, according to the New York Times. The data was collected by Google’s Street View automobiles, which have digitized about five million miles of roadways in 49 countries.

According to BBC News, Germany’s data chief claimed Google’s actions as “one of the biggest known data protection violations in history.” It was also noted that the miniscule penalty would not dissuade future abuses. The maximum penalty currently allowed by law is €150,000. Google made $10.7 billion in net profit last year, over 50,000 times the amount of the penalty, stated by The Times of India.

Program Errors or Negligence?

Google claims the privacy violations are nothing more than program errors. However, numerous other countries have filed suits as a result of the company’s negligence. Peter Fleischer, Google's global privacy counsel, told the New York Times that the company does its best to respect privacy rights and does not deliberately farm private data.

DailyTech revealed that Google settled privacy litigation with 38 U.S. states in March for $7 million. The company was also ordered to establish an internal privacy program, run educational advertisements in major newspapers of the effected states, and explain to users how to encrypt their data while using Wi-Fi via a YouTube video.

These developments shed light on just how easily individuals and corporations can gain access to private information through wireless networks. There are several precautions that can maximize your security while using Wi-Fi. Specific services, such as LifeLock Identity Protection, can not only aid in preventing security breaches, it will save you the time and hassle of calling your credit card companies to cancel accounts.

At Home

Almost all wireless routers have security technology known as Wi-Fi Protected Access Version Two (WPA2). It encrypts information as it travels from point A to point B. Always make sure this feature is on and make certain the router access password is at least eight letters long, includes both lower and upper case letters, numerals and at least one punctuation mark.

On the Go

Smartphones far outsell PCs, which means hotspots are utilized more than ever. It's best to connect only to those that require a password to maximize privacy and security. You can also use a VPN (Virtual Private Network), which encrypts all data sent or received by your device. VPN services are relatively inexpensive, and can be installed on most smartphones. By using a VPN, you can use those free Wi-Fi hotspots without worrying about hackers or corporations “accidentally” scooping up your personal information.

05/28/13

Computing Pi with Python

Pi is a truly magical number that has a lot of people following it. I am not quite sure what is so fascinating with an irrational number that keeps repeating forever. From my point of view, I am interested in computing Pi, that is computing the value of Pi. Since Pi is an irrational number, it goes on forever. This means that any computation of Pi is just an approximation. If you compute 100 digits, I can compute 101 digits and be more accurate. Some people have set aside super computers to try to compute the most accurate Pi to date. Some extremes include Calculating 5 Trillion Digits of Pi. You can even find online a txt file containing 1 billion digits of Pi (Be warned, it will take a while to download the file and you can not open it with your regular notepad application). For me, it is interesting how you can compute Pi with a few simple line of Python.

wpid-200px-Innovation_and_Technology_Commission.svg-2013-05-28-12-54.png

You could always use the math.pi variable. It is included in the standard library and it should be used before you try to calculate it. In fact, we are going to use it to calculate our accuracy. To get started, let us take a look at a very straight forward approach of computing Pi. As usual, I will be using Python 2.7, same ideas might apply for different version. Most of the algorithms that we are going to use are direct implementations from the Pi WikiPedia page. Let us look at the following code:


import sys
import math

def main(argv):

	if len(argv) != 1:
		sys.exit('Usage: calc_pi.py <n>')

	print '\nComputing Pi v.01\n'
	
	a = 1.0
	b = 1.0/math.sqrt(2)
	t = 1.0/4.0
	p = 1.0
		
	for i in range(int(sys.argv[1])):
		at = (a+b)/2
		bt = math.sqrt(a*b)
		tt = t - p*(a-at)**2
		pt = 2*p
		
		a = at;b = bt;t = tt;p = pt
		
	my_pi = (a+b)**2/(4*t)
	accuracy = 100*(math.pi-my_pi)/my_pi
		
	print "Pi is approximately: " + str(my_pi)
	print "Accuracy with math.pi: " + str(accuracy)
	
if __name__ == "__main__":
	main(sys.argv[1:])

This is a very simple script, you can download, run, modify and share it as you like. You may see an output similler to the one bellow:

You will notice that one n is larger than 4 our approximated Pi and accuracy do not change anymore. We can only assume that the same will apply for larger values of n. So what are we to do? Lucky, there is more than one way to crack this egg. Using the Python Decimal Library we can compute Pi to a very high degree of accuracy. Let us see how the library works. The simple version is that it gives you a decimal number with more than 11 digits the normal Python float will give you. Here is an example of the Python Decimal Library:

Look at all those digits. Wait! We only entered 3.14, why are we getting all that junk? That is memory junk. In a nut shell, Python gave you the decimal number you wanted, plus a little extra. It won’t effect any calculation as long as the precision is less than when the junk numbers begin. You can specify how many digits you want exactly by setting the getcontext().prec to the number of digits you want. Let us try it out.

wpid-python_decimal_example_6_digits-2013-05-28-12-54.png

Sweet. Now let us try to use this to see if we can get a better approximation with our previous code. Now I normally am against using from library import *, but in this case it will make the code look nicer.


import sys
import math
from decimal import *

def main(argv):

	if len(argv) != 1:
		sys.exit('Usage: calc_pi.py <n>')

	print '\nComputing Pi v.01\n'
	
	a = Decimal(1.0)
	b = Decimal(1.0/math.sqrt(2))
	t = Decimal(1.0)/Decimal(4.0)
	p = Decimal(1.0)
		
	for i in range(int(sys.argv[1])):
		at = Decimal((a+b)/2)
		bt = Decimal(math.sqrt(a*b))
		tt = Decimal(t - p*(a-at)**2)
		pt = Decimal(2*p)
		
		a = at;b = bt;t = tt;p = pt
		
	my_pi = (a+b)**2/(4*t)
	accuracy = 100*(Decimal(math.pi)-my_pi)/my_pi
		
	print "Pi is approximately: " + str(my_pi)
	print "Accuracy with math.pi: " + str(accuracy)
	
if __name__ == "__main__":
	main(sys.argv[1:])

And the output:

Ok. We are more accurate, but it seems like there is some rounding off. We got the same accuracy from n=100 and from n=1,000. So now what? Well, now we come to ask for help from formulas. The way we calculated Pi until now is by summation of the parts. I found some code online from DAN on his article about Calculating Pi. He suggests we use the following 3 formulas:

Let us start with the Bailey–Borwein–Plouffe formula. It looks like this:

In code we can write it like this:


import sys
import math
from decimal import *

def bbp(n):
    pi = Decimal(0)
    k = 0
    while k &lt; n:
        pi += (Decimal(1)/(16**k))*((Decimal(4)/(8*k+1))-(Decimal(2)/(8*k+4))-(Decimal(1)/(8*k+5))-(Decimal(1)/(8*k+6)))
        k += 1
    return pi

def main(argv):

        if len(argv) != 2:
		sys.exit('Usage: BaileyBorweinPlouffe.py <prec> <n>')
		
	getcontext().prec = (int(sys.argv[1]))
	my_pi = bbp(int(sys.argv[2]))
	accuracy = 100*(Decimal(math.pi)-my_pi)/my_pi

	print "Pi is approximately " + str(my_pi)
	print "Accuracy with math.pi: " + str(accuracy)
    
if __name__ == "__main__":
	main(sys.argv[1:])

Set aside the “wrapping” code around it, the bbp(n) function is really what you want. The larger n you give it and the larger you set getcontext().prec the more accurate your calculation will be. Let us take a look at some exaction of the code:

That is plenty of digits. As you can tell, we are not more accurate than we were before. So we need to move on to our next formula, hoping to get a better accuracy, the Bellard’s formula. It looks like this:

wpid-dbf2d4355c108f6b3388985be4976799-2013-05-28-12-54.png

We are going to only change our commutation formula, the rest of the code will remain the same. If you want you can download Bellard's formula in python. Let us take a look at bellards(n):


def bellard(n):
    pi = Decimal(0)
    k = 0
    while k &lt; n:
        pi += (Decimal(-1)**k/(1024**k))*( Decimal(256)/(10*k+1) + Decimal(1)/(10*k+9) - Decimal(64)/(10*k+3) - Decimal(32)/(4*k+1) - Decimal(4)/(10*k+5) - Decimal(4)/(10*k+7) -Decimal(1)/(4*k+3))
        k += 1
    pi = pi * 1/(2**6)
    return pi

The output:

Not , we get the same accuracy. Well, let us try the third formula, Chudnovsky algorithm, that looks like this:

wpid-826dc7788dba249ee86fc0135e06b035-2013-05-28-12-54.png

Again, let us only look at the computation formula (assume we have a factorial formula). If you want you can download Chudnovsky formula in python.

Here is the code and output:


def chudnovsky(n):
    pi = Decimal(0)
    k = 0
    while k &lt; n:
        pi += (Decimal(-1)**k)*(Decimal(factorial(6*k))/((factorial(k)**3)*(factorial(3*k)))* (13591409+545140134*k)/(640320**(3*k)))
        k += 1
    pi = pi * Decimal(10005).sqrt()/4270934400
    pi = pi**(-1)
    return pi

So what is our conclusion? Fancy algorithms do not live up to the expectations in machine float worlds. I was really looking forward to a better accuracy than what we got when we used the summation formula. I guess that is too much to ask for. If you really need Pi, just use the math.pi variable. However, for fun and to test out how fast you computer really is, you can always try to calculate the first million digits of Pi, or maybe more...

05/23/13

Why Switching to RackSpace Mail is Worth the $2

Some of my clients live in the dark age of fighting off email storage limits. To me this is a thing of the past. We are in the year of 2013, I can buy a 1 TB hard drive for $60 off of Amazon, having a 1GB email limit sounds absurd to me. Yet, there are many provides that take advantage of consumers who do not know any better. Begin a well informed consumer is always a benefit. I strongly advise anyone to do their own research and not relay on my words and/or opinions. Just for a quick compression, Google Gmail will give you 10+ GB for free. However, using Gmail is not always a good solution when you are a legitimate business and must maintain a professional approach. Seriously, put yourself in the shoes of your clients. If you were communicating with a sales person and got a proposal from the following 2 addresses, which are you more likely to not consider junk?

someplace@gmail.com or mike@someplace.com

It is obvious that the ladder is a better selection. You most likely already have a website for your company, if not, you should. So you have the domain name and regular email from your own hosting provide. For example, HostGator will say that you have unlimited storage. In reality, at 1 GB emails sent to your mailbox will bounce back to the sender. You could delete old email, but what if you want to keep some for archiving, marketing or even legal future usage? The answer is that you need more storage. In part, that is one of the reason I suggest to my customers to move to RackSpace for their email provider. You can still keep your domain name and hosting at different locations and just have your email service through RackSpace Email.

wpid-Rackspace_Cloud_Company_Logo_clr_300x109-2013-05-23-16-43.jpg

RackSpace offers 2 different packages, they offer regular email mailboxes for $2 per month per mailbox and for $10 they offer full exchange. This leads me to some “hidden benefits” RackSpace has. Quite often people like to use Microsoft Exchange as a way to scare people into buying equipment that can sum up to $10K and more. The truth is that if all you need is the following times, most likely RackSpace email will do the trick for you.

25GB Mailbox
Contacts
Calendar
Tasks
Notes

The system will allow you to share contacts and calendar appointments as well as keep personal ones. In a nut shell, it will give you all the power of exchange without you having to worry or pay an arm and a leg. Now, Microsoft Exchange does have some more advance features. If you really need it, you could go with that option, for $10 you can have it all. If you want you can even take the system out for a RackSpace Email Test Drive. Here are some screen shoots of their system taken directly oof of RackSpace website:

I hope I at least got you thinking about your email service. Yes, you can get away with free email, but you usually get what you pay for. For my client RackSpace might work. For others it may not. We live in a “Zero Time Communication Age”. Internal and external digital communication has to be fast and reliable in order to succeeded. I feel confidante that the migration for my client will work well and that I will be able to share their experiences in the near future. If I have not convinced you yet, I suggest you start a chat with one of the RackSpace support or sale staff. They are always their to answer question and are very knowledgeable.

05/13/13

Never Give Up On Your Dreams

young dreams may never die

Captain DeadBones Chronicles

The art of coding, one line at a time…