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