Comp5

• Journey through the required programming.
• Many times, we will use short programming contractions so as to demonstrate some of the syntactical possibilities.

In [ ]:

%%writefile factorial.c
/* Factorial without using recursive function
* Factorial of a number n is defined as n!=n(n-1)(n-2)...3.2.1
* Exp 5!=5x4x3x2x1=120
* Special: 1!=0!=1
*/
#include<stdio.h>
int fact(int r);
int main()
{
    int num;
    printf("Enter the number : ");
    scanf("%d",&num);
    printf("\nOUTPUT: %d! = %d.",num,fact(num));
}

int fact(int r)
{
    int term=1;
    for(int i=1;i<=r;term=term*i++);
    return(term);
}

Overwriting factorial.c

In [ ]:

!gcc factorial.c
!./a.out

Enter the number : 5

OUTPUT: 5! = 120.

Series¶

Repetition is a fundamental necessity in programming, and it is primarily achieved using loops. Loops allow a block of code to be executed multiple times, either for a specific number of iterations or until a certain condition is met, such as reaching a desired level of accuracy in a calculation.

To optimize code in a loop, the primary focus is on minimizing the work done inside the loop body, as operations within a loop are executed repeatedly.

• Move loop-invariant codes that yield same result in every iteration should be mmoved to before the loop starts.
• Employ strength reduction to replace expensive operations with cheaper ones. Powers functions,Division, modulo, multiplication are computationally intensive. This is done by using efficient data srtucture and algorithm. Exps: Replacement of dividing by 2 by multiplying by 0.5, or bit-shift operations, avoiding squares or cube powers by multiplications, precalculate constants etc.
• Avoid unnecessary function calls, small functions statements can be written in the loop itself.
• Use Local Variables: Accessing local variables is typically faster than accessing global variables or object attributes due to quicker lookup times. Use of contiguous memory makes the access faster.
• Loop Unrolling: This involves expanding the loop body to perform multiple iterations in a single pass, which reduces the overhead of loop control instructions (like incrementing the counter and checking the condition) and branching.

All these can be achieved by practice, critical observations and applying the ideas of Computing time and Memory access.

$\sum_i = T_1 + T_2 + \ldots$:

sum =0;
loop { sum=sum+T_i};
print sum;

Sometimes, sum=first term of the summation is used, then loop starts from second term.

$\prod_i = T_1 × T_2 × \ldots$:

prod=1;
loop {prod *= Ti};
print prod;

Let's begin with a simple sum. Though the result can be obtained using Gauss sum formula $sum=s(s+1)/2$, we would see how the result is obtained by doing term by term addition.

In [1]:

%%writefile sum_numbers.c
/* 1 + 2 +3 + ... + n = n(n+1)/2 */
#include<stdio.h>
int main()
{
    int i,n,sum;
    printf("Enter value of n: ");
    scanf("%d",&n);

    sum=0; // sum initialization
    for(i=1;i<=n;i++) {
      sum=sum+i;
    }
    printf("Sum of  first %d Natural numbers =%d",n,sum);

    sum=n*(n+1)/2;
    printf("\nSum of %d Natural numbers by Formula =%d",n, sum);
}

Writing sum_numbers.c

In [2]:

!gcc sum_numbers.c
!./a.out

Enter value of n: 10
Sum of  first 10 Natural numbers =55
Sum of 10 Natural numbers by Formula =55

In [8]:

%%writefile seriessum1.c
/* Sum = 1^2 + 2^2 + 3^2 + .... + n^2 = n(n+1)(2n+1)/6 */
# include <stdio.h>
void main ()
{
  int n, f=1, sum=0;
  printf ("\nEnter the value for n: ");
  scanf("%d", &n);
  for(int i=1;i<=n;i++) sum += i*i;
  printf ("\nSum for %d terms =%d", n,sum);
  sum = n*(n+1)*(2*n+1)/6;
  printf ("\nSum for %d terms by Formula =%d", n,sum);
}

Overwriting seriessum1.c

In [9]:

!gcc seriessum1.c
!./a.out

Enter the value for n: 10

Sum for 10 terms =385
Sum for 10 terms by Formula =385

In [20]:

%%writefile seriessum2.c
/* Sum = 1 + 2 + 2^2 + .... + 2^n = 2^(n+1) - 1 */
# include <stdio.h>
# include <math.h>
void main ()
{
  int n, f, sum;
  printf ("\nEnter the value for n: ");
  scanf("%d", &n);
  // Method 1: Less eficient, uses very costly (for large n) power inside loop.
  sum=0;
  for (int i=0;i<n;i++) sum += pow(2, i);
  printf ("\nSum by power for %d terms =%d", n,sum);
  // Method 2: Each term is obtained by multiplying 2 to previous term!
  sum=0;
  f=1;
  for (int i=1;i<=n;i++) {
    sum += f;
    f *= 2;
  }
  printf ("\nSum for %d terms by method 2 =%d", n,sum);
  sum = pow(2, n) - 1;
  printf ("\nSum for %d terms by Formula =%d", n,sum);
}

