NUMERIC
ALGORITHM
DSA GROUP 6
DEPARTMENT OF COMPUTER SCIENCE, UNIVERSITY OF ILORIN, ILORIN, NIGERIA
GROUP MEMBERS
1. ISHOLA ABDULMALIK KAYODE 22/52HA191
2. FAJUYIGBE ABIOLA LYDIA 21/25PJ020
3. DAIRO MUBARAK AYODEJI 21/25PJ019
4. BUSARI FOUADH OMOGBOLAHAN 21/52HA059
5. BABATUNDE OLAMIDE PRECIOUS 21/52HA052
6. LATEEFAT BELLO 21/52HA058
7. BADMUS ARAFAT AYOMIDE 21/52HA053
8. CONDE NAYUMA 21/52HA060
9. BAKER OLUWASEUN FUAD 21/52HA055
10. FOLORUNSHO OLUWATIMILEHIN ISRAEL 21/25PJ022
11. BAKARE IRETOMIWA PETER 21/52HA054
12. FEHINTOLA IBRAHIM OPEYEMI 21/25PJ021
13. BASSEY SHARON 21/52HA057
14. ABDULLAHI MOHAMMED DAUDA 21/52HA062
WHAT ARE NUMERIC ALGORITHMS?
• NUMERIC ALGORITHMS ARE STEPS OR PROCEDURES USED TO SOLVE MATH
PROBLEMS USING COMPUTERS.
• THESE ALGORITHMS HELP IN CALCULATIONS LIKE FINDING PRIME NUMBERS,
CONVERTING BETWEEN NUMBER SYSTEMS, AND MORE.
PRIMALITY TEST: WHAT IS A PRIME
NUMBER?
● A PRIME NUMBER IS A NUMBER GREATER THAN 1 THAT HAS NO DIVISORS OTHER THAN
1 AND ITSELF.
● EXAMPLES: 2, 3, 5, 7, 11 ARE PRIME NUMBERS.
● NON-PRIME NUMBERS: 4, 6, 8, ETC., BECAUSE THEY CAN BE DIVIDED BY OTHER
NUMBERS.
• THERE ARE 2 WAYS TO FIND PRIME NUMBERS IN A GIVEN SET OF NUMBERS:
• ● SCHOOL METHOD
• ● OPTIMIZED SCHOOL METHOD .
• 1. SCHOOL METHOD: A SIMPLE SOLUTION IS TO ITERATE THROUGH ALL NUMBERS FROM 2 TO N-1 AND
FOR EVERY NUMBER CHECK IF IT DIVIDES N. IF WE FIND ANY NUMBER THAT DIVIDES, WE RETURN
FALSE. IT IS A STRAIGHTFORWARD AND INTUITIVE APPROACH TO CHECK WHETHER A GIVEN NUMBER N
IS A PRIME NUMBER.
• EFFICIENCY OF THE SCHOOL METHOD: - TIME COMPLEXITY: O(N) , SINCE IT ITERATES THROUGH ALL
NUMBERS FROM 2 TO N-1. FOR LARGE N , THIS CAN BE SLOW.
• LIMITATIONS: - THE METHOD IS INEFFICIENT FOR LARGE NUMBERS BECAUSE OF ITS LINEAR TIME
COMPLEXITY.
• - MORE OPTIMIZED METHODS, LIKE CHECKING DIVISORS UP TO SQRT{N} , CAN SIGNIFICANTLY
REDUCE THE COMPUTATIONAL EFFORT.
• 2. THE OPTIMIZED SCHOOL METHOD FOR PRIMALITY TESTING IMPROVES THE BASIC SCHOOL METHOD
BY REDUCING THE NUMBER OF DIVISORS WE NEED TO CHECK. THIS IS ACHIEVED BY RECOGNISING A
KEY MATHEMATICAL PROPERTY ABOUT DIVISORS AND FACTORS. FOR ANY NUMBER N, IF IT HAS A
DIVISOR LARGER THAN SQRT{N}, THERE MUST BE A CORRESPONDING DIVISOR SMALLER THAN SQRT{N}.
.
.
PRIMALITY TEST ALGORITHM
● THE ALGORITHM CHECKS IF A NUMBER IS PRIME.
● THE ALGORITHM CHECKS DIVISIBILITY FROM 2 TO THE SQUARE ROOT OF THE NUMBER.
● IF NO NUMBER DIVIDES EVENLY, IT’S PRIME. IF A DIVISOR IS FOUND, IT’S NOT PRIME.
• STEPS FOR IS PRIME(N):
1. LOOP THROUGH NUMBERS FROM 2 TO √N.
2. IF ANY NUMBER DIVIDES N, RETURN FALSE.
3. IF NO DIVISOR IS FOUND, RETURN TRUE (PRIME).
BASE CONVERSIONS: WHY CONVERT
NUMBERS?
• BASE CONVERSIONS ARE A FUNDAMENTAL CONCEPT IN COMPUTER SCIENCE AND DIGITAL SYSTEMS.
COMPUTERS USE BINARY (BASE-2) TO REPRESENT DATA, WHILE HUMANS ARE MORE COMFORTABLE WITH
DECIMAL (BASE-10). THEREFORE, IT'S OFTEN NECESSARY TO CONVERT NUMBERS BETWEEN DIFFERENT
NUMERAL SYSTEMS (LIKE DECIMAL TO BINARY, HEXADECIMAL TO DECIMAL, AND MORE).
• FOR EXAMPLE, THE DECIMAL NUMBER 74 IS WRITTEN AS 1001010 IN BINARY.
• WHY ARE BASE CONVERSIONS IMPORTANT?
1. DIGITAL SYSTEMS: COMPUTERS USE BINARY (BASE-2) TO PROCESS DATA, SO KNOWING HOW TO CONVERT
BETWEEN DECIMAL AND BINARY HELPS IN PROGRAMMING AND WORKING WITH COMPUTER HARDWARE.
2. ERROR DETECTION: BASE CONVERSIONS ARE ALSO USED TO CHECK FOR ERRORS IN DATA TRANSMISSION OR
STORAGE, HELPING ENSURE DATA IS CORRECT.
BASE CONVERSION ALGORITHM
(DECIMAL TO BINARY)
● THE ALGORITHM HELPS TO CONVERT A DECIMAL NUMBER TO BINARY.
• STEPS FOR CONVERSION TO BINARY(N):
1. DIVIDE THE NUMBER BY 2 AND SAVE THE REMAINDER.
2. REPEAT UNTIL THE NUMBER BECOMES 0.
3. REVERSE THE SAVED REMAINDERS TO GET THE BINARY FORM.
• EXAMPLE FOR DECIMAL 74 → BINARY 1001010.
GREATEST COMMON DIVISOR (GCD)
● THE GREATEST COMMON DIVISOR (GCD) IS A CLASSIC EXAMPLE OF A NUMERIC ALGORITHM, WIDELY USED TO
SOLVE PROBLEMS INVOLVING INTEGERS. IT IDENTIFIES THE LARGEST NUMBER THAT EVENLY DIVIDES TWO OR
MORE INTEGERS
• EXAMPLE:
• INPUT: A = 20, B = 28
OUTPUT: 4
•
EXPLANATION: THE FACTORS OF 20 ARE 1, 2, 4, 5, 10 AND 20. THE FACTORS OF 28 ARE 1, 2, 4, 7, 14 AND 28. AMONG
THESE FACTORS, 1, 2 AND 4 ARE THE COMMON FACTORS OF BOTH 20 AND 28. THE GREATEST AMONG THE COMMON
FACTORS IS 4.
THERE ARE 2 WAYS TO GET THE GCD OF 2 NUMBERS IN DSA
1. NAIVE/BASIC/BRUTE METHOD
2. EUCLIDEAN METHOD
E
M
• 2. EUCLUIDEAN METHOD: THE EUCLIDEAN ALGORITHM IS ONE OF THE MOST EFFICIENT METHODS TO CALCULATE THE
GCD OF TWO NUMBERS. THIS WORKS BECAUSE THE GCD OF TWO NUMBERS DOESN’T CHANGE IF YOU REPLACE THE
LARGER NUMBER WITH ITS REMAINDER WHEN DIVIDED BY THE SMALLER NUMBER. YOU REPEAT THIS PROCESS UNTIL THE
REMAINDER BECOMES 0. AT THAT POINT, THE OTHER NUMBER IS THE GCD.
• PRINCIPLE FOR EUCLIDEAN IS: GCD(N, M % N). .
• HOW IT WORKS
1. THE ALGORITHM USES RECURSION TO REPEATEDLY REDUCE THE PROBLEM SIZE BY COMPUTING REMAINDERS.
2. THE BASE CASE ENSURES TERMINATION WHEN THE SECOND NUMBER BECOMES 0.
• STEPS
1. BASE CASE:
● IF N = 0, THE GCD IS M.
● THIS IS BECAUSE ANY NUMBER IS DIVISIBLE BY 0, AND THE OTHER NUMBER (M) IS THE GCD.
● EXAMPLE: GCD(9, 0) = 9.
1. IF N IS NOT EQUAL TO 0, THE ALGORITHM REDUCES THE PROBLEM TO SMALLER NUMBERS BY REPLACING M WITH N AND
N WITH M % N.
• REPEAT THE PROCESS CONTINUES UNTIL N BECOMES 0, AT WHICH POINT THE VALUE OF M IS THE GCD.
.
MAXIMUM VALUE IN A NUMBER SYSTEM
● THE ALGORITHM CALCULATES THE MAXIMUM NUMBER THAT CAN BE FORMED WITH N
DIGITS IN A GIVEN NUMBER SYSTEM (BINARY, DECIMAL, ETC.).
● EXAMPLE: THE MAXIMUM 4-DIGIT NUMBER IN DECIMAL IS 9999. IN BINARY, IT IS 1111 (15
IN DECIMAL).
MAX VALUE ALGORITHM
● THE FORMULA TO FIND THE MAXIMUM VALUE IS: B^N - 1, WHERE B IS THE BASE AND N IS THE NUMBER
OF DIGITS.
● EXAMPLE: MAXIMUM VALUE IN HEXADECIMAL (BASE 16) FOR 6 DIGITS IS FFFFFF (16777215 IN DECIMAL).
• STEPS FOR MAX VALUE(NUMBER BASE, N):
1. IDENTIFY THE NUMBER SYSTEM.
2. DETERMINE THE NUMBER OF DIGITS
3. USE THE FORMULA B^N - 1.
4. RETURN THE RESULT.
FACTORIAL OF A NUMBER
● THE FACTORIAL OF A NUMBER IS THE PRODUCT OF ALL INTEGERS FROM 1 TO THAT
NUMBER.
● EXAMPLE: 4! = 4 × 3 × 2 × 1 = 24.
• SPECIAL CASES:
• 0! = 1 (BY DEFINITION)
• 1! = 1
FACTORIAL ALGORITHM (ITERATIVE)
• A FACTORIAL ALGORITHM IS A METHOD TO CALCULATE THE FACTORIAL OF A NUMBER N USING A LOOP OR
RECURSION. THE FACTORIAL OF A NUMBER N IS :
• N!=N×(N−1)×(N−2)×⋯×1N! = N \TIMES (N-1) \TIMES (N-2) \TIMES \DOTS \TIMES 1N!=N×(N−1)×(N−2)×⋯×1
• STEPS FOR FACTORIAL(N):
1. START WITH A RESULT OF 1.
2. MULTIPLY BY EACH NUMBER FROM 2 TO N.
3. RETURN THE FINAL RESULT
APPLICATION OF NUMERICAL ALGORITHM
NUMERICAL METHOD IS MATHEMATICAL WHILE A NUMERICAL ALGORITHM IS A
PRECISE STEPS THAT IMPLEMENT A NUMERICAL METHOD
WEATHER FORECASTING: USED TO PREDICT THE WEATHER BY SOLVING EQUATIONS THAT DESCRIBE
ATMOSPHERIC BEHAVIOR.
FINANCE: HELPS IN PRICING STOCKS, MANAGING RISK, AND OPTIMIZING INVESTMENT PORTFOLIOS.
SEARCH ENGINES: RANKING ALGORITHMS USE MATH TO DETERMINE THE MOST RELEVANT WEB PAGES FOR
YOUR SEARCH.
ROBOTICS: ALGORITHMS HELP ROBOTS PLAN THEIR MOVEMENTS AND AVOID OBSTACLES FOR PRECISE ACTIONS
THESE EXAMPLES HIGHLIGHT HOW NUMERICAL ALGORITHMS POWER DIVERSE APPLICATIONS ACROSS
INDUSTRIES, MAKING THEM INTEGRAL TO MODERN TECHNOLOGY AND EVERYDAY LIFE
SUMMARY OF NUMERIC ALGORITHMS
● WE LEARNED ABOUT SEVERAL NUMERIC ALGORITHMS THAT HELP SOLVE COMMON PROBLEMS IN
MATHEMATICS.
1. PRIMALITY TEST: CHECKING IF A NUMBER IS PRIME.
2. BASE CONVERSIONS: CONVERTING NUMBERS BETWEEN DIFFERENT NUMBER SYSTEMS.
3. GCD: FINDING THE GREATEST COMMON DIVISOR.
4. MAX VALUE IN A SYSTEM: FINDING THE LARGEST NUMBER WITH N DIGITS IN A SPECIFIC
BASE.
5. FACTORIAL: CALCULATING THE PRODUCT OF NUMBERS UP TO A GIVEN NUMBER.
● THESE ALGORITHMS HELP POWER SYSTEMS IN REAL-WORLD APPLICATIONS LIKE WEATHER
FORECASTS, COMPUTATIONS, ETC.
THANK YOU
ANY QUESTIONS?
FEEL FREE TO ASK IF YOU NEED CLARIFICATION