package main

import (
	"fmt"
	"time"
)

func main() {

	num1 := 2000000000
	num2 := 2000000000

	start := time.Now()
	a := naive(num1, num2)
	elapsed := time.Since(start)
	fmt.Printf("Product: %d, Elapsed Time: %d \n", a, elapsed)

	start = time.Now()
	a = russian(num1, num2)
	elapsed = time.Since(start)
	fmt.Printf("Product: %d, Elapsed Time: %d \n", a, elapsed)

	start = time.Now()
	a = recRussian(num1, num2)
	elapsed = time.Since(start)
	fmt.Printf("Product: %d, Elapsed Time: %d \n", a, elapsed)
}

func naive(a, b int) int {
	x := a
	y := b
	z := 0
	for x > 0 {
		x = x - 1
		z = z + y
	}
	return z
}

func russian(a, b int) int {
	x := a
	y := b
	z := 0

	for x > 0 {
		if x%2 == 1 {
			z = z + y
			x = (x - 1) / 2
		} else {
			x = x / 2
		}
		y = y * 2
	}
	return z
}

func recRussian(a, b int) int {
	if a == 0 {
		return 0
	}
	if a%2 == 0 {
		return 2 * recRussian(a/2, b)
	} else {
		return b + 2*recRussian((a-1)/2, b)
	}
}