[Golang] Large Positive Integer Addition


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 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.

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 {
              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