Algorithms and Data Structures

Algorithm: A process or set of rules used for calculation or problem-solving, esp. with a computer.
Program: A series of coded instructions to control the operation of a computer or other machine. [– concise OED '91]

E.g., long multiplication

Computers typically have single instructions to multiply 32- and 64-bit* integers but what about integers much bigger than that? Long-multiplication, the usual manual method for multiplying large integers as taught in school, is an example of an algorithm. If the two integers have d1 and d2 digits respectively, the algorithm requires approximately k×d1×d2 steps to give its result, where k is a constant.

     123
   × 456
  ------
   49200   123×4 left shift 2 columns
    6150   123×5 left shift 1 column
  +  738   123×6
  ------
   56088
  ------

The HTML FORM below runs a demonstration of integer long-multiplication. Change the values, click the 'go' button and experiment:

×

There are much faster algorithms for the multiplication of big integers.


* 64-bits is equivalent to approximately 20 decimal digits.