Overwriting seriessum2.c

In [21]:

!gcc seriessum2.c -lm
!./a.out

Enter the value for n: 12

Sum by power for 12 terms =4095
Sum for 12 terms by method 2 =4095
Sum for 12 terms by Formula =4095

In [22]:

%%writefile seriessum3.c
/* Sum = 1^2 - 2^2 + 3^2 - 4^2 + .... + (-1)^(n-1)n^2 = (-1)^n n(n+1)/2 */
# include <stdio.h>
# include <math.h>
void main ()
{
  int n, sign, sum;
  printf ("\nEnter the value for n: ");
  scanf("%d", &n);
  // Dont use power inside loop, Take care alternate signs.
  sign=1;
  sum=1;
  for (int i=2;i<=n;i++) {
    sign=-sign;
    sum += sign*i*i;
  }
  printf ("\nSum for %d terms =%d", n,sum);

  sum = pow(-1, n-1)*n*(n+1)/2;
  printf ("\nSum for %d terms by Formula =%d", n,sum);
}

Writing seriessum3.c

In [24]:

!gcc seriessum3.c -lm
!./a.out

Enter the value for n: 11

Sum for 11 terms =66
Sum for 11 terms by Formula =66

In [25]:

%%writefile seriessum4.c
/* Sum = 1x2x3 + 2x3x4 + 3x4x5 + .... + n(n+1)(n+2) = n(n+1)(n+2)(n+3)/4 */
# include <stdio.h>
void main ()
{
  int n, sum;
  printf ("\nEnter the value for n: ");
  scanf("%d", &n);
  // Dont use power inside loop, Take care alternate signs.
  sum=0;
  for (int i=1, t1, t2;i<=n;i++) {
    t1= i+1;
    t2= i+2;
    sum += i*t1*t2;
  }
  printf ("\nSum for %d terms =%d", n,sum);

  sum = n*(n+1)*(n+2)*(n+3)/4;
  printf ("\nSum for %d terms by Formula =%d", n,sum);
}

Writing seriessum4.c

In [26]:

!gcc seriessum4.c
!./a.out

Enter the value for n: 10

Sum for 10 terms =4290
Sum for 10 terms by Formula =4290

In [27]:

%%writefile seriessum5.c
/* Sum = 2/3 + 2/9 + 2/27 + .... + 2/3^n = 1-(1/3^n) */
# include <stdio.h>
# include <math.h>
void main ()
{
  int n;
  printf ("\nEnter the value for n: ");
  scanf("%d", &n);
  // Dont use power inside loop, Take care alternate signs.

  float t1=2;
  float t2=3;
  float sum=0;
  for (int i=1;i<=n;i++) {
    sum += t1/t2;
    t2=3*t2; // ready for next term.
  }
  printf ("\nSum for %d terms =%f", n,sum);

  sum = 1-pow(3, -n);
  printf ("\nSum for %d terms by Formula =%f", n,sum);
}

Writing seriessum5.c

In [28]:

!gcc seriessum5.c -lm
!./a.out

Enter the value for n: 10

Sum for 10 terms =0.999983
Sum for 10 terms by Formula =0.999983

• $\pi$ is defined as the ratio of circumference to the diameter of any circle. It is a constant irrational number. So, its exact value is never ending and not known. It can be approximated to many digits after the decimal by using different techniques.
• Here we use Lebniz formula for $\pi/4$. $$ \frac{\pi}{4} =\frac{1}{1}+\frac{-1}{3}+\frac{1}{5}+\ldots = \sum_{j=0}^n \frac{(-1)^j}{2j+1}$$
• While doing programing, we stress evaluation term by term rather than using a sum side or formula based short-hand implementation.
• Generally, for alternate -ve +ve terms in a for loop is obtained by -1 raised to power to a variable (say j) other than counter of for loop that is initialised to zero before loop and then incremented inside the loop manually.

In [1]:

