[Golang] Large Positive Integer Addition
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 add two large natural numbers in Go?
Solution:
After some googling [2], I found the tutorial [3] which shows how to perform large integer addition. 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 PositiveIntToString(a [MaxDigits]int) (result string) {
isLeadingZero := true
for i := MaxDigits - 1; i >= 0; i-- {
if isLeadingZero && a[i] == 0 {
continue
} else {
isLeadingZero = false
switch a[i] {
case 0:
result += "0"
case 1:
result += "1"
case 2:
result += "2"
case 3:
result += "3"
case 4:
result += "4"
case 5:
result += "5"
case 6:
result += "6"
case 7:
result += "7"
case 8:
result += "8"
case 9:
result += "9"
default:
panic("invalid digit in int array")
}
}
}
return
}
func main() {
a := MakePositiveInt(`37107287533902102798797998220837590246510135740250`)
b := MakePositiveInt(`46376937677490009712648124896970078050417018260538`)
c := AddPositiveInt(a, b)
fmt.Println(PositiveIntToString(a))
fmt.Println(PositiveIntToString(b))
fmt.Println(PositiveIntToString(c))
}
Tested on: Go Playground
References:
[1] | Large sum - Problem 13 - Project Euler |
[2] |
[3] | Analysis of Algorithms: Lecture 20 |