Project Euler 13: Adding Very Large Integers
Peter Prevos |
436 words | 3 minutes
Share this content
Project Euler 13 asks to add one hundred numbers with fifty digits. This seems like a simple problem where it not that most computers are not designed to deal with numbers with a lot of integers. For example: 264 = 18446744073709551616. When asking R to compute this value, we get 1.844674e+19, losing most of the digits and limiting the accuracy of the results. Computers solve this problem using Arbitrary-Precision Arithmetic. Many software libraries can process long integers without losing accuracy. Euler Problem 13 requires this type of approach.
Project Euler 13 Definition
Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
Solution
The easy way to solve this problem is to use the GMP package for working with huge integers. This package uses a special number types such as Big Rational and Big Integer. The number of digits in these number types is only limited by the size of your computer's memory.
## Project Euler 13: Adding Very Large Numbers
## GMP Library
library(gmp)
numbers <- readLines("data/p013_numbers.txt")
gmp_method <- function() {
digits <- sum(as.bigz(numbers))
answer <- substr(as.character(digits),1,10)
return(answer)
}
gmp_method()Using Base-R
To find the solution to this problem using only base R, I wrote a function to add numbers using strings instead of integers. The function adds leading zeros to the smallest number to make them both the same length. The function then proceeds to add numbers in the same way we were taught in primary school.
## Base-R Solution
big.add <- function(a, b) {
## Add leading zeros to smallest number
if (nchar(a)<nchar(b))
a <- paste0(paste(rep(0, nchar(b) - nchar(a)), collapse = ""), a)
if (nchar(a)>nchar(b))
b <- paste0(paste(rep(0, nchar(a) - nchar(b)), collapse = ""), b)
solution <- vector()
remainder <- 0
for (i in nchar(b):1) {
p <- as.numeric(substr(a, i, i))
q <- as.numeric(substr(b, i, i))
r <- p + q + remainder
if (r >= 10 & i != 1) {
solution <- c(solution, r %% 10)
remainder <- (r - (r %% 10)) / 10
} else {
solution <- c(solution, r)
remainder <- 0
}
}
return(paste(rev(solution), collapse = ""))
}With this function, the problem is easy to solve. The second part of the code runs this function over the one hundred numbers provided on the Euler Problem page and calculates the answer.
base_method <- function() {
answer <- 0
for (i in numbers)
answer <- big.add(answer, i)
answer <- substr(answer, 1, 10)
return(answer)
}
base_method()This solution for managing very large numbers is reused in Project Euler 25 which asks for a Fibonacci number with 1000 decimals.
Share this content
