Vedic Mathematics- The Cosmic Software for Implementation of Fast Algorithms

Contributed by:
Harshdeep Singh
This PDF contains :
1. Introduction,
2. Vedic Mathematics Sutra,
2.1 Nikhilam navata charanam Dashatah,
2.2 Urdhva-tiryakbyham,
3. Uses of Vedic Sutras,
3.1 VLSI Implementation of RSA encryption,
3.2 Multiplier and square architecture,
3.3 Discrete Fourier Transform,
3.4 Digital Signal Processing,
3.5 Block Convolution,
3.6 ALU Design,
3.7 Elliptic Curve Encryption,
4. Performance Analyses of Vedic Algorithms,
Dr.S.M.Khairnar Ms. Sheetal Kapade Mr.Naresh Ghorpade
Professor and Head Assistant Professor Assistant Professor
Maharashtra Academy of Sinhgad Academy of Engineering, Sinhgad College of Science,Pune
Engineerimg,Alandi,Pune Pune [email protected]
[email protected] [email protected]
Abstract principles. These principles are general in nature
Veda, by definition, is ‘store house of and can be applied in many ways. In practice
knowledge’. Hence Vedic Mathematics has a many applications of the sutras may be learned
much ancient origin though attributed to the and combined to solve actual problems. The
techniques rediscovered between 1911, 1918. beauty of Vedic mathematics lies in the fact that
Mathematicians from across the spectrum from it reduces otherwise cumbersome looking
Hindu, Buddha and Jaina subcultures have calculations in conventional mathematics to a
contributed immensely to this body of very simple ones [2]. This is so because the
knowledge. Now a day’s interest in Vedic Vedic formulae are claimed to be based on the
Mathematics is growing in the field of computer natural principles on which the human mind
science where researchers are looking for a new works. This is a very interesting field and
and better approach to the subject. Even foreign presents some effective algorithms which can be
researchers are said to be using this ancient applied to various branches of engineering such
technique for implementation of fast algorithms. as computing , VLSI implementation and
In this survey paper, we will provide the readers digital signal processing.
an overview of the Vedic mathematics, as well as This paper is organized as follow: Section 2
several extended work in the area. In addition, provides overview of the vedic sutras like
we also review several state-of-art applications “Nikhilam navata charanam Dashatah”,
that take full advantage of such simple ancient “Urdhva-tiryakbyham”, Uses of these sutras are
Vedic Mathematical technique. elaborated in section 3, performance of Vedic
algorithms analyzed in section 4, and last section
Key words: Vedic mathematics, Nikhilam sutra, concludes the paper.
Urdhva-tiryakbyham, RSA algorithm 2. Vedic Mathematics Sutra
1. Introduction Vedic Mathematics essentially rests on the 16
The ancient system of Vedic Mathematics was Sutras or mathematical formulas as referred to in
rediscovered from the Indian Sanskrit texts the Vedas. Sri Sathya Sai Veda Pratishtan has
known as the Vedas, between 1911 and 1918 by compiled these 16 Sutras and 13 sub-Sutras [1].
Sri Bharati Krishna Tirthaji (1884-1960) [1]. The In the field of engineering most of the researcher
word ‘Vedic’ is derived from the word ‘Veda’ are using following sutras
which means the store-house of all knowledge. i) Nikhilam navata charanam Dashatah,
Vedic Mathematics is based on sixteen sutras or ii) Urdhva-tiryakbyham
2. 2.1 Nikhilam navata charanam Dashatah From the above equation we can derive the left
The formula simply means: “all from 9 and the hand side of the product as {x – y1} or {y– x1}
last from 10”. The algorithm has its best case in and the right hand side as (x1.y1)
multiplication of numbers, which are nearer to The basic operations involved in the algorithm
bases of 10, 100, 1000 i.e. increased powers of for a given set of numbers are given below.
10. The procedure of multiplication using the Consider 98 x 97
Nikhilam involves minimum mental manual Here the Nearest Base = 100
calculations, which in turn will lead to reduced
number of steps in computation, reducing the
space, saving more time for computation. The
numbers taken can be either less or more than the
base considered. The mathematical derivation of
the algorithm is given below.
Consider two n-bit numbers x and y to be
multiplied. Then their complements can be
represented as x1 = 10n - x and y1 = 10n – y. The
product of the two numbers can be given as p =
(x, y). Now a factor 102n +10n (x + y) is added
and subtracted on the right hand side of the
Result = 98 x 97 = 9506
product equation, which is mathematically
The Nikhilam Sutra can also be modified for
expressed as shown below.
binary arithmetic.
p = xy + 102n +10n (x + y) - 102n - 10n ( x + y)
2.2 Urdhva-tiryakbyham
On simplifying we get,
This is the general formula which is applicable to
p = {10n (x + y) - 102n} + {102n -10n (x + y) + xy}
all cases of multiplication. Urdhva Triyagbhyam
= 10n {(x + y) - 10n} + {(10n – x) ( 10n – y)} =
means “Vertically and Crosswise”, which is the
10n {x – y1} + {x1 y1}
method of multiplication followed.
= 10n {y – x1} + {x1 y1}
Illustration: Consider the product (325 X 738)
3. Figure 1: Steps for multiplication by Urdhva tiryakbhyam Sutra
has a small box common to a digit of the
Let us consider the multiplication of (5498 × multiplicand. These small boxes are partitioned
2314). The conventional method which is into two halves by the crosswise lines. Each digit
already known to us will require 16 of the multiplier is then independently multiplied
multiplications and 15 additions. with every digit of the multiplicand and the two
An alternative method of multiplication using digit product is written in the common box. All
Urdhva tiryakbhyam Sutra is shown in figure 2. the digits lying on a crosswise dotted line are
The numbers to be multiplied are written on two added to the previous carry. The least significant
consecutive sides of the square as shown in the digit of the obtained number acts as the result
figure 1. The square is divided into rows and digit and the rest as the carry for the next step.
columns where each row/column corresponds to Carry for the first step (i.e., the dotted line on the
one of the digit of either a multiplier or a extreme right side) is taken to be zero.
multiplicand. Thus, each digit of the multiplier
4. Figure 2: Alternative way of multiplication by Urdhva tiryakbhyam Sutra
• Algorithm for 3 by 3 multiplication
Step 1 Step 2 Step 3 Step 4 Step 5
• Algorithm for 4 by 4 multiplication
Step 1 Step 2 Step 3 Step 4
Step 5 Step 6 Step 7
3. Uses of Vedic Sutras designing, Discrete Fourier Transform , High
Vedic mathematics is used by several researchers speed low power VLSI arithmetic and algorithm,
in the field of Digital signal processing, Chip RSA encryption system . Most of the researchers
5. have used the vedic mathematics method such as There are many algorithms for finding DFT. But
multiplication, division, squares and cubes in now a day’s only VAN-NEUMAN architectural
above mention fields. implementation of classical method is found to
3.1 VLSI Implementation of RSA encryption be used in digital computers.
H. Thapliyal [3] implementated RSA encryption Mr.S.Kulkarni [5] analyzes and compares the
or decryption algorithm using the algorithm of implementation of Discrete Fourier Transform
ancient Indian vedic mathematics which is being algorithm by existing and by vedic mathematics
modified to improve the performance .The most techniques. It is suggested that architectural level
significant aspect is the development of divisor changes in the entire computation system to
architecture based on straight division algorithm accommodate the Vedic Mathematics method
of Vedic mathematics and embedding it in RSA increases the overall efficiency of DFT
encryption or decryption circuitry for improved procedure.
efficiency .They proved that RSA circuitry 3.4 Digital Signal Processing
implemented using vedic division and Digital Signal processing is a technology that is
multiplication is efficient in terms of area and present in almost every engineering discipline. It
speed compared to its implementation using is also the fastest growing technology of the
conventional multiplication and division century and hence it posses tremendous
architecture. challenges to the engineering community. Faster
3.2 Multiplier and square architecture addition and multiplication are of extreme
Time, area and power efficient multiplier and importance in DSP for Convolution, DFT and
square architecture based on ancient Indian vedic Digital filters .The core computing process is
mathematics is developed by H. Thapliyal [4]. always a multiplication routine and hence DSP
Developed algorithm was for low power and engineers are constantly looking for new
high speed applications. It is based on generating algorithms and hardware to implement them. The
partial product and their sums in one step. The methods in Vedic Mathematics are
design implemented is described at both gate and complementary directly and easy. Mr. Mangesh
high level using verilog Hardware Description Karad and Mr. Chidgupkar [6] highlight the use
Language. The design code is tested using of multiplication process based on vedic
“Veriwelsimulator. Their work relates to the algorithms and implemented on 8085 and 8086
field of mathematical coprocessor in computers microprocessors. Use of Vedic algorithms shows
and more specifically to improve speed and appreciable saving of processing time.
power over the conventional co-processor. 3.5 Block Convolution
The Vedic multiplier and square architecture In DSP applications convolution with very long
developed by them were faster than array sequence is often required. To compute
multiplier and booth multiplier in FPGA convolution of long sequence overlap add
implementation. method (OLA) and overlap solve method (OLS)
3.3 Discrete Fourier Transform can be considered which are well known
6. efficient schemes for high order filtering. a high speed power efficient multiplier in the co-
Hanumantharaju M. C., Jayalakshami H.[7] processor. Using Vedic techniques various
proposed a high performance and area efficient arithmetic modules can be designed and
architecture for FPGA implementation of block integrated into a Vedic ALU, which is
convolution. By using vertically and crosswise compatible for co-processor. The advantages of
structure of vedic mathematics new multiplier Vedic multipliers are increase in speed, decrease
architecture is developed and embedded it into in delay, decrease in power consumption and
OLA and OLS methods for improved efficiency. decrease in area occupancy. This Vedic co-
The result shows that the proposed vedic processor is more efficient than the conventional
multiplier architecture achieves a significant one.
improvement in performance over the traditional 3.7 Elliptic Curve Encryption
multiplier architectures. If the bits in the number H. Thapliyal and M.B. Srinivas [9] developed an
are continuously increased to N by N ( N is any algorithm for point doubling using square
number) bits then Vedic Mathematics algorithm of ancient Indian Vedic mathematics.
architecture shows greatest advantage as In order to calculate efficient hardware circuit,
compare to other architectures of the multipliers square of a number and duplex D property of
over gate delays and regularity of structure. binary numbers. Also the techniques for
3.6 ALU Design computation of fourth power of number are
The ever increasing demands in enhancing the proposed. A considerable input in the point
ability of processors to handle the complex and addition and doubling has been observed when
challenging processes has resulted in the implemented using proposed techniques for
integration of number of processor cores into one exponentiation.
chip still the load on processor is not less. This 4. Performance Analyses of Vedic Algorithms
load is reduced by supplementing the main co- Various parameters are recommended by
processor which is designed to work on specific researchers to evaluate the performance of Vedic
types of functions like numeric computations, Maths algorithm. Researchers suggested many
signal processing, graphics etc. The speed of parameters few of them are: Time, Delay, Power
ALU depends on the multipliers. In algorithm and Number of slices.
and structure levels, numerous multiplication The following table shows the comparison of
techniques have been developed to enhance the Delay (ns) factor for multiplication implemented
efficiency of multiplier which concentrates on in different algorithms between Conventional
reducing the partial product and their additions. and Vedic way.
But in this case principle behind the Conclusion
multiplication remains same. Use of Vedic Vedic mathematics can be used in
mathematics for multiplication strikes difference implementation of fast algorithms in various
in actual process. M. Ramalatha [8] used Urdhva fields of engineering. The performance analysis
tiryakbhyam Sutra of Vedic mathematics to build of Vedic algorithms is done on the basis of delay.
7. This shows efficiency of Vedic multiplier in
terms of high speed and less complexity
Sr. No. Implemented in Conventional Vedic
8 bit 16 bit 8 bit 16 bit
01 VLSI Implementation of High 31.241 57.973 26.081 54.973
Performance RSA Algorithm
02 High Speed Energy Efficient 31.029 46.811 15.418 22.604
ALU Design
03 An Efficient Method of Elliptic 30.370 60.646 15.193 23.600
Curve Encryption ( for square)
04 An Efficient Method of Elliptic 604.861 1327.809 542.325 1207.677
Encryption ( for point
Table No. 1
. References: Vedic Mathematics”, Proceedings of
[1] Swami Bharati Krishna Tirthaji , Vedic International Conference on Computational
Mathematics. Delhi: Motilal Banarsidass Intelligence and Multimedia Applications,
Publishers, 1965. 2007.
[2] Vedic Mathematics [Online]. Available: [8] M. Ramalatha, K. Deena Dayalan, P. Dharani, “ High Speed Energy Efficient ALU Design
Accessed November 2010. using Vedic Multiplication Techniques”
[3] H. Thapliyal and M. B. Srinivas “VLSI ACTEA, IEEE pp 600-603
implementation of RSA Encryption system [9] H. Thapliyal and M. B. Srinivas, “An
using Vedic Mathematics”, Proceedings of Efficient Method of Elliptic Curve
International Conferenceon Security Encryption Using Ancient Indian Vedic
Management, 2005. Mathematics”, Proc. IEEE MIDWEST
[4] H. Thapliyal and M. B. Srinivas, “High symp.Circuits and systems, pp. 826{829,
Speed Efficient N by N Bit Parallel Cincinnati, Aug. 2005.
Hierarchical Overlay Multiplier Architecture
Based", pp. 225-228, Dec. 2004.
[5] Mr.Shripad Kulkarni “ Discrete Fourier
Transform by Vedic Mathematics”
[6] P. D. Chidgupkar and M. T. Karad, “The
Implementation of Vedic Algorithms in
Digital Signal Processing”, Global J. of
Engg. Edu., Vol.8, No. 2, pp. 153-158, 2004.
[7] Hanumantharaju M. C., Jayalakshami H.,
Renuka R, Ravishankar M., “High Speed
Block Convolution using Ancient Indian