© Guest Editors’ Introduction: The Top 10 Algorithms

An algorithm is a sequence of finite computational steps that
transforms an input into an output. (Cormen and Leiserson, 2009)

Algos is the Greek word for pain. Algor is Latin, to be cold. Neither is the root for algorithm, which stems instead from al-Khwarizmi, the name of the ninth-century Arab scholar whose book al-jabr wa’l muqabalah devolved into today’s high school algebra textbooks. Al-Khwarizmi stressed the importance of methodical procedures for solving problems. Were he around today, he’d no doubt be impressed by the advances in his eponymous approach.

Some of the very best algorithms of the computer age are highlighted in the January/February 2000 issue of Computing in Science & Engineering, a joint publication of the American Institute of Physics and the IEEE Computer Society. Guest editors Jack Don-garra of the University of Tennessee and Oak Ridge National Laboratory and Fran-cis Sullivan of the Center for Comput-ing Sciences at the Institute for Defense Analyses put togeth-er a list they call the “Top Ten Algorithms of the Century.”

“We tried to assemble the 10 al-gorithms with the greatest influence on the development and practice of science and engineering in the 20th century,” Dongarra and Sullivan write. As with any top-10 list, their selections—and non-selections—are bound to be controversial, they acknowledge. When it comes to picking the algorithmic best, there seems to be no best algorithm.

1946: Metropolis Algorithm for Monte Carlo

John von Neumann, Stan Ulam, and Nick Metropolis, all at the Los Alamos Scientific Laboratory, cook up the Metropolis algorithm, also known as the Monte Carlo method.

Monte Carlo methods are the only practical choice for evaluating problems of high dimensions.

1947: Simplex Method for Linear Programming

George Dantzig, at the RAND Corporation, creates the simplex method for linear programming.

The Simplex method relies on noticing that the objective function’s maximum must occur on a corner of the space bounded by the constraints of the “feasible region.”

1950: Krylov Subspace Iteration Methods

Magnus Hestenes, Eduard Stiefel, and Cornelius Lanczos, all from the Institute for Numerical Analysis at the National Bureau of Standards, initiate the development of Krylov subspace iteration methods.

The importance of iterative algorithms in linear algebra stems from the simple fact that a direct approach will require \( O(N^3) \) work. The Krylov subspace iteration methods have led to a major change in how users deal with large, sparse, nonsymmetric matrix problems.

1951: The Decompositional Approach to Matrix Computations

Alston Householder of Oak Ridge National Laboratory formalizes the decompositional approach to matrix computations.

Introducing the decompositional approach to matrix computations revolutionized the field.

1957: The Fortran Optimizing Compiler

John Backus leads a team at IBM in developing the Fortran optimizing compiler.

The creation of Fortran may rank as the single most important event in the history of computer programming: Finally, scientists (and others) could tell the computer what they wanted it to do, without having to descend into the netherworld of machine code. Although modest by modern compiler standards—Fortran I consisted of a mere 23,500 assembly-language instructions—the early compiler was nonetheless capable of surprisingly sophisticated computations. As Backus himself recalls in a recent history of Fortran I, II, and III, published in 1998 in the IEEE Annals of the History of Computing, the compiler “produced code of such efficiency that its output would startle the programmers who studied it.”

1959: QR Algorithm for Computing Eigenvalues

J.G.F. Francis of Ferranti Ltd., London, finds a stable method for computing eigenvalues, known as the QR algorithm.

The QR Algorithm for computing eigenvalues of a matrix has transformed the approach to computing the spectrum of a matrix.

1962: Quicksort Algorithm for Sorting

Tony Hoare of Elliott Brothers, Ltd., London, presents Quicksort.

Hoare’s algorithm uses the age-old recursive strategy of divide and conquer to solve the problem.

Sorting is a central problem in many areas of computing so it is no surprise to see an approach to solving the problem as one of the top 10. Quicksort is one of the best practical sorting algorithm for general inputs. In addition, its complexity analysis and its structure have been a rich source of inspiration for developing general algorithm techniques for various applications.

1965: Fast Fourier Transform

James Cooley of the IBM T.J. Watson Research Center and John Tukey of Princeton University and AT&T Bell Laboratories unveil the fast Fourier transform.

Easily the most far-reaching algo-rithm in applied mathematics, the FFT revolutionized signal processing. The underlying idea goes back to Gauss (who needed to calculate orbits of asteroids), but it was the Cooley–Tukey paper that made it clear how easily Fourier transforms can be computed. Like Quicksort, the FFT relies on a divide-and-conquer strategy to reduce an ostensibly \( O(N^2) \) chore to an \( O(NlogN) \) frolic. But unlike Quick- sort, the implementation is (at first sight) nonintuitive and less than straightforward. This in itself gave computer science an impetus to investigate the inherent complexity of computational problems and algorithms.

Mozart could listen to music just once and then write it
down from memory without any mistakes. (Vernon, 1996)

FFT is an algorithm “the whole family can use.” The FFT is perhaps the most ubiquitous algorithm in use today to analyze and manipulate digital or discrete data. The FFT takes the operation count for discrete Fourier transform from \( O(N^2) \) to \( O(NlogN) \).

1977: Integer Relation Detection

Helaman Ferguson and Rodney Forcade of Brigham Young University advance an integer relation detection algorithm.

Some recently discovered integer relation detection algorithms have become a centerpiece of the emerging discipline of “experimental mathematics” — the use of modern computer technology as an exploratory tool in mathematical research.

1987: Fast Multipole Method

Leslie Greengard and Vladimir Rokhlin of Yale University invent the fast multipole algorithm.

The Fast Multipole Algorithm was developed originally to calculate gravitational and electrostatic potentials. The method utilizes techniques to quickly compute and combine the pair-wise approximation in \( O(N) \) operations.

• The Best of the 20th Century: Editors Name Top 10 Algorithms, By Barry A. Cipra, a mathematician and writer based in Northfield, Minnesota.
• The Top10 Algorithms From The 20th Century, Alex Townsend, Cornell University

Problem

189. Rotate Array

Follow up

• Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
• Could you do it in-place with O(1) extra space?

Java

Using Reverse

© Approach 4: Using Reverse

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

class Solution {
    public void rotate(int[] nums, int k) {
        final int N = nums.length;
        if (k >= N)
            k = k % N;
        reverse(nums, 0, N - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, N - 1);
    }

    private void reverse(int[] nums, int start, int end) {
        int temp;
        for (int i = 0; i < (end - start + 1) / 2; i++) {
            temp = nums[start + i];
            nums[start + i] = nums[end - i];
            nums[end - i] = temp;
        }
    }
}

Submission Detail

• 35 / 35 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for Rotate Array.
• Memory Usage: 39.4 MB, less than 97.56% of Java online submissions for Rotate Array.

brute force

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

class Solution {
    public void rotate(int[] nums, int k) {
        int temp;
        final int N = nums.length;
        if (k >= N)
            k = k % N;
        for (; k > 0; k--) {
            temp = nums[N - 1];
            for (int i = N - 1; i > 0; i--) {
                nums[i] = nums[i - 1];
            }
            nums[0] = temp;
        }
    }
}

Submission Detail

• 35 / 35 test cases passed.
• Runtime: 183 ms, faster than 22.49% of Java online submissions for Rotate Array.
• Memory Usage: 39.4 MB, less than 96.24% of Java online submissions for Rotate Array.

© Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne

Types of analyses

• Best case - Lower bound on cost.
• Worst case - Upper bound on cost.
• Average case - “Expected” cost.

Order-of-growth classifications

notation

Tilde notation

• Estimate running time (or memory) as a function of input size N
• Ignore lower order terms

1.4 Analysis of Algorithms

Stop Translating in Your Head.
Learn to Think in English.

To be honest, it is an easy but time taking process. Although I’m not a native speaker but still I know it is pretty difficult in the beginning when we try to think in English.

Think in single words

When

