• Home
  • About Us
    • About Us
    • Locations
    • Staff
    • S²TEM Family
  • We Offer
    • Continuing Education Courses
    • Instructional Classroom Support
    • Instructional Coaching
    • Remote Learning Support
    • STEM School Certification Planning and Preparation
    • Strategic Leadership Planning and Support
  • Resources
    • Digital Breakouts
    • Newsletter
    • Computational Thinking Lessons & Tools >
      • What is Computational Thinking?
      • Math Lessons
      • Science Lessons
      • Tools
    • Disciplinary Literacy Strategies and Lessons >
      • Math Lessons
      • Science Lessons
      • Self-Paced Learning Modules
      • Strategy Warehouse
      • Training Guides
    • STEM Lessons
    • Standard Support System (S3) >
      • Biology Lessons
      • Elementary Algebra Lessons
      • K-8 Mathematics Lessons
      • K-8 Science Lessons
      • Physical Science Lessons
    • Building a STEM School
    • STEM Framework
    • STEM Opportunity Database
    • Profile of SC Graduate
  • Grants
  • STEM Education Month
  • Donate
S²TEM Centers SC
  • Home
  • About Us
    • About Us
    • Locations
    • Staff
    • S²TEM Family
  • We Offer
    • Continuing Education Courses
    • Instructional Classroom Support
    • Instructional Coaching
    • Remote Learning Support
    • STEM School Certification Planning and Preparation
    • Strategic Leadership Planning and Support
  • Resources
    • Digital Breakouts
    • Newsletter
    • Computational Thinking Lessons & Tools >
      • What is Computational Thinking?
      • Math Lessons
      • Science Lessons
      • Tools
    • Disciplinary Literacy Strategies and Lessons >
      • Math Lessons
      • Science Lessons
      • Self-Paced Learning Modules
      • Strategy Warehouse
      • Training Guides
    • STEM Lessons
    • Standard Support System (S3) >
      • Biology Lessons
      • Elementary Algebra Lessons
      • K-8 Mathematics Lessons
      • K-8 Science Lessons
      • Physical Science Lessons
    • Building a STEM School
    • STEM Framework
    • STEM Opportunity Database
    • Profile of SC Graduate
  • Grants
  • STEM Education Month
  • Donate

Creating Better Algorithms

6/6/2019

0 Comments

 
Two mathematicians have just created the most efficient algorithm for multiplication of very large numbers, as reported in an article in the April 2019 Quanta magazine.  The two, Joris van der Hoeven of the French National Center for Scientific Research and David Harvey of Australia's University of New South Wales created an algorithm that beat the previous record-holder Martin Fürer's algorithm created in 2007.  

In third or fourth grade all of us were taught that the way to multiply numbers of more than a single digit was to stack the numbers on top of one another and then multiply the digits in the ones column, the tens column, the hundreds column, and then do all of the adding to get the answer.  

The stacking or carry over method is not unique to the U.S. classroom.  It has been standard across civilizations and ages.  Babylonian school children of four thousand years ago would feel right at home in an American classroom when the kids are being taught the carry over method.  It is also quite efficient when used to multiply classroom worksheet kinds of problems:  one digit times two digits, two digits times two digits.  A two digit times two digit problem requires four multiplications; a three digit times three digits requires nine.  

However, once the problems become more practical, stacking and multiplying each digit in the top row by each in the bottom becomes quite onerous when the numbers to be multiplied have 100 digits, there will be 10,000 multiplications!

In science and engineering big numbers are everywhere.  The mathematical constants such as the speed of light are both important since the speed of light "allows you to describe all kinds of phenomena," according to Joris van der Hoeven.  The stack and multiply method, even when executed by fast modern computers encounters a speed bump when multiplying "millions or billions of digits" as when computers are asked to "accurately calculate pi or as part of the worldwide search for primes..."

To multiply one 1-billion digit number by another requires 1 billion squared multiplications which would take even a modern computer 30 years.  

Mathematicians began searching for a better way to do this kind of multiplications in the 1960s.  The better way would be an algorithm, a procedure to accomplish a specific task; that is, "to solve a general, well-specified problem." (Skiena, 2008)

The well-defined problem, according to David Harvey the other co-author of the new algorithm, is to "turn some of the multiplications into additions, and the idea is additions will be faster for computers."  

The first improved algorithm was created in 1971 but its authors Arnold Schönhage and Volker Strassen also "conjectured that there should be an even faster algorithm than the one they found." You can read about this algorithm here."

