-
Notifications
You must be signed in to change notification settings - Fork 0
/
AxiomVsKaratsuba10s.R
99 lines (81 loc) · 2.98 KB
/
AxiomVsKaratsuba10s.R
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
# install the required packages
install.packages("microbenchmark")
install.packages("ggplot2")
# load the packages
library(microbenchmark)
library(ggplot2)
# Define the axiom multiplication function
axiom_multiplication <- function(x, y) {
# Break down x and y into multiples of 10 and single digits
x_tens <- floor(x/10)
x_ones <- x - 10*x_tens
y_tens <- floor(y/10)
y_ones <- y - 10*y_tens
# Initialize a variable z to 0
z <- 0
# Iterate through the digits of x
for (i in 1:length(x)) {
# Iterate through the digits of y
for (j in 1:length(y)) {
# Calculate the product x[i] * y[j]
product <- x[i] * y[j]
# Add the product to the corresponding element of z
z[i+j-1] <- z[i+j-1] + product
}
}
# Return z as the final result
return(z)
}
# define the Karatsuba multiplication function
karatsuba <- function(x, y) {
if (length(x) <= 1 || length(y) <= 1) {
return(axiom_multiplication(x, y))
}
m <- max(length(x), length(y))
m2 <- floor(m/2)
xl <- x[1:m2]
xr <- x[(m2+1):m]
yl <- y[1:m2]
yr <- y[(m2+1):m]
z0 <- karatsuba(xl, yl)
z1 <- karatsuba(xl + xr, yl + yr)
z2 <- karatsuba(xr, yr)
c(z0 + (z1 - z0 - z2) * 10^m2, z2)
}
# define the inputs for the multiplication functions
x <- rnorm(100)
y <- rnorm(100)
# measure the execution time of the multiplication functions
result <- microbenchmark(axiom_multiplication(x, y), karatsuba(x, y))
# print the results
print(result)
# visualize the results using a bar chart
ggplot(result, aes(x=expr, y=time, fill=expr)) +
geom_bar(stat="identity") +
theme(legend.position = "none") +
labs(title = "Comparison of multiplication methods", x = "Method", y = "Execution time (ms)")
# visualize the results using a histogram
ggplot(result, aes(x=time, fill=expr)) +
geom_histogram(bins=50) +
theme(legend.position = "none") +
labs(title = "Comparison of multiplication methods", x = "Execution time (ms)", y = "Frequency")
# visualize the results using a plot
ggplot(result, aes(x=expr, y=time, color=expr)) +
geom_point() +
labs(title = "Comparison of multiplication methods", x = "Method", y = "Execution time (ms)")
# get a summary of the results
summary <- summary(result)
# print the summary
print(summary)
# compare the mean execution time of the two methods
if (summary[1, "mean"] < summary[2, "mean"]) {
print("The axiom multiplication method is faster on average.")
} else {
print("The Karatsuba multiplication method is faster on average.")
}
# compare the mean execution time of the two methods
if (summary[1, "mean"] < summary[2, "mean"]) {
print(paste("The axiom multiplication method is", round(summary[2, "mean"] / summary[1, "mean"], 2), "times faster than the Karatsuba method."))
} else {
print(paste("The Karatsuba multiplication method is", round(summary[1, "mean"] / summary[2, "mean"], 2), "times faster than the axiom multiplication method."))
}