-
Notifications
You must be signed in to change notification settings - Fork 0
/
AxerovsFurer.R
109 lines (86 loc) · 3.66 KB
/
AxerovsFurer.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
100
101
102
103
104
105
106
107
108
109
# Define the Axero algorithm
axero <- function(x, y) {
# Convert x and y to character vectors
x_str <- as.character(x)
y_str <- as.character(y)
# Convert the character vectors to integer vectors
x_digits <- as.integer(strsplit(x_str, "")[[1]])
y_digits <- as.integer(strsplit(y_str, "")[[1]])
# Initialize result to 0
result <- 0
# Loop through each digit of x
for (i in 1:length(x_digits)) {
# Skip the calculation if the x digit is 0
if (x_digits[i] == 0) {
next
}
# Loop through each digit of y
for (j in 1:length(y_digits)) {
# Skip the calculation if the y digit is 0
if (y_digits[j] == 0) {
next
}
# Calculate the product of the x digit and the y digit
product <- x_digits[i] * y_digits[j]
# Calculate the number of zeros to place after the product
num_zeros <- (length(x_digits) - i) + (length(y_digits) - j)
# Add the product with the appropriate number of zeros to the result
result <- result + (product * 10^num_zeros)
}
}
return(result)
}
# Define the Furers algorithm
furers <- function(x, tol = 1e-6) {
# Set the initial estimate of the square root to x / 2
sqrt_x <- x / 2
# Loop until the estimate converges to the desired level of precision
repeat {
# Calculate a new estimate of the square root
sqrt_x_new <- (sqrt_x + (x / sqrt_x)) / 2
# Calculate the absolute difference between the new and old estimates
diff <- abs(sqrt_x_new - sqrt_x)
# If the difference is within the desired tolerance, break the loop
if (is.na(diff)) {
# Update the estimate of the square root
sqrt_x <- sqrt_x_new
} else if (diff < tol) {
break
}
# Update the estimate of the square root
sqrt_x <- sqrt_x_new
}
return(sqrt_x)
}
# Set the seed for reproducibility
set.seed(123)
# Generate a vector of 100 random numbers within a certain range
x <- as.integer(runif(100, 1e2, 1e4))
# Measure the execution times of the Axero and Furers algorithms
axero_times <- sapply(x, function(xi) system.time(axero(xi, xi))["elapsed"])
furers_times <- sapply(x, function(xi) system.time(furers(xi))["elapsed"])
# Create a data frame with the execution times of the two algorithms
execution_times <- data.frame(algorithm = rep(c("Axero", "Furers"), each = 100),
time = c(axero_times, furers_times))
# Load the ggplot2 package
library(ggplot2)
# Create a bar chart to visualize the execution times
ggplot(execution_times, aes(x = algorithm, y = time)) +
geom_bar(stat = "identity", position = "dodge")
# Install the car package if necessary
install.packages("car")
# Load the car package
library(car)
# Compare the distribution of execution times for the Axero and Furers algorithms
qqplot(execution_times[execution_times$algorithm == "Axero", "time"],
execution_times[execution_times$algorithm == "Furers", "time"],
xlab = "Axero", ylab = "Furers")
# Calculate the average execution times for the two algorithms
axero_mean <- mean(execution_times[execution_times$algorithm == "Axero", "time"])
furers_mean <- mean(execution_times[execution_times$algorithm == "Furers", "time"])
# Print a statement stating how many times the faster algorithm is faster than the slower algorithm
if (axero_mean < furers_mean) {
print(paste("The Axero algorithm is", round(furers_mean / axero_mean, 2), "times faster than the Furers algorithm."))
} else {
print(paste("The Furers algorithm is", round(axero_mean / furers_mean, 2), "times faster than the Axero algorithm."))
}