%%writefile valueOfPiLeibnitz.c
#include<stdio.h>
#include<math.h>
int main()
 {
    int count;
    float pi, j;
    printf(" Please Enter The  Number of Iteration: ");
    scanf("%d",&count);

    // Method 1: using power function
    pi=0;
    j=1;
    for (int i=0; i<count;i++) pi=pi+pow(-1,i)/(2*i+1);
    printf("Value of Pi(using Power) is %f",4*pi);

    // Method 2: using alternate -ve +ve terms and counter.
    pi=0.0;
    float t1=1, t2=1; // First term numerator and denominator.
    for (int i=0; i<count;i++) {
      pi=pi+t1/t2;
      t1=-t1;
      t2 += 2;
    }
    printf("\nValue of Pi(using Alternate) is %f",4*pi);
    return 0;
 }

Overwriting valueOfPiLeibnitz.c

In [2]:

!gcc valueOfPiLeibnitz.c -lm
!./a.out

 Please Enter The  Number of Iteration: 1000
Value of Pi(using Power) is 3.140593
Value of Pi(using Alternate) is 3.140593

Exponential series.¶

Evaluate the Exponential pwer series: $$e^x=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\ldots$$ We may get the sum identifying recurrence relation for $n>1$: $$T_n=T_{n-1}\left(\frac{x}{n}\right)$$ where, $T_0=1$ and $T_1=x$. If $T_n$ is known, $T_{n+1}$ can be known by multiplying $x/n$. This is a converging series, each successive term value decreases. We set an accuracy so that if term value is less than the accuracy, program stops. We count the number of terms needed for desired accuracy.

In [3]:

%%writefile exponential.c
# define ACCURACY 0.0001
#include<stdio.h>
void main()
{
  int n, count;
  float x, term, sum;
  printf("Enter the value of x:");
  scanf("%f",&x);

  n=sum=term=count=1;
  while(term>ACCURACY)
  {
    term=term*x/n;
    sum += term;
    n++;
    count++;
  }
  printf("Terms= %d e^(%f)= %f\n",count, x, sum);
}

Writing exponential.c

In [5]:

!gcc exponential.c
!./a.out

Enter the value of x:3.4
Terms= 16 e^(3.400000)= 29.964083

Sine Series¶

$$\sin x=x-x^3/3! + x^5/5! - x^7/7! \ldots$$ In the First program we use the formula for $i^{th}$ term. This involves use of power function and large factorial finding that are computer intensive.

The implementation must be changed so as to reduce computation. This is achieved by observing in the series the following steps:

• Alternate +ve and -ve sign.
• Steps jump by 2 values: tetm1 term3 ... .
• $t_1=\frac{t^x_1=x}{t^y_1=1}$, $t_3=\frac{t^x_3=-x^3}{t^y_3=3!}$, $t_5=\frac{t^x_5=x^5}{t^y_5=5!}$ ...
• $\frac{t^x_5}{t^y_5}=\frac{x^5}{5!} =\frac{-x^3}{3!}×\frac{-x^2}{4×5}=\frac{t^x_3}{t^y_3} ×\frac{-x^2}{4×5}= \frac{-x^2\times t^x_3}{4\times5\times t^y_3}$
• So, Taking $5=i$ : $\frac{t^x_{i}}{t^y_{i}} = \frac{-x^2\times t^x_{i-2}}{(i-1)i\times t^y_{i-2}}$
• As the loop progresses, for $n\ge 30$, the value of $n!$ becomes a massive number that exceeds the capacity of standard data types. In such scenarios, one could employ scientific notation or a symbolic language like Python or Scilab. This illustrates why these languages should be utilized when studying physical relations—they allow the user to focus on the underlying science without getting bogged down in low-level technical constraints. We will use Scilab for these purposes in subsequent semesters. However, a readily available trick within the current context is to note that, while the denominator grows huge, the overall term becomes very small, as is characteristic of any convergent series. Therefore, the most advisable approach is to compute subsequent terms iteratively by dividing the previous term by only the new factors that appear in the denominator.
• So, Taking $5=i$ : $T_i = \frac{-x^2\times T_{i-2}}{(i-1)i}$ can run till end.

The "second function" implements a more efficient approach, resulting in both improved speed and increased capacity. The initial implementation, which likely used direct calculation, could not handle a large number of terms because of storage limitations for extremely large factorials and the time required for their computation. The optimized second function overcomes these limitations. However, it should be noted that this approach may not improve the accuracy of the final sum beyond the machine's precision limit. The terms themselves become effectively zero for $n>25$, contributing nothing further to the sum. The optimization primarily allows the program to run without encountering execution errors or overflow disasters for larger input values.

In [68]:

%%writefile sineseries1.c
#include<stdio.h>
#include<math.h>
float fact(int r);
int main()
{
	int q=0,n;
	float ang,rad,pi=3.141,sinx;

	printf("Enter the angle in degree:\n");
	scanf("%f",&ang);
	rad=(pi/180.0)*ang;
	printf ("\nEnter the value of max terms(n~30): ");
  scanf ("%d", &n);

	sinx=0;
	for(int i=1;i<=n; i += 2) {
		sinx=sinx+(pow(rad,i)*((pow(-1,q))*(1/fact(i))));
		q++;
	}
	printf("The value of sin(%f) is %f",ang,sinx);
	printf("\nThe value of inbuilt sin(%f) is %f",ang,sin(rad));
}

float fact(int r)
{
	int j=1;
	for(int i=1;i<=r;i++) j=j*i;
	return(j);
}

Overwriting sineseries1.c

In [69]:

!gcc sineseries1.c -lm
!time ./a.out

Enter the angle in degree:
36

Enter the value of max terms(n~30): 30
The value of sin(36.000000) is 0.587689
The value of inbuilt sin(36.000000) is 0.587689
real	0m11.109s
user	0m0.000s
sys	0m0.002s

In [58]:

%%writefile sineseries2.c
/* Each term is calculated from previous term */
# include <stdio.h>
# include <math.h>
void main()
{
  float n, ang,rad,pi=3.141;
	printf("Enter the angle in degree:\n");
	scanf("%f",&ang);

  rad=(pi/180.0)*ang;
  printf ("\nEnter the value of max terms(n~30): ");
  scanf ("%f", &n);
  n=2*n; // As the sum jumps two values, max terms doubled.

  float tx=-rad*rad, ty;
  float term=rad, sum=term;
  for (float i=3; i<=n; i+=2) {  // i=1 First term is already stored in sum.
    term = term*tx;
    ty=i*(i-1);
    ty=1/ty;
    term = term*ty;
    sum += term;
    if (term==0) { // Demonstration only, not needed for the program.
      printf("\nFor iteration %.f ty=%f term=%f\n",i/2,ty,term);
      break;
    }
  }
  printf("\nThe value of sin(%5.2f) = %f",ang, sum);
  printf("\nThe value of inbuilt sin(%.2f) = %f",ang,sin(rad));
}

Overwriting sineseries2.c

In [59]:

!gcc sineseries2.c -lm
!time ./a.out

Enter the angle in degree:
30

Enter the value of max terms(n~30): 50

For iteration 16 ty=0.000947 term=0.000000

The value of sin(30.00) = 0.499914
The value of inbuilt sin(30.00) = 0.499914
real	0m10.403s
user	0m0.000s
sys	0m0.002s

In [52]:

%%writefile cosineseries1.c
/* cosx= 1 - x^2/2! +x^4/4! -x^6/6! + ...
* MacLAurin series for cosine function.
*/
# include<stdio.h>
# include<math.h>
float fact(int r);
int main()
{
	int q=0, n=20;
	float cosx=0,pi=3.14,t,x;

	printf("enter an angle:\n");
	scanf("%f",&x);
	t=(pi/180.0)*x;
	for(int i=0; i<=n; i += 2) {
		cosx=cosx+(pow(t,i)*(pow(-1,q)*1/fact(i)));
		q++;
    }
    printf("\nThe value of cos(%.2f) is %f",x,cosx);
		printf("\nThe value of inbuilt cos(%.2f) is %f",x,cos(t));
}

float fact (int r)
    {
    	int j=1;
    	for(int i=1;i<=r;i++) j=j*i;
		  return(j);
	}

Overwriting cosineseries1.c

In [53]:

!gcc cosineseries1.c -lm
!./a.out

enter an angle:
34

The value of cos(34.00) is 0.829206
The value of inbuilt cos(34.00) is 0.829206

In [49]:

%%writefile cosineseries2.c
/* cosx= 1 - x^2/2! +x^4/4! -x^6/6! + ...
* MacLAurin series for cosine function.
*/
# include<stdio.h>
# include<math.h>

int main()
{
	int n=20;
	float cosx,pi=3.14, ang, rad;

	printf("enter an angle:\n");
	scanf("%f",&ang);
	rad=(pi/180.0)*ang;

	float term=1, ty=1, t=-rad*rad;
	cosx=term;
	for(int i=2; i<=n; i += 2)
	{
			ty=i*(i-1);
			ty=1/ty;
			term = term*t*ty;
			cosx=cosx+term;
	}
    printf("\nThe value of cos(%.2f) is %f",ang,cosx);
		printf("\nThe value of inbuilt cos(%.2f) is %f",ang,cos(rad));
}

Overwriting cosineseries2.c

In [51]:

!gcc cosineseries2.c -lm
!./a.out

enter an angle:
34

The value of cos(34.00) is 0.829206
The value of inbuilt cos(34.00) is 0.829206