Saturday, October 5, 2013

Chop-down algorithm

Day today programming we need to find solutions for various logical problems. today i got a task to create a program to find triangular numbers between any given two numbers. I implemented it using python. Following code shows how i did it.

   
import math,sys

#create a list with numbers
def create_list():
    num_list=[]
    for num in range(int(input("insert start point: ")),int(input("Insert end point: "))):
        num_list.append(num)
    return num_list

#function to find triangular numbers
def get_triangles(numlist):
    triangles = []
    for i in numlist:
        if (check_triangle(i)):
            triangles.append(i)
    return triangles

#function to check number is triangular or not
def check_triangle(n):
    return math.sqrt((8*n)+1).is_integer()

#fuction main to run the process
def main():
    numlist = create_list()
    print(get_triangles(numlist))
Even though it seems like the task is completed it was not. I tried it with the range of  0 - 100000000(1*10^8) numbers . it was horrible to see the out put and time taken to complete the task. my computer was stuck for few minutes and  unable to complete the task. i was tried with 10000000 (1*10^7). then i saw that 95% of memory  was occupied by the program. Then i modified the program as follow
   
import sys,_thread,time,math

#function to create a  list with numbers
def create_list():
    num_list=[]
    for num in range(int(input("insert start point: ")),int(input("Insert end point: "))):
        num_list.append(num)
    return num_list
   

#determine 3 cutdownpoints
def cut_down_points(count):
    if(count%4==0):
        return [count*0.25,count*0.5,count*0.75]
    else:
        while(count%4!=0):
            count = count+1
            first = int(count*0.25)
            second = int(count*0.5)
            third = int(count*0.75)
        return [first,second,third]

#cutdown list to 4 peces
def cutdown(num_list,cut_points):
    return [num_list[0:cut_points[0]],num_list[cut_points[0]:cut_points[1]],
            num_list[cut_points[1]:cut_points[2]],num_list[cut_points[2]:]]

#function to find triangular numbers
def find_triangle_numbers(numlists):
    triangles=[]
    for i in numlists:
        if(check_triangle(i)):
            triangles.append(i)
    print (triangles)
    #return triangles
            
#function to check number is triangle or not
#if number x is a triangle 8x+1 need to be a perfect squre number 
def check_triangle(n):
    return math.sqrt((8*n)+1).is_integer()

#start 4 threads to find triangles
def find_all_triangles(numberlist):
    #print (numberlist)
    num_set_01= _thread.start_new_thread(find_triangle_numbers,(numberlist[0],))
    num_set_02= _thread.start_new_thread(find_triangle_numbers,(numberlist[1],))
    num_set_03= _thread.start_new_thread(find_triangle_numbers,(numberlist[2],))
    num_set_04= _thread.start_new_thread(find_triangle_numbers,(numberlist[3],))

#main function to run the process 
def main():
    numbers = create_list()
    temp_cutdown_point_list = cut_down_points(int(len(numbers)))
    cutdown_point_list=[int(i) for i in temp_cutdown_point_list]
    cut_list = cutdown(numbers,cutdown_point_list)
    find_all_triangles(cut_list)
I sow that the program was not stuck as previous and did the task smoothly with a minimum execution time. After careful consideration i defined following algorithm to accomplish this kind of tasks.

NAME : Chop-down algorithm 
TASK : increase the efficiency of searching tasks  in vary large domains
ALGORITHM :
assume Domain size is equal to M where M > 10e6
Start
   chop down the domain in to n parts where n <= M/[(M*5)/100]
   create n number of  individual threads (avoid resource killing)
   assign single sub domain to each thread
   perform searching
End



Eg:  assume that we need to find triangular numbers between 0 and 10e6
             STEP 01 :
             n = 10e6/[(10e6 * 5)/100] =  20
             so we need to break the domain in to 20 parts
             STEP 02 :
             create 20 threads
             STEP 03 :
             assign single sub domain to each thread
                               Thread_01 >>>> 0  -  5*10e4
                                Thread_02>>>> 5*10e4  -  10*10e4
                                 .
                                 .
                                 .

             STEP 04 :
             Start threads to perform search
                               EG.  Thread_03 ->
                                             Search each value in its domain and print triangular values
             End


                         
                             










Friday, October 4, 2013

Algorithm to find GCD (Greatest common divisor )

What is GCD ?
 The largest integer that divides a set of numbers

Eg . GCD for 15 and 10 is 5

To find this prophetically Eucilds algorithm can be used. it is very much easy and fast way to find GCD within the programs.

Algorithm :
assume "a" and "b" are the numbers we need to find GCD

A=a and B=b
while B>0 do
         R= A mod B
         A = B
         B = R
return A

Following python code shows how it can be used in a python program  
#Find GCD with Eucilds Algorithm
def FindGCD_Eucilds(num_one,num_two):
    A=num_one
    B=num_two
    while (B>0):
        R=A%B
        A=B
        B=R
    return A

print(FindGCD_Eucilds(15,5))

Wednesday, October 2, 2013

Useful Python regular expressions

Regular expressions:

In general we are using expressions to represent common format of a mathematical domain. The term "Regular expression" also engage with a job exactly similar to that. We can see regular standard patterns of strings such as email addresses, phone numbers, ID numbers etc. When we talking about software developing some times we may need to use this formats in order to verify the corresponding insertions of users. That is the place where "Regular expression" plays it's role. we can define a pattern for the day today string patterns in order to verify them.

Regular expression designing is some kind of a art which has a challenge. Following patterns are designed by my self in order to use in python programs.
           

import re

#regular expression to find email addresses ie. sandaru.weerasooriya@gmailcom
regmail = r'(?:[a-z]|[A-Z])+(?:[.]?)(?:[a-z]|[A-Z])+[@][a-z]+[.][a-z]+(?:[^ *])'
founded_mails=re.findall(regmail,"Sandaru.wEerasooriya@gmail.com amalka@gmail.com")
print (founded_mails)
 
#regular expression to identify phonenumbers ie.international and local mobile number formats
regnum = r'[/+]?[0-9][0-9][0-9][-]?[0-9][0-9][0-9][-]?[0-9][0-9][0-9][0-9][0-9]?'
founded_numbers = re.findall(regnum,"071-4969763 077-496-9763 +94714969763 0714969763 0717896678")
print(founded_numbers)

#regular expression to identify only mobitel numbers
regMobitel = r'(?:(?:[/+][9][4][7][1])|(?:[0][7][1][-]?[1-9][1-9]))(?:[0-9][-]?[0-9][0-9][0-9][0-9][0-9]?)'
founded_mobitels = re.findall(regMobitel,"071-4969763 077-496-9763 +94714969763 0714969763")
print(founded_mobitels)

#regular expression to identify only dialog numbers
regDialog = r'(?:(?:[/+][9][4][7][7])|(?:[0][7][7][-]?[1-9][1-9]))(?:[0-9][-]?[0-9][0-9][0-9][0-9][0-9]?)'
founded_dialog = re.findall(regDialog,"071-4969763 077-496-9763 +94714969763 0714969763")
print(founded_dialog)