The prediction came true when Martin Fürer, a Penn State mathematician produced a faster one in 2007. You can read more about this algorithm here. 
 
The Quanta article includes an example of an algorithm that was created by Anatoly Karatsuba, a student of Andrey Kologorov and spent a week trying to prove his teacher wrong. The Karatsuba algorithm betters the n^2 step limit proposed by his teacher with n^1.58.

Here it is a 2-digit by 2-digit problem solved with the Karatsuba algorithm.
25
63

Step A. Break the numbers up:
2  5
6  3
 
Step B. Multiply the tens:
2 x 6 = 12
 
Step C. Multiply the ones:
5 x 3= 15
 
Step D. Add the digits of the numbers to be multiplied
2 + 5 = 7
6 + 3 = 9
 
Step E. Multiply those sums:
7 x 9 = 63
 
Step F. Subtract Step B and Step C from Step E.
 
                         63
  1. -             15
  2. -             12
                   36
Step G. Assemble the numbers
12
  36
    15
1576
 
Karatsuba has replaced multiplication that requires n^2 steps with addition which only requires 2n steps. When used with two 1024-digit numbers, Karatsuba requires 2^10 multiplications while the classical algorithm requires (2^10)^2 steps.

As Martin Furer is quoted in the Quanta article “With addition, you do it a year earlier in school because it’s much easier, you can do it in linear time, almost as fast as reading the numbers from right to left.”

“The algorithm design space is surprisingly rich.” (Stanford Algorithms)

There are other ways to multiply beyond what we learned in third grade.

For examples, visit this link.
​
What’s your alternative algorithm?
 
Resources:
Hartnett, Kevin (2019). “Mathematicians Discover the Perfect Way to Multiply,” Quanta Magazine, April 11, 2019.
 
Skiena, Steven S. (2008). The Algorithm Design Manual. Springer-Verlag London Limited.


