Coding Grandmaster · project 10 of 46 · premium, free for now
Powers in a flash
Write power_steps(base, exp) that returns (result, multiplications) using repeated squaring, and pow_mod(base, exp, m) that returns base ** exp % m the same way (without ever building the full power).
Learn
To compute 3^100 you do not need 99 multiplications. Square repeatedly: 3, 3², 3⁴, 3⁸ and so on, and multiply together only the squares that match the 1s in the exponent's binary form. That is about 7 + a few steps instead of 99. Doing it modulo m keeps the numbers small, which is how computers handle huge numbers in cryptography.
Your task
Write power_steps(base, exp) that returns (result, multiplications) using repeated squaring, and pow_mod(base, exp, m) that returns base ** exp % m the same way (without ever building the full power).
Stretch challenge
How many multiplications does 3 ** 1000 need with this method?
Press Run to see what your program prints.
More in this module
Keep going in Coding Grandmaster
Euclid's shortcut
Write gcd_steps(a, b) returning (gcd, steps) where steps counts the remainder steps, and lcm(a, b). Print gcd_steps(48, 18) and lcm(4, 6).
Start →8The sieve of Eratosthenes
Write primes_below(n) using a list of True/False flags (a sieve) that returns the list of primes less than n. Print how many primes there are below 100 and the last one.
Start →9Digits and casting out nines
Write digit_sum(n) using % and //, and digital_root(n) that repeats digit_sum until one digit remains. Print both for 98765.
Start →11Perfect numbers
Write divisor_sum(n) (the sum of proper divisors, found by looping d up to the square root and adding both d and n // d) and print the perfect numbers below 1000.
Start →12Counting in other bases
Write to_base(n, base) returning the digits as text, using the string "0123456789ABCDEF". Print 10 in binary and 255 in hexadecimal.
Start →Practise the idea
💡 Play Binary Bits
Switch bit values to make the decimal number shown on screen.
FAQ
Powers in a flash: common questions
I am stuck. What can I do?
Press Hint for a nudge, read the message next to each goal, and compare your code with the lesson text. If you still need it, Show answer reveals a model solution. Try to type it yourself rather than copy it.
Does my work get saved?
Your ticks and XP are saved in this browser, and in your account if you log in. The code you type is not stored on a server.
Start a conversation
Enjoying coding? Meet a teacher.
Tell us the learner's age, country and what they would like to build, and we will suggest a class. A parent or guardian can make the enquiry.
- Tell us the learner’s age or grade and goals
- We’ll suggest a suitable class or learning path
- We’ll confirm format, timing and fees with a parent or guardian
Play it, don't just read it
Write some code right now
Free games that need no sign-up. Pick one and play for five minutes.
Pick a game
- Predict the OutputRead a short Python program and choose what it prints. Then watch it run…Play
- Code BuilderThe lines of a Python program are mixed up. Tap them into the right…Play
- Bug HunterA Python program prints the wrong answer. Find the one line with the…Play
- Code JungleWrite real Python to guide Miko the monkey to every banana. 24 levels:…Play