<p><div><div><div><div data-width="100" data-show-faces="false" data-send="true" data-layout="button_count" data-height="21" data-href="https://www.r-bloggers.com/euler-problem-13-large-sum-of-1000-digits/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="http://r.prevos.net/euler-problem-13/"> The Devil is in the Data</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<p>Euler Problem 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:</p>
<p> <img title="2^{64} = 18446744073709551616 " alt="2^{64} = 18446744073709551616 " class="latex" src="http://s0.wp.com/latex.php?latex=2%5E%7B64%7D+%3D+18446744073709551616+&bg=ffffff&%23038;fg=000&%23038;s=0"></p>
<p>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 <a target="_blank" rel="nofollow" href="https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic">Arbitrary-precision Arithmetic</a>. There are many software libraries that can process long integers without loosing accuracy. Euler Problem 13 requires this type of approach.</p>
<h2>Euler Problem 13 Definition</h2>
<p>Work out the first ten digits of the <a target="_blank" rel="nofollow" href="https://projecteuler.net/problem=13">sum of the following one-hundred 50-digit numbers</a>.</p>
<h2>Solution</h2>
<p>The easy way to solve this problem is to use the <a target="_blank" rel="nofollow" href="https://cran.r-project.org/web/packages/gmp/index.html">gmp package</a> for working with very large 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 the memory.</p>
<pre>
library(gmp)
numbers &lt;- readLines(&quot;Euler/p013_numbers.txt&quot;)
digits &lt;- as.bigz(sum(as.numeric(numbers)))
answer &lt;- substr(as.character(digits),1,10)
</pre>
<p>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. This function can in principle be used for several other Euler Problems using large integers.</p>
<pre>
# Add numbers with many digits
big.add &lt;- function(a, b) {
    # Add leading zeros to smallest numer
    if (nchar(a) &lt; nchar(b)) 
        a &lt;- paste0(paste(rep(0, nchar(b)-nchar(a)), collapse=&quot;&quot;), a) 
    if (nchar(a) > nchar(b)) 
        b &lt;- paste0(paste(rep(0, nchar(a)-nchar(b)), collapse=&quot;&quot;), b)
    solution &lt;- vector()
    remainder &lt;- 0
    for (i in nchar(b):1) {
        p &lt;- as.numeric(substr(a, i, i))
        q &lt;- as.numeric(substr(b, i, i))
        r &lt;- p + q + remainder if (r >= 10 &amp; i!=1) {
            solution &lt;- c(solution, r %% 10)
            remainder &lt;- (r - (r %% 10))/10
        } else {
            solution &lt;- c(solution, r)
            remainder &lt;- 0
        }
    }
    return(paste(rev(solution), collapse=&quot;&quot;))
}
</pre>
<p>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.</p>
<pre>
numbers &lt;- readLines(&quot;Euler/p013_numbers.txt&quot;)
answer &lt;- &quot;0&quot;
for (i in numbers) {
    answer &lt;- big.add(answer, i)
}
answer &lt;- substr(answer, 1, 10)
</pre>
<h2>Multiplying Big Numbers</h2>
<p>You can expand this function to multiply a very large number with a smaller number using the Reduce function. This function adds the number a to itself, using the <em>big.add</em> function. The outcome of the addition is used in the next iteration until it has been repeated <em>b</em> times. The number b in this function needs to be a ‘low’ number because it uses a vector of the length b.</p>
<pre>
big.mult &lt;- function(a, b) {
    Reduce(big.add, rep(a, as.numeric(b)))
}
</pre>
<p><iframe height="359" width="584" allowfullscreen="true" src="http://www.youtube.com/embed/6bpLYxk9TUQ?version=3&rel=1&%23038;fs=1&%23038;autohide=2&%23038;showsearch=0&%23038;showinfo=1&%23038;iv_load_policy=1&%23038;wmode=transparent" type="text/html"></iframe></p>
<p>The post <a target="_blank" rel="nofollow" href="http://r.prevos.net/euler-problem-13/">Euler Problem 13: Large Sum of 1000 Digits</a> appeared first on <a target="_blank" rel="nofollow" href="http://r.prevos.net/">The Devil is in the Data</a>.</p>
<p>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="http://r.prevos.net/euler-problem-13/"> The Devil is in the Data</a></strong>.</div>
<hr>
<a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="https://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a title="The R Project for Statistical Computing" rel="nofollow" href="https://www.r-project.org/">R</a> news and <a title="R tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/tutorial">tutorials</a> on topics such as: <a title="Data science" rel="nofollow" href="https://www.r-bloggers.com/search/data%20science">Data science</a>, <a title="Big Data" rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data">Big Data, <a title="R jobs" rel="nofollow" href="https://www.r-users.com/">R jobs</a>, visualization (<a title="ggplot and ggplot2 tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2">ggplot2</a>, <a title="Boxplots using lattice and ggplot2 tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/boxplot">Boxplots</a>, <a title="Maps and gis" rel="nofollow" href="https://www.r-bloggers.com/search/map">maps</a>, <a title="Animation in R" rel="nofollow" href="https://www.r-bloggers.com/search/animation">animation</a>), programming (<a title="RStudio IDE for R" rel="nofollow" href="https://www.r-bloggers.com/search/RStudio">RStudio</a>, <a title="Sweave and literate programming" rel="nofollow" href="https://www.r-bloggers.com/search/sweave">Sweave</a>, <a title="LaTeX in R" rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX">LaTeX</a>, <a title="SQL and databases" rel="nofollow" href="https://www.r-bloggers.com/search/SQL">SQL</a>, <a title="Eclipse IDE for R" rel="nofollow" href="https://www.r-bloggers.com/search/eclipse">Eclipse</a>, <a title="git and github, Version Control System" rel="nofollow" href="https://www.r-bloggers.com/search/git">git</a>, <a title="Large data in R using Hadoop" rel="nofollow" href="https://www.r-bloggers.com/search/hadoop">hadoop</a>, <a title="Web Scraping of google, facebook, yahoo, twitter and more using R" rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping">Web Scraping</a>) statistics (<a title="Regressions and ANOVA analysis tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/regression">regression</a>, <a title="principal component analysis tutorial" rel="nofollow" href="https://www.r-bloggers.com/search/PCA">PCA</a>, <a title="Time series" rel="nofollow" href="https://www.r-bloggers.com/search/time+series">time series</a>, <a title="finance trading" rel="nofollow" href="https://www.r-bloggers.com/search/trading">trading</a>) and more...
<img height="1" alt="" width="1" src="http://feeds.feedburner.com/~r/RBloggers/~4/Ys9eUDgDJdE"></a></div>