Linear Congruences

A congruence of the

where m is a positive integer, a and b are integer and x is a variable, is called a linear congruence.

Peasant or binary multiplication

Peasant or binary multiplication has been widely used among those who are unschooled and thus have not memorized the multiplication tables required by long multiplication. The algorithm was also in use in ancient Egypt [Wiki]. :)

Explain:
suppose,
the task is to find the value of 12 x 7

Recurrence Relation : How many 1's between 0 to n

Explain:
we know,
Total Number of 1 bit between 0 to 2^n-1
On = 2^(n-1) + 2*On-1 [Read: Recurrence Relation : How many 1's between 0 to (2^n-1) ]
Vn = 2^n -1 

Now,
1. Given n and let T1 = 0
2. Nn = n
3. find i, where v[i]>Nn
4. T1 = o[i-1]
5. MSB_ONE = Nn - v[i-1];
6. T1 = T1+MSB_ONE;
7. Now new, Nn = MSB_ONE-1;
8. break if Nn<=0; otherwise go to step3

Recurrence Relation : How many 1's between 0 to (2^n-1)

Explain:
0
1

Total Number of 1 bit between 0 to 1
O1 = 1


Total Number of 1 bit between 0 to 3 (2^2 - 1)
O2 = 2 + 2*f(1) = 2^(2-1)+ 2*O1

Total Number of 1 bit between 0 to 7 (2^3-1)
O3 =  2^(3-1)+ 2*O2

so the recurrence relation is
On = 2^(n-1) + 2*On-1





Iteration:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

#include<stdio.h> typedef unsigned long long int64; int main(){ int64 O[65],two; int i; O[1]=1; two = 1; printf("Total Number of 1's bits between 0 and %llu:%llu\n",(two<<1)-1,O[1]); for (i=2;i<64;i++){ two = two<<1; O[i] = two + 2*O[i-1]; printf("Total Number of 1's bits between 0 and %llu:%llu\n",(two<<1) -1,O[i]); } return 0; }

Output:

 


Recursion:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

#include<stdio.h> typedef unsigned long long int64; int64 O[65]; int64 count1(int l){ int64 two =1,a=0; if (l==1) return 1; two = two<<(l-1); return a = a+ (2*count1(l-1))+two; } int main(){ int64 two=1; int i; for (i=1;i<64;i++){ O[i] = count1(i); two = two<<1; printf("Total Number of 1's bits between 0 and %llu:%llu\n",two-1,O[i]); } return 0; }

Convert a decimal Number to Binary Without array in C

Algorithm:
1. take input x
2. Initialize r := 0,cb = 0;
3. while(x!=0) Begin
4. cb := cb+1, r := left shift by 1 bit
5. r :=r + (x&1)
6. n:= right shift by 1;
7. End

Count Bits of a Number in C

It is very simple to determine the number of bits of an integer number:
Algorithm:
1. take input x, initialize countbit : = 0
2. check x is zero, yes then go to step 5
3. x: = Shift one bit left of x,countbit:=countbit+1;
4. go to step 2.
5. End

The Foundation: Logic & Proof - 01

Problem Definition: we want to solve 3 or less variable logical Expression. For example: Let, Given Logical Expression: (a|b)&(c|b)
Output:

a	b	c	(a|b)&(c|b)
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1