0

As a self taught programmer, I was unaware of libraries such as gmp and wrote several "Big Integer" functions myself to handle large integer arithmetic. The key idea driving my algorithms is storing my large integers of interest in an array (i.e. each index would represent a single digit of the number (e.g. 123456789 would be in the array like so: (1,2,3,4,5,6,7,8,9)). An example of big integer addition is below.

MyBigIntegerAddition <- function(x1, x2) {
    MyNum1 <- as.integer(strsplit(as.character(x1), "")[[1]])
    MyNum2 <- as.integer(strsplit(as.character(x2), "")[[1]])

    if (length(MyNum1) < length(MyNum2)) {
        while (length(MyNum1) < length(MyNum2)) {MyNum1 <- c(0L, MyNum1)}
    } else if (length(MyNum2) < length(MyNum1)) {
        while (length(MyNum2) < length(MyNum1)) {MyNum2 <- c(0L, MyNum2)}
    } 

    MyNum1 <- MyNum1 + MyNum2
    lenMyNum1 <- length(MyNum1)

    if (lenMyNum1 >= 2L) {
        for (j in lenMyNum1:2L) {
            TempB1 <- MyNum1[j] %% 10L
            TempB2 <- floor(MyNum1[j]/ 10L)
            MyNum1[j] <- TempB1
            MyNum1[j - 1L] <- MyNum1[j - 1L] + TempB2
        }
    }

    while ((MyNum1[1L] / 10L) > 1L) {
        TempB1 <- MyNum1[1L] %% 10L
        TempB2 <- floor(MyNum1[1L]/ 10L)
        MyNum1[1L] <- TempB1
        MyNum1 <- c(TempB2, MyNum1)
    }

    paste(MyNum1, collapse = "")
}

Below is a random example comparing output

MyBigIntegerAddition("103489710232857289034750289347590984710923874","2987234756    23746529875692873456927834569298347569237")
[1] "298723579113456762732981908207217182160283058493111"
>     add.bigz("103489710232857289034750289347590984710923874","298723475623746529875692873456927834569298347569237")
Big Integer ('bigz') :
[1] 298723579113456762732981908207217182160283058493111

I have provided a function that verifies my results as well.

TestStringMath <- function(n,Lim1,Lim2) {
    samp1 <- sample(Lim1:Lim2,n)
    samp2 <- sample(Lim1:Lim2,n)
    count <- 0L

    for (i in 1:n) {
        temp1 <- add.bigz(samp1[i], samp2[i])
        temp2 <- as.bigz(MyBigIntegerAddition(samp1[i], samp2[i]))
        if (!(temp1==temp2)) {
            count <- count+1L
        }
    }
    count
}

Question: How exactly does gmp's arithmetic functions work? Do they convert numbers to strings and use arrays? Do they simply invoke more memory?

Joseph Wood
  • 7,077
  • 2
  • 30
  • 65
  • 2
    The gmp C library is open source, so you could take the gmp entry point(s) used in `gmp::add.bigz` as a starting point of where to look in the gmp C library (not the gmp package). – Joshua Ulrich Oct 29 '15 at 19:24
  • 6
    [Here is a link](https://gmplib.org/manual/Algorithms.html#Algorithms) to the "Algorithms" chapter of the GMP library documentation, devoted to explaining "what goes on behind the scenes". It (and the following chapter, on how GMP represents values behind the scenes) might provide an easier path to grasping the big picture than starting right in with the C code ;). – Josh O'Brien Oct 29 '15 at 19:56
  • @JoshuaUlrich, I just found your extremely helpful [question](http://stackoverflow.com/q/19226816/4408538) & [answer](http://stackoverflow.com/a/19226817/4408538) yesterday that really gets at the heart of my question above. I probably should have been a bit more persistent in my search efforts. Anywho, thanks as usual, and cheers!! – Joseph Wood May 01 '16 at 16:54

0 Answers0