Modular Multiplication
Double and add along the bits of b, reducing every partial result, so nothing exceeds 2m.
Decision · step 2 of 9Number Theory Basics: Multiply by doubling and adding, mod 7
This bit is 1, so add the current doubling in: (0 + 6) mod 7 = 6.
What you will see
The product is built by doubling and adding, reducing each time.
Cost
| Best | O(log b) |
|---|---|
| Average | O(log b) |
| Worst | O(log b) |
| Space | O(1) |
How you work with it here
play it through, step one change at a time, run it on your own input.
Screen readers: Numbers announce their value and role; each step announces the arithmetic performed.
Reduced motion: Values crossfade; no travelling digits.
Before this
Taught by the same lesson
Number Theory Basics covers these too, in the same run.