Tag: mathematics


16 June 2019 / Paul Hankin / programming

Computing large integer powers modulo some number is a somewhat common operation. For example, it’s used in RSA encryption. Usually, this is done using exponentiation by squaring, but this go program correctly prints the results of $n^{2^{64}}\ (\mathrm{mod}\ 115763)$ for $n$ from 1 to 20, seemingly naively:

package main

import "fmt"

func main() {
	for n := 1; n <= 20; n++ {
		result := 1
		for i := 0; i < 2^64; i++ {
			result = (result * n) % 115763
		fmt.Printf("pow(%d, pow(2, 64)) mod 115763 = %d\n", n, result)

It runs, unoptimized, in a few milliseconds on my desktop. You can run it yourself online using the go playground. Feel free to edit the code a little before running it to convince yourself it’s not just fast because the playground is caching the results or something.

How can it be that fast? Is go’s optimizing compiler that clever? It’s not, and there’s a trick in the code. Can you see it?

14 June 2019 / Paul Hankin / programming
21 May 2015 / Paul Hankin / game theory / computer science

This blog post looks at closed-hand Chinese Poker, and describes a near-optimal strategy for it which is readily implementable on a computer.