When your mind is clear and you’re not busy, one to two times a day.

How

If you’re just starting to learn English, don’t worry—it’s never too early to start thinking in English. You can begin as soon as you know even a small number of vocabulary words.

Look around you. What do you see? In your head, try to name each object in your surroundings.

Charles Thomas tells his students to name the things that they see around them, wherever they are.

“As you continue with this, it becomes more of a habit, so things are going to pop up into your head – computer, telephone, chair, desk. Whatever it is…wherever you are.”

Start with nouns and then add in verbs, he suggests.

He says you can also do this at home when you wake up and before you go to sleep.

“I’ve had students tell me that they label everything in their room or their apartments so that these English words, kind of, stick in their heads.”

Narrate your day, Describe your day

When

When your mind is clear and you’re not busy, one to two times a day.

How

A narrator is someone who tells or reads the story. In books, the narrator is the part without dialogue, which describes what’s happening. Many movies—especially documentaries—use narrators to explain certain parts. Now you get to pretend to be the narrator in your life, as if your life were a movie!

Your daily life narration might sound something like this: “It’s morning. She wakes up and rubs her eyes, preparing to face the day. She yawns as she makes herself a cup of coffee, and wonders what she should wear today.”

Thomas asks his beginning-level students to describe their day using the simple present verb form. So, they would think to themselves things like, “I put on my shirt” and “He drives the bus.”

For example, you might tell yourself, “When I leave the house, I’m going to get an iced coffee. Then, I’ll take the train to class. I’m studying with Paola today. She said she booked a study room at the library for 2 p.m.”

Make up conversations, Talk to yourself in English

This is a great way to practice what you might say in a real conversation.

When

When you’re alone and not busy, once a day.

How

Of course, when you speak to other people you don’t just tell them about your day. Conversations come in many different topics, so you’ll want to practice conversations as well.

For example, if you’re planning to go to a restaurant soon you can practice a conversation with the waiter. Think of both the waiter’s parts and yours. Your conversation might look something like this:

Waiter: “Hello, and welcome to our restaurant. Do you know what you’ll be ordering?”

You: “I’m not sure yet. What do you recommend?”

Waiter: “If you like seafood, our fish of the day is fantastic.”

You: “Great, I’ll have that, then.”

You can try the conversation in different ways, and seeing how differently it turns out each time.

Get creative

When

Every time you don’t know how to say something in English.

How

So you’re sitting in your car and practicing your English. That’s great! But what do you do when you can’t think of how to say a word? Instead of interrupting a conversation to pull out a dictionary app, it’s time to get creative.

For example, if you’re trying to explain to someone that you lost your key, but can’t remember the word “key,” you can tell them instead that “I can’t open my door because it’s locked,” or “I can’t get into my house, I lost the thing you use to unlock the door.”

Both sentences don’t use the word “key,” but they’re both clear enough to be understood.

Build your vocabulary

When

Every time you think in English.

How

You know that word you couldn’t remember earlier? (The words you don’t know, which cause you to get creative in #4.) As soon as you can, write down the “definition” in English or the word in your native language. Carry around a little book or use a note app on your phone. Every time you can’t think of a word (or don’t know a word) in English, write it down. At the end of the day, look up these words in English and write them down. This will help you fill in the gaps in your vocabulary.

Now that you have a long list of new words, what can you do with them? The first step is to use them in conversations (and your thoughts). A good way to do this is by grouping the words into chunks. Choose a group of around five words every morning, and use them throughout the day. This will help you remember them in the long run.

Something else you can do with your growing vocabulary list is move them to the digital world. Wordnik is a website where you can look up a word and see real examples of it being used. You can also make a list of words here. Add your new words and learn how to use them. As you internalize these new words you can move from your “vocabulary” list to a “learned words” list.

The Dictionary website (and apps) also lets you add words to a list of favorites, as does the Vocabulary website. Use these websites and lists!

Use an English to English dictionary, Don’t use a bilingual dictionary

When

Every time you look up a word.

How

When you feel more comfortable thinking in English, make sure to do this in your daily life whenever possible. This includes looking up words in an English to English dictionary (with definitions in English). The less you translate, the easier it will become to just think and speak in English.

Think in sentences, Learn vocabulary in phrases, not single words

Our brains are pattern-matching machines that remember things put into context. If I can’t come up with any context examples, I check out Cambridge Advanced Learner’s Dictionary or google it.

For example, if you are sitting in a park, you can tell yourself things like, “It’s such a beautiful day” and “People are playing sports with their friends.”

Once this becomes easy, you can move on to more difficult sentences.

Hinshaw sometimes uses this exercise to think about what he wants to say to people in Spanish.

“I definitely try to say these sentences in my head or try to put the words together without thinking too much about if it’s absolutely correct.”

Describe unknown words

Another exercise that both Thomas and Hinshaw suggest is describing in your mind objects you don’t know the words for.

An example would be if you couldn’t think of the word “garage,” Thomas says.

“If you’re looking at your house and you see your garage, but you can’t think of the name in English, you can say, ‘The place inside where I put my car.’ Or you can say, ‘It’s next to my house. I keep things there.’”

He says you can also use shorter phrases, such as “It’s similar to…” or “It’s the opposite of…”

Hinshaw says doing this can help learners of any language. As a Spanish learner, he does it himself.

Take notes

Hinshaw suggests writing down just five to 10 new words and phrases each day.

Keeping a notebook, he says, helps you remember the situation that you needed that word or phrase for. This makes it easy to recall when you are in such a situation again.

Practice it daily

Thomas says do a little every day.

“So when you’re doing it every day, over and over again, little by little, that’s the key. Because, when you make things a habit, then it just pops up into your mind without thinking and then, before you know it, really, you’re thinking in English.”

Get an English-speaking friend or partner

Travel

• Do You Think in English? Here’s Why You Should, Plus 6 Steps That Show Exactly How to Start
• Train Your Brain to Think in English
• How can I start thinking in English in my mind?
• Stop Translating in Your Head & Learn to Think in English
• 6 Ways to Think in English
• Learn How to Think in English

© Inspiring quotes for English learners

These inspiring quotes will help you stay motivated to improve your English every day. It’s easy to get discouraged after a bad grade on a test or a particularly difficult lesson. It is hard to learn a new language, and more importantly, it takes time, effort, and practice. But even when the task seems hard, it’s never impossible, as these inspiring quotes will tell you. So change tactics, try something new, and keep on learning English!

An investment in education pays the best interest. — Benjamin Franklin

Anyone who stops learning is old, whether at twenty or eighty. — Henry Ford

Education costs money, but then so does ignorance. — Sir Claus Moser

Education is not preparation for life. Education is life itself. — John Dewey

Get over the idea that only children should spend their time studying. Be a student as long as you still have something to learn, and this will mean all your life. — Henry Doherty

I am always doing that which I cannot do in order that I may learn how to do it. — Pablo Picasso

I am always ready to learn although I do not always like being taught. — Winston Churchill

I hope that in this year to come, you make mistakes. Because if you are making mistakes, then you are making new things, trying new things, learning, living, pushing yourself, changing yourself, changing your world. — Neil Gaiman

I learned the value of hard work by working hard. — Margaret Mead

If the goal you’ve set for yourself has a 100 percent chance of success, then frankly you aren’t aiming high enough. — Benny Lewis

If you hold a cat by the tail you learn things you cannot learn any other way. — Mark Twain

If you’re determined to learn, no one can stop you. — Zig Ziglar

It is good to have an end to journey toward, but it is the journey that matters in the end. — Ernest Hemingway

Knowledge is of no value unless you put it into practice. — Anton Chekhov

Live as if you were to die tomorrow. Learn as if you were to live forever. — Mahatma Ghandi

Never discourage anyone who continually makes progress, no matter how slow. — Plato

Self education is the only kind of education there is. — Isaac Asimov

The noblest pleasure is the joy of understanding. — Leonardo da Vinci

Theory is knowledge that doesn’t work. Practice is when everything works and you don’t know why. — Herman Hesse

There are no foreign lands. It is the traveller only who is foreign. — Robert Louis Stevenson

There are no secrets to success. It is the result of preparation, hard work, and learning from failure. — Colin Powell

You can be discouraged by failure, or you can learn from it. So go ahead and make mistakes, make all you can. Because, remember that’s where you’ll find success - on the far side of failure. — Thomas Watson

You can get help from teachers, but you’re going to have to learn a lot by yourself, sitting alone in a room. — Dr. Seuss

You don’t learn to walk by following rules. You learn by doing, and by falling over. — Richard Branson

You’ll never know everything about anything. — Julia Child

Start to Freelance

• Upwork
• Fiverr

Coding Contests

• Topcoder
• HackerEarth
• Coderbyte
• Project Euler
• CodeChef
• Codeforces
• Sphere Online Judge (SPOJ)
• Google Code Jam
• CodingBat
• Codility
• HackerRank
• InterviewBit

Record and Sell Online Courses

• Udemy
• BitDegree
• Udacity
• Skillshare

YouTube Channel

Start a Podcast

Sell an Ebook

• Amazon Kindle Direct Publishing

Start to Write

• Medium

• Side Gigs That Will Make You Money as a Programmer in 2020 - An unbiased look at revenue streams every programmer can use to boost their income
• How to Make Extra Money as a Programmer - There are plenty of opportunities to expand your income beyond your day job
• 8 Side Income Ideas For Programmers

by William Shakespeare

That time of year thou mayst in me behold,
When yellow leaves, or none, or few, do hang
Upon those boughs which shake against the cold,
Bare ruined choirs, where late the sweet birds sang;
In me thou seest the twilight of such day
As after sunset fadeth in the west,
Which by and by black night doth take away,
Death’s second self that seals up all in rest;
In me thou seest the glowing of such fire
That on the ashes of his youth doth lie,
As the deathbed whereon it must expire,
Consum’d with that which it was nourish’d by;
This thou perceiv’st, which makes thy love more strong,
To love that well, which thou must leave ere long.

• Sonnet 73
• Sonnet 73: That time of year thou mayst in me behold

Beats me! Just post solution of other guy.

Problem

15. 3Sum

Java

two pointers

© LeetCode – 3Sum - two pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);

        ArrayList<List<Integer>> result = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            int j = i + 1;
            int k = nums.length - 1;

            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            while (j < k) {
                if (k < nums.length - 1 && nums[k] == nums[k + 1]) {
                    k--;
                    continue;
                }

                if (nums[i] + nums[j] + nums[k] > 0) {
                    k--;
                } else if (nums[i] + nums[j] + nums[k] < 0) {
                    j++;
                } else {
                    ArrayList<Integer> l = new ArrayList<>();
                    l.add(nums[i]);
                    l.add(nums[j]);
                    l.add(nums[k]);
                    result.add(l);
                    j++;
                    k--;
                }
            }
        }

        return result;
    }
}

Submission Detail

• 318 / 318 test cases passed.
• Runtime: 21 ms, faster than 65.13% of Java online submissions for 3Sum.
• Memory Usage: 43.1 MB, less than 88.54% of Java online submissions for 3Sum.

Quadratic algorithm

© 3SUM - Quadratic algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        final int N = nums.length;
        Arrays.sort(nums);
        Set<List<Integer>> set = new HashSet<List<Integer>>();
        int start, end;
        int a, b, c;
        for (int i = 0; i < N - 1; i++) {
            a = nums[i];
            start = i + 1;
            end = N - 1;
            while (start < end) {
                b = nums[start];
                c = nums[end];
                if (a + b + c == 0) {
                    set.add(new ArrayList<>(Arrays.asList(a, b, c)));
                    start = start + 1;
                    end = end - 1;
                } else if (a + b + c > 0) {
                    end = end - 1;
                } else {
                    start = start + 1;
                }
            }
        }
        return new ArrayList<>(set);
    }
}

Submission Detail

• 318 / 318 test cases passed.
• Runtime: 230 ms, faster than 27.64% of Java online submissions for 3Sum.
• Memory Usage: 43.5 MB, less than 64.19% of Java online submissions for 3Sum.

concise solution

© Java clean solution (15 lines) https://leetcode.com/problems/3sum/discuss/865345/Java-clean-solution-(15-lines)

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

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        HashSet<List<Integer>> res = new HashSet<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            int target = -1 * nums[i];
            HashSet<Integer> set = new HashSet<>();
            for (int j = i + 1; j < nums.length; j++) {
                if (set.contains(target - nums[j]))
                    res.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], target - nums[j])));
                set.add(nums[j]);
            }
        }
        return new ArrayList<>(res);
    }
}

