Euler project problem 1 in R - various approaches

Question

I saw this problem on social media and looked into some fast implementations. Does anyone have some input in what could even be faster?

Euler Project Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

I used 1:1e8 as a base range to get to significant differences between the methods.

# library call only needed for the furrr:future_map_dbl solution
library(furrr)
plan(multisession)

nums <- 1:1e8

t1 <- Sys.time()
sum(nums[which(nums %% 3 == 0 | nums %% 5 == 0)])

t2 <- Sys.time()
sum(sapply(nums, function(x) if (x %% 3 == 0 | x %% 5 == 0) x else 0))

t3 <- Sys.time()
sum(purrr::map_dbl(nums, ~ if (.x %% 3 == 0 | .x %% 5 == 0) .x else 0))

t4 <- Sys.time()
sum(furrr::future_map_dbl(nums, ~ if (.x %% 3 == 0 | .x %% 5 == 0) .x else 0))

t5 <- Sys.time()

times <- c(t1, t2, t3, t4, t5)
t <- times[2:5] - times[1:4]
names(t) <- c("base-r","sapply","map_dbl","future_map_dbl")
t

The times on my computer were

Time differences in secs
        base-r         sapply        map_dbl future_map_dbl
      2.745852     186.671004      80.694654      31.161530

Using the non-base R methods add some overhead which is noticable in smaller ranges, e.g. nums <- 1:1e6

Time differences in secs
        base-r         sapply        map_dbl future_map_dbl
    0.05106783     0.78388309     1.50676894     0.32907510

Did you try using Intel's MKL (like in R Open, or here https://stackoverflow.com/questions/38090206/linking-intels-math-kernel-library-mkl-to-r-on-windows)? — Santiago Capobianco, Jan 04 '23 at 04:08

Ritchie Sacramento · Accepted Answer · 2023-01-04T10:57:10.017

This isn't readily generalizable to multiples of more than two numbers but to answer the problem as written you can use the arithmetic series formula, where we calculate the sum of the series for each value minus the series of the lowest common multiple of the two values.

f <- function(x, y, range_max) {
  
  # Function to calculate arithmetic series sum
  as_sum <- function(v) {
    n <- floor(range_max / v)
    n / 2 * (v + n * v)
  }
  # Function to find lowest common multiple
    find_lcm <- function(x, y){
      gcd <- function(x, y) {
        ifelse(x %% y != 0, Recall(y, x %% y), y)
      }
      x * y / gcd(x, y)
    }
    
    lcm <- find_lcm(x, y)
    as_lcm <- as_sum(lcm) * (lcm <= 1000)
    
    sum(as_sum(c(x, y))) - as_lcm 
}

Benchmark:

nums<- 1:1e8
bench::mark(arithmetic_series_sum = f(3, 5, 1e8),
            subset_sum = sum(nums[which(nums %% 3 == 0 | nums %% 5 == 0)]))[1:9]

# A tibble: 2 × 9
  expression                 min   median `itr/sec` mem_alloc `gc/sec` n_itr  n_gc total_time
  <bch:expr>            <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl> <int> <dbl>   <bch:tm>
1 arithmetic_series_sum   13.2µs   14.5µs 65916.           0B    0     10000     0   151.71ms
2 subset_sum               4.56s    4.56s     0.219     3.7GB    0.877     1     4      4.56s

Euler project problem 1 in R - various approaches

1 Answers1