0 Comments

    Dr. John HOlton

    Dr. John Holton joined the S²TEM Centers SC in July of 2013, as a research associate with an emphasis on the STEM literature including state and local STEM plans from around the nation.

    Archives

    April 2020
    February 2020
    January 2020
    November 2019
    October 2019
    September 2019
    August 2019
    June 2019
    May 2019
    April 2019
    January 2019
    December 2018

    Categories

    All
    1919
    3-D Printing
    AAS
    A. B. Frank
    Addition Vs. Multiplication
    Additive Manufacturing
    Albert Einstein
    Algorithm
    A Mathematical Theory Of Communication
    Anatoly
    Andrey
    Anode
    Anopheles
    Antigen Switching
    Anti-vaccine Advocates
    Antoine Lavoisier
    Apollo
    Arnold
    Associate Degree
    Atomic Number
    Atomic Weight
    Audion Tube
    Australia
    B And T Cells
    Bell Laboratory
    Bell Telephone Company
    Bill Gates
    Black Hole
    Blood Test
    Brain
    Burlington House
    Business And Industry
    Cancer Research
    Captain Cook
    Carbohydrates
    Cathode
    Chicken Pox
    Cholera
    Classical Algorithm For Multiplication
    Claude Shannon
    Columbia
    Committee Of Ten
    Community
    Concept Map
    Conservation Of Matter
    Coordinate System
    Cough
    COVID-19
    Critical Comparator
    Daniel Kahnemann
    David
    Deer
    Dendritic Cells
    Dimitri Mendeleev
    Diploma
    Dogs
    Double-blind
    Douglas Brinkley
    Eagle
    Ebola
    Ecology
    Ecosystem
    Ecosystems
    Edvard Moser
    Edwin Aldrin
    Effectiveness Of Measles Vaccine
    Electromagnetic Wave
    Electro-mechanical Repeater
    Element
    Elizabeth Holmes
    E=mc^2
    Emerging Infectious Diseases
    End-to-end Solutions
    Energy-mass
    Entrorhinal Cortex
    Environment
    Erythrocyte
    Experiment
    Explorer 1
    Extinction
    Ferrets
    Fever
    Frank B. Jewett
    Fraud
    Fungi
    Fungus Root
    Fürer
    Gates Foundation
    Gemini
    General Theory Of Relativity
    George Schultz
    Goals
    Gondwana
    Gravity
    Gravity Waves
    Green Plants
    Grid Cells
    Harvey
    Henry Kissinger
    Hiding From The Immune System
    High School
    Hippocampus
    Host
    Host Cell Wall
    Hyades Star Cluster
    IBM
    Imagination
    Immune System
    Influenza
    Integration
    Internal Representation
    International Geophysical Year (IGY)
    Isaac Newton
    Isomalt
    James Clerk Maxwell
    James Mattis
    James Webb
    John Dalton
    John F. Kennedy
    John O'Keefe
    Karatsuba
    Kiwi
    Kologorov
    Landmark
    Large Numbers
    Lee DeForest
    Leprosy
    Liver Cells
    Loading Coils
    Lyndon B. Johnson
    Macrophages
    Malaria
    Maori
    Maps
    Marie-Anne Lavoisier
    Martin
    Martin Gelber
    Mathematics
    May 26 1919
    May-Britt Moser
    Measles
    Measles Vaccine
    Measles Virus
    Mercury
    MERS
    Michael Collins
    Microfluidics
    Moa
    Moon Landing
    Mother Trees
    Mycorrhiza
    NASA
    Neil Armstrong
    Neuroscience
    New York City
    New Zealand
    New Zealand Settlement
    Nitrates
    Nobel Prize For Physiology Or Medicine
    Non-Euclidian Geometry
    Oliver Wheatstone
    Partnerships
    Periodic Table Of The Elements
    PfErythrocyte Membrane Protein
    Phosphates
    Place Cells
    Plasmodium Falciparum
    Protein
    P-TECH
    Rabbits
    Rash
    Rats
    Red Blood Cell
    Red Sore Eyes
    Redstone Rocket
    Richard Feynman
    Richard Powers
    Robert Millikan
    Rohit Bhargava
    Royal Society Of Chemistry
    Runny Nose
    Russian Chemical Society
    Safeway
    SARS
    SARS-CoV-2
    Saturn V
    Scaffolding
    Schistosomiasis
    Schönhage
    Science
    Scientific Constants
    Scope And Sequence
    Shape Shifter
    Sheep
    Sir Arthur Eddington
    Sir Joseph Banks
    Smallpox
    Social Media
    Soviet Union
    Space
    Space-time
    Special Relativity
    Speed Of Light
    Sputnik
    STEM
    Stoats
    Strasen
    Surface Protein
    Suzanne Simard
    Synapse
    System 1
    System 2
    Technology
    The Overstory
    Theranos
    The Royal Astronomical Society
    The Royal Society Of London
    The University Of British Columbia
    Third Grade
    Thomas A. Edison
    Total Solar Eclipse
    Trial And Error
    Tuberculosis
    Typhoid
    Vaccine
    Van Der Hoeven
    Vanguard
    Virus
    Volker
    Walgreens
    Weasels
    Websites
    Werner Von Braun
    West Nile Fever
    Wood Wide Web
    "you Are The Easiest One To Fool"
    Yuri Gagarin
    Zika
    Zoonosis
    Zoonotic

    RSS Feed

#SCSTEMCenters

QUICK LINKS
We Offer
About Us
Donate
Locations
RESOURCES
STEM Lessons
Resource Library
Building a STEM School
Newsletter
CONNECT
Contact Us
Newsletter
Twitter
Facebook
Pinterest
Vertical Divider
S²TEM Centers SC is an innovation partnership managed by South Carolina’s Coalition for Mathematics & Science at Clemson University.
Picture
Picture

Copyright © S²TEM Centers SC 2019
  • Home
  • About Us
    • About Us
    • Locations
    • Staff
    • S²TEM Family
  • We Offer
    • Continuing Education Courses
    • Instructional Classroom Support
    • Instructional Coaching
    • Remote Learning Support
    • STEM School Certification Planning and Preparation
    • Strategic Leadership Planning and Support
  • Resources
    • Digital Breakouts
    • Newsletter
    • Computational Thinking Lessons & Tools >
      • What is Computational Thinking?
      • Math Lessons
      • Science Lessons
      • Tools
    • Disciplinary Literacy Strategies and Lessons >
      • Math Lessons
      • Science Lessons
      • Self-Paced Learning Modules
      • Strategy Warehouse
      • Training Guides
    • STEM Lessons
    • Standard Support System (S3) >
      • Biology Lessons
      • Elementary Algebra Lessons
      • K-8 Mathematics Lessons
      • K-8 Science Lessons
      • Physical Science Lessons
    • Building a STEM School
    • STEM Framework
    • STEM Opportunity Database
    • Profile of SC Graduate
  • Grants
  • STEM Education Month
  • Donate