Submission Detail

• 318 / 318 test cases passed.
• Runtime: 768 ms, faster than 6.51% of Java online submissions for 3Sum.
• Memory Usage: 43.4 MB, less than 73.80% of Java online submissions for 3Sum.

ref

• 3SUM

For almost a decade, scientists chased the source of a deadly new virus through China’s tallest mountains and most isolated caverns.

They finally found it here: in the bats of Shitou Cave. The virus in question was a coronavirus that caused an epidemic of severe acute respiratory syndrome, or SARS, in 2003.

Coronaviruses are a group of viruses covered in little protein spikes that look like a crown— or “corona” in Latin. There are hundreds of known coronaviruses. Seven of them infect humans, and can cause disease. The coronavirus SARS-CoV causes SARS, MERS-CoV causes MERS, and SARS-CoV-2 causes the disease COVID-19.

Of the seven human coronaviruses, four cause colds, mild, highly contagious infections of the nose and throat. Two infect the lungs, and cause much more severe illnesses. The seventh, which causes COVID-19, has features of each: it spreads easily, but can severely impact the lungs.

When an infected person coughs, droplets containing the virus spray out. The virus can infect a new person when the droplets enter their nose or mouth. Coronaviruses transmit best in enclosed spaces, where people are close together. Cold weather keeps their delicate casing from drying out, enabling the virus to survive for longer between hosts, while UV exposure from sunlight may damage it. These seasonal variations matter more for established viruses. But because no one is yet immune to a new virus, it has so many potential hosts that it doesn’t need ideal conditions to spread.

In the body, the protein spikes embed in the host’s cells and fuse with them — enabling the virus to hijack the host cell’s machinery to replicate its own genes.

Coronaviruses store their genes on RNA. All viruses are either RNA viruses or DNA viruses. RNA viruses tend to be smaller, with fewer genes, meaning they infect many hosts and replicate quickly in those hosts. In general, RNA viruses don’t have a proofreading mechanism, whereas DNA viruses do. So when an RNA virus replicates, it’s much more likely to have mistakes called mutations.

Many of these mutations are useless or even harmful. But some make the virus better suited for certain environments — like a new host species. Epidemics often occur when a virus jumps from animals to humans. This is true of the RNA viruses that caused the Ebola, Zika, and SARS epidemics, and the COVID-19 pandemic. Once in humans, the virus still mutates — usually not enough to create a new virus, but enough to create variations, or strains, of the original one.

Coronaviruses have a few key differences from most RNA viruses. They’re some of the largest, meaning they have the most genes. That creates more opportunity for harmful mutations. To counteract this risk, coronaviruses have a unique feature: an enzyme that checks for replication errors and corrects mistakes. This makes coronaviruses much more stable, with a slower mutation rate, than other RNA viruses.

While this may sound formidable, the slow mutation rate is actually a promising sign when it comes to disarming them. After an infection, our immune systems can recognize germs and destroy them more quickly if they infect us again so they don’t make us sick. But mutations can make a virus less recognizable to our immune systems — and therefore more difficult to fight off. They can also make antiviral drugs and vaccines less effective, because they’re tailored very specifically to a virus. That’s why we need a new flu vaccine every year — the influenza virus mutates so quickly that new strains pop up constantly. The slower mutation rate of coronaviruses means our immune systems, drugs, and vaccines might be able to recognize them for longer after infection, and therefore protect us better.

