# [Golang] Large Positive Integer Multiplication

Problem: [1]

This comes from problem 13 in Project Euler. There are two large numbers:

37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538

If you use strconv.Atoi to convert the string to int, you will get panic which reports overflow. So how do we multiply two large natural numbers in Go?

Solution:

After some googling [2], I found the tutorial [3] which shows how to perform large integer multiplication. The following is Go implementation of the algorithm.

Run Code on Go Playground

```package main

import (
"fmt"
)

const MaxDigits = 100
const BASE = 10

func MakePositiveInt(s string) (n [MaxDigits]int) {
// make n zero
for i := 0; i < MaxDigits; i++ {
n[i] = 0
}

for index, digit := range s {
i := len(s) - index - 1
switch digit {
case '0':
n[i] = 0
case '1':
n[i] = 1
case '2':
n[i] = 2
case '3':
n[i] = 3
case '4':
n[i] = 4
case '5':
n[i] = 5
case '6':
n[i] = 6
case '7':
n[i] = 7
case '8':
n[i] = 8
case '9':
n[i] = 9
default:
panic("invalid digit in number string")
}
}

return
}

func AddPositiveInt(a, b [MaxDigits]int) (c [MaxDigits]int) {
var carry, sum = 0, 0

// make c zero
for i := 0; i < MaxDigits; i++ {
c[i] = 0
}

for i := 0; i < MaxDigits; i++ {
sum = a[i] + b[i] + carry

if sum >= BASE {
carry = 1
sum -= BASE
} else {
carry = 0
}

c[i] = sum
}

if carry != 0 {
}

return
}

func MultiplyOneDigit(a [MaxDigits]int, n int) (b [MaxDigits]int) {
var carry = 0

// make b zero
for i := 0; i < MaxDigits; i++ {
b[i] = 0
}

for i := 0; i < MaxDigits; i++ {
b[i] = n * a[i]

b[i] += carry

if b[i] >= BASE {
carry = b[i] / BASE
b[i] %= BASE
} else {
carry = 0
}
}

if carry != 0 {
panic("overflow in multiplication")
}

return
}

func ShiftLeft(a [MaxDigits]int, n int) [MaxDigits]int {
var i int

for i = MaxDigits - 1; i >= n; i-- {
a[i] = a[i-n]
}
for i >= 0 {
a[i] = 0
i -= 1
}

return a
}

func MultiplyPositiveInt(a, b [MaxDigits]int) (c [MaxDigits]int) {
// make c zero
for i := 0; i < MaxDigits; i++ {
c[i] = 0
}

for i := 0; i < MaxDigits; i++ {
tmp := MultiplyOneDigit(b, a[i])
tmp = ShiftLeft(tmp, i)
}

return
}

func PrintPositiveInt(a [MaxDigits]int) {
for i := MaxDigits - 1; i >= 0; i-- {
if isLeadingZero && a[i] == 0 {
continue
} else {
fmt.Print(a[i])
}
}
fmt.Println("\n")
}

func main() {
a := MakePositiveInt(`37107287533902102798797998220837590246510135740250`)
b := MakePositiveInt(`46376937677490009712648124896970078050417018260538`)
c := MultiplyPositiveInt(a, b)
PrintPositiveInt(a)
PrintPositiveInt(b)
PrintPositiveInt(c)
}
```

Tested on: Go Playground

References: