powmod homework

powmod homework

package main

import "fmt"

func simpPowMod(base, exp, mod int) int {
	var val int = 1
	for i:=0; i < exp; i++ {
		val = val * base
	}
	return val % mod
}

func betterPowMod(base, exp, mod int) int {
	var val int = 1
	for i:=0; i < exp; i++ {
		val = (val * base) % mod
	}
	return val
}

func qkPowMod(base, exp, mod int) int {
	var accum int = 1
	for ; exp > 0; exp = exp/2 {
		if exp % 2 > 0 {
			accum = (accum * base) % mod
		}
		base = (base * base) % mod
	}
	return accum
}

func main() {
	var base, exp, mod int
	fmt.Println("Base: ")
	fmt.Scanf("%d", &base)
	fmt.Println("Exponent: ")
	fmt.Scanf("%d", &exp)
	fmt.Println("Modulus: ")
	fmt.Scanf("%d", &mod)
  /*
	base = 2147483647
	exp = 2147483647
	mod = 212116501
	*/
	var total int = qkPowMod(base, exp, mod)
	fmt.Println(total)
}