Overview
Schoolbook Multiplication multiplies each digit of one number by each digit of the other, shifts partial products according to position, and sums them with carries.
FoundationSource checked
Schoolbook Multiplication
Multiplies numbers by forming digit-by-digit partial products and adding them by place value.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Numerical Methods
- Difficulty
- Beginner
- Family
- Integer Arithmetic
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 6
- Code example
- Ready
- Visualization
- Ready
Core Concepts
partial productplace valuecarry propagationinteger arithmetic
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n log n)
Worst
O(n^2)
Space
O(n)
When to Use
- Use it for small integers or as a simple exact multiplication baseline.
- Use it when clarity matters more than asymptotic speed.
- Use it as a base case in recursive multiplication algorithms.
When Not to Use
- Avoid it for very large integers when asymptotically faster multiplication is available.
- Avoid it when fixed-width arithmetic can overflow without wider intermediates.
- Avoid it when the representation uses limbs and carry handling is not defined.
What It Does
- Computes exact integer products
- Combines digit partial products by place value
Use Cases
- Teaching multiplication algorithms
- Small integer arithmetic
- Base case inside faster multiplication methods
Inputs
- Numbers, vectors, matrices, or functions
- Tolerance or precision settings
Outputs
- Computed numeric result
- Residual, factorization, or approximation
Pseudocode
- 1.Create an output array initialized to zero.
- 2.For each digit i of the first number:
- 3.For each digit j of the second number:
- 4.Add digit[i] * digit[j] to output position i + j.
- 5.Propagate carries across output positions.
- 6.Return the normalized product.
Canonical Example
- Input
- 23 * 14
- Output
- 322
- Explanation
- 23 * 4 = 92 and 23 * 10 = 230; adding the shifted partial products gives 322.
Implementation Notes
- Choose a base or limb size that leaves room for intermediate products and carries.
- Accumulate partial products into positions indexed by digit offsets.
- Normalize carries after accumulation or carefully during each addition.
Common Pitfalls
- Forgetting positional shifts for partial products.
- Dropping carries between digit or limb positions.
- Using intermediate types that overflow before the carry is handled.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow multiplying every digit pair and carrying positional sums on a small integer multiplication example.
Step 1 of 6: Create an output array initialized to zero.
numerical-methods-mechanismNotes
Faster integer multiplication methods often use schoolbook multiplication for small subproblems.
Sources (2)
What each reference supports for this entry.
Modern Computer Arithmetic
BookReference for Schoolbook Multiplication's arithmetic operations, modular arithmetic, multiplication, division, or number-theoretic implementation details.
Open sourceIntroduction to Algorithms (CLRS)
BookTextbook support for Schoolbook Multiplication's algorithm family, complexity framing, and standard implementation concepts.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toKaratsuba Multiplication
Numerical Methods · Core
Karatsuba multiplication reduces large products into fewer recursive subproducts.
Compare with thisRelationships
View full relationship pageAlternative toKaratsuba Multiplication
Karatsuba multiplication reduces large products into fewer recursive subproducts.
Alternative toToom-Cook Multiplication
Toom-Cook is usually chosen for larger integers where interpolation overhead pays off.
Alternative toFFT-Based Integer Multiplication
FFT-based multiplication targets very large integers by turning multiplication into convolution.
Tags
Numerical Methods