Notes - Imperative Programming HT23, Misc

Created: July 07, 2024

Flashcards

Give an iterative algorithm for fast exponentiation along with its invariants.

 
def fastExp(x, n):
	if n == 0:
		return 1
	currX = x
	currN = n
	y = 1
	while currN > 0:
		if n even then
			currX = currX * currX
			currN = currN / 2
		else
			y = currX * y
			currX = currX * currX
			currN = (currN-1) / 2
	return y
// Invariants: result = y*currX^currN && 0 <= currN <= n
// Variant: currN
// I and currN == 0 \implies y = x^n

What is a loop variant?

A variable which decreases at each iteration of the loop.



Related posts