Still, we don’t know how long our bodies remain immune to different coronaviruses. There’s never been an approved treatment or vaccine for a coronavirus. We haven’t focused on treating the ones that cause colds, and though scientists began developing treatments for SARS and MERS, the epidemics ended before those treatments completed clinical trials.

As we continue to encroach on other animals’ habitats, some scientists say a new coronavirus jumping to humans is inevitable — but if we investigate these unknowns, it doesn’t have to be devastating.

The computation of the modular multiplicative inverse is an essential step in the derivation of key-pairs in the RSA public-key encryption method. A benefit for the computer implementation of these applications is that there exists a very fast algorithm (the extended Euclidean algorithm) that can be used for the calculation of modular multiplicative inverses.

Extended Euclidean algorithm

Bézout’s identity — Let a and b be integers with greatest common divisor d. Then, there exist integers x and y such that ax + by = d. More generally, the integers of the form ax + by are exactly the multiples of d.

The integers x and y are called Bézout coefficients for (a, b); they are not unique. A pair of Bézout coefficients can be computed by the extended Euclidean algorithm.

\( m’m + n’n = gcd(m, n) \)

\(
\begin{align*}
\begin{cases} \text{if }m = 0, \text{we simply take } m’=0 \text{ and } n’=1 \text{ as } gcd(0, n)=n \\
\text{Otherwise }m \neq 0, \text{we let }r=n \bmod m=n-\lfloor \frac{n}{m} \rfloor m
\end{cases}
\end{align*}
\)

\( \overline{r}r + \overline{m}m = gcd(r,m) \)

\( \text{ as } gcd(m, n) = gcd(r, m) \)
\( \overline{r}(n-\lfloor \frac{n}{m} \rfloor m) + \overline{m}m = m’m + n’n \implies \)
\( (\overline{m}-\lfloor \frac{n}{m} \rfloor \overline{r})m + \overline{r}n = m’m + n’n \implies \)

\(
\begin{align*}
\begin{cases} m’ = \overline{m}-\lfloor \frac{n}{m} \rfloor \overline{r} \\
n’ = \overline{r}
\end{cases}
\end{align*}
\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public class ExtendedEuclid {
    public static void main(String[] args) {
        int m = 12, n = 18;
        EEResult re = extendedEuclid(m, n);
        System.out.printf("%d*%d + %d*%d = %d", re.a, m, re.b, n, re.d);
    }

    public static EEResult extendedEuclid(int m, int n) {
        EEResult re = new EEResult();
        if (m==0) {
            re.d = n;
            re.a = 0;
            re.b = 1;
            return re;
        }
        re = extendedEuclid(n%m, m);
        int d = re.d;
        int a = re.b - (n/m)*re.a;
        int b = re.a;
        re.d = d;
        re.a = a;
        re.b = b;
        return re;
    }

    static class EEResult {
        int d;
        int a;
        int b;
    }
}

Modular multiplicative inverse

Finding modular multiplicative inverses also has practical applications in the field of cryptography, i.e. public-key cryptography and the RSA Algorithm.

\( \displaystyle ax\equiv b{\pmod {m}} \)

\( \displaystyle x\equiv a^{-1}{\pmod {m}} \)

\(
\begin{align*}
\begin{cases} d_1 \equiv 35^{-1}{\pmod {3}} = 2 \\
d_2 \equiv 21^{-1}{\pmod {5}} = 1 \\
d_3 \equiv 15^{-1}{\pmod {7}} = 1
\end{cases}
\end{align*}
\)

1
2
3
4
5

import java.math.BigInteger;

BigInteger.valueOf(35).modInverse(BigInteger.valueOf(3));
BigInteger.valueOf(21).modInverse(BigInteger.valueOf(5));
BigInteger.valueOf(15).modInverse(BigInteger.valueOf(7));