# Notes - Imperative Programming HT23, Misc

> Source: https://ollybritton.com/notes/uni/prelims/ht23/ip/notes/misc/ · Updated: 2024-07-07 · Tags: uni, notes

- [Course - Imperative Programming I and II HT23](https://ollybritton.com/notes/uni/prelims/ht23/ip/)

### Flashcards
Give an iterative algorithm for fast exponentiation along with its invariants.::
```scala
def fastExp(x, n):
	if n == 0:
		return 1
	currX = x
	currN = n
	y = 1
	while currN > 0:
		if currN 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
```

@Define a loop variant.::
A variable which decreases at each iteration of the loop.

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt