Function in python are First- Class Objects. This means that they can be passed around and used just like any other data types. In Shorthand it's also known as "First-class function"

What is First Class Object Objects ?

- Created at runtime
- assigned to a variable or element in a data structure
- passed as an arguments to a function
- returned as the result of a function

Integers, Strings and dictionaries are other examples of first- class objects in Python.

Treating a function like an Object

Created at runtime

```
>>> def factorial(n):
... """return n!"""
... return 1 if n < 2 else n * factorial(n - 1)
...
>>> factorial(5)
120
>>> factorial.__doc__
'return n!'
>>> type(factorial)
<class 'function'>
>>>
```

In The above example we created a function at the runtime,

`__doc__`

is one of several attribute of the function objects, and factorial is an instance of function classassigned to a variable or element in a data structure

```
>>> fact = factorial
>>> fact
<function factorial at 0x7fdfb7f7fbf8>
>>> fact(4)
24
>>>
```

We can assign it a variable fact and call it through that name

passed as an arguments to a function

```
>>> map(factorial, range(5))
<map object at 0x7fdfb7e93390>
>>>
```

We can also pass factorial as an argument to function In the above example we passed it to the map and italso returns a function as result, Which produces a below result when passed to list

returned as the result of a function

```
>>> list(map(factorial, range(5)))
[1, 1, 2, 6, 24]
>>>
```

Another example is the

`sorted`

built-in function: an optional key arguments lets you provide a function to be applied to each item for sorting.```
>>> name = ['Ankur', 'Anand', 'Sam', 'John', 'KK', 'I']
>>> sorted(name, key=len)
['I', 'KK', 'Sam', 'John', 'Ankur', 'Anand']
```

Custom Reverse Function used for Sorting.

```
>>> def reverse_sort(word):
... ''' reverse the word '''
... return word[::-1]
...
>>> reverse_sort('Ankur')
'ruknA'
>>> sorted(name, key=reverse_sort)
['I', 'KK', 'Anand', 'Sam', 'John', 'Ankur']
>>>
```

## Understanding First Class Function in python

Recursive Approach:

```
def calculate_factorial_recursive(number):
'''
This function takes one agruments and
returns the factorials of that number
This is naive recursive approach
'''
#base case
if number == 1 or number == 0:
return 1
return number * calculate_factorial_recursive(number - 1)
```

The Recursive approach is not the best approach. It will give

`RuntimeError: maximum recursion depth exceeded`

. for large number as python doesn't have optimized tail recursion
But it have been written for pedagogical purposes, to illustrate the effect of several fundamental algorithmic optimizations in the n factorial of a very large number.

First Improvement : Successive Multiplicative Approach This function uses the approach successive multiplication like 8! = 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

```
def calculate_factorial_multi(number):
if number == 1 or number == 0:
return 1
result = 1 # variable to hold the result
for x in xrange(1, number + 1, 1):
result *= x
return result
```

*The profiled result for this function :*

For n = 1000 -- Total time: 0.001115 s

for n = 10000 -- Total time: 0.035327 s

for n = 100000 -- Total time: 3.77454 s.

Now If we see the result from line_profiler we will see that most %time was spent in multiplication step of the above code i.e

`result *= x`

which is almost 98%.
Second Improvement : Reduce the number of successive multiplication As the multiplication is very costly especially for a large number , we can use the pattern and reduces the number of multiplication by half. Lets group the above 8! example 8! = 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 - together:

`8! = (8 * 1) * (7 * 2) * (6 * 3) * (5 * 4)`

which can be written as `8! = 8 * (8 + 6 = 14) * (14 + 4 = 18) * (18 + 2)`

.*so first factor is the number we are taking. second factor is the first factor plus first factor minus two from the factor and then in next we multiply the result with added result. Odd number also follows the same pattern till even just handle the case of one odd*.

Code to do the same:

Python :

```
def calculate_factorial_multi_half(number):
if number == 1 or number == 0:
return 1
handle_odd = False
upto_number = number
if number & 1 == 1:
upto_number -= 1
print upto_number
handle_odd = True
next_sum = upto_number
next_multi = upto_number
factorial = 1
while next_sum >= 2:
factorial *= next_multi
next_sum -= 2
next_multi += next_sum
if handle_odd:
factorial *= number
return factorial
```

*The profiled result for this function :*

For n = 1000 -- Total time: 0.00115 s

for n = 10000 -- Total time: 0.023636 s

for n = 100000 -- Total time: 3.65019 s

It is not optimised very much, but are at least not obscenely slow. It's shows some improvement in the mid range but didn't improved much with scaling. In this function too most of the %time is spent on multiplication:

Java Code for the same:

```
private static void calculateFactorial(int uptoValue) {
BigInteger answer=BigInteger.ONE;
boolean oddUptoValue=((uptoValue&1)==1);
int tempUptoValue=uptoValue;
if(oddUptoValue){
tempUptoValue=uptoValue-1;
}
int nextSum = tempUptoValue;
int nextMulti = tempUptoValue;
while (nextSum >= 2){
answer=answer.multiply(BigInteger.valueOf(nextMulti));
nextSum -= 2;
nextMulti += nextSum;
// long product=(tempUptoValue-i+1L)*i;
}
if(oddUptoValue){
answer=answer.multiply(BigInteger.valueOf(uptoValue));
}
System.out.println(answer);
}
```

Further Improvement : Using prime decomposition to reduce the total number of multiplication Since there are (number / ln number) prime number smaller than number so we can further reduce the total number of multiplication

```
def calculate_factorial_prime_decompose(number):
prime = [True]*(number + 1)
result = 1
for i in xrange (2, number+1):
if prime[i]:
#update prime table
j = i+i
while j <= number:
prime[j] = False
j += i
sum = 0
t = i
while t <= number:
sum += number/t
t *= i
result *= i**sum
return result
```

*The profiled result for this function :*

n = 1000 -- Total time = 0.007484 s

n = 10000 -- Total time = 0.061662 s

n = 100000 -- Total time = 2.45769 s

You can see the detailed profiled result of all the discussed algorithms prepared here, in case if you want to see.

## Efficient Factorials Algorithms !

While i was learning the Shell Scripting an Interesting thing Happened.

and tried to execute it on Cygwin Environment on windows (For those who don't know what is Cygwin Search Google of Visit https://www.

I wrote the following shell script on windows platform using sublime test editor

```
#!/bin/bash
a=20
b=10
sum=`expr $a + $b`
echo $sum
```

and tried to execute it on Cygwin Environment on windows (For those who don't know what is Cygwin Search Google of Visit https://www.

**cygwin**.com/ ) .. i got an error

'20\r': command not found

now there was no error in the script i was wondering what went wrong then i realized after seeing the error that instead of a=20 the expr is taking a as '20/r' . so after little bit of help with google i came to know in windows environment Line ends with CRLF(/r/n Carriage return and Line Feed) while in Unix it ends with LF (Line Feed Only).

So variable a ended with '20/r/n' in windows editor (so was variable b); while for Unix anything before '/n' was assumed as variable.

After writing the same code on Vi editor everything was fine and running!

## Difference between Windows based Editor and Unix based Editor !

This Title is a property of The Side I Hide .. This Illustration is created for display purpose only not for commercial use by anyone other than blog owner..

GET IN TOUCH FOR LOGO DESIGN.

## HEADER DESIGN 8 !

This Title is a property of Midnight Scribbles .. This Illustration is created for display purpose only not for commercial use by anyone other than blog owner..

GET IN TOUCH FOR LOGO DESIGN.

## HEADER DESIGN 7 !

This Title is a property of The Little Princess ! .. This Illustration is created for display purpose only not for commercial use by anyone other than blog owner..

GET IN TOUCH FOR LOGO DESIGN.

## HEADER DESIGN 6 !

This "Header" and the Title is a property of Desitionary .. This Illustration is created for display purpose only not for commercial use .

GET IN TOUCH FOR LOGO DESIGN.

GET IN TOUCH FOR LOGO DESIGN.

## Header Design 5 !

This " It’s all about creating magic in words! " Tagline is a property of http://www.sarusinghal.com/ .. This Illustration is created for display purpose only not for commercial use .

Vector File Available in .AI, .SVG along with readymade PNG and JPEG format image for instant use . IF you want then get in touch. * File will not include the Tagline

GET IN TOUCH FOR LOGO DESIGN.

## Header Design 3 !

This " A Rat's Nibble" Title is a property of http://ratnibbles.blogspot.in/ .. This Illustration is created for display purpose only not for commercial use .

GET IN TOUCH FOR LOGO DESIGN.

## Header Design 2 !

Subscribe to:
Posts
(
Atom
)