[Golang] Large Positive Integer Multiplication
Problem: [1]
This comes from problem 13 in Project Euler. There are two large numbers:
3710728753390210279879799822083759024651013574025046376937677490009712648124896970078050417018260538If 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.
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 {
panic("overflow in addition")
}
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)
c = AddPositiveInt(c, tmp)
}
return
}
func PrintPositiveInt(a [MaxDigits]int) {
isLeadingZero := true
for i := MaxDigits - 1; i >= 0; i-- {
if isLeadingZero && a[i] == 0 {
continue
} else {
isLeadingZero = false
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:
[1] | Large sum - Problem 13 - Project Euler |
[2] |
[3] | Large Integer Arithmetic - Analysis of Algorithms: Lecture 20 |