- Commit
- 4b1e1f1d839e88520beb84a69850002e96fa7402
- Parent
- a1cd8c3a5d8223b16919f0ba1d53096d137e6723
- Author
- Pablo Emilio Escobar Gaviria <pablo-escobar@riseup.net>
- Date
Merge branch 'no-paralel'
An exercise on polyglossy: the same problem solved on multiple languages
Merge branch 'no-paralel'
4 files changed, 30 insertions, 152 deletions
Status | File Name | N° Changes | Insertions | Deletions |
Modified | Makefile | 2 | 1 | 1 |
Modified | c++/main.cpp | 65 | 15 | 50 |
Modified | c/main.c | 56 | 9 | 47 |
Modified | rust/main.rs | 59 | 5 | 54 |
diff --git a/Makefile b/Makefile @@ -1,5 +1,5 @@ c-bin: - gcc -O2 -pthread -o bin/c ./c/main.c + gcc -O2 -o bin/c ./c/main.c cpp-bin: g++ -O2 -o ./bin/cpp -std=c++11 -pthread ./c++/main.cpp
diff --git a/c++/main.cpp b/c++/main.cpp @@ -8,11 +8,10 @@ #define FAIL 1 #define INVALID_INPUT 2 -std::map<unsigned int, unsigned int> sums_cache; - -inline unsigned int sum_digits(unsigned int n) +inline int sum_digits(unsigned int n) { unsigned int sum = 0; + while (n != 0) { sum += (n % 10); @@ -22,61 +21,27 @@ inline unsigned int sum_digits(unsigned int n) return sum; } -void get_counterexpl_thread(unsigned int start, - unsigned int max, - unsigned int interval) +bool counterexpl(unsigned int max, std::map<unsigned int, int> sums_cache) { - for (auto a = start; a <= max; a += interval) + for (auto a = 0; a <= max; a ++) for (auto b = a; b <= max; b++) - { - auto diff = sums_cache[a + b] - (sums_cache[a] + sums_cache[b]); - - if (diff % 9 != 0) - exit(FAIL); - } -} + if ((sums_cache[a + b] - sums_cache[a] - sums_cache[b]) % 9 != 0) + return true; -bool read_first_arg(int argc, char *argv[], unsigned int *value) -{ - try - { - std::string value_str = argv[1]; - *value = std::stoul(value_str); - return true; - } - catch (...) - { - return false; - } + return false; } int main(int argc, char *argv[]) { - unsigned int max; - if (read_first_arg(argc, argv, &max)) - { - auto n_threads = std::thread::hardware_concurrency(); - std::vector<std::thread> threads; - - // Builds the sums cache - for (int i = 0; i != 2 * max; i++) - sums_cache[i] = sum_digits(i); + if (argc < 2) return INVALID_INPUT; + unsigned int max = std::stoul(argv[1]); - // Distributes calculations across threads evenlly - for (int i = 0; i < n_threads; i++) - { - auto thread = std::thread(get_counterexpl_thread, - i, - max, - n_threads); - thread.join(); - } + std::map<unsigned int, int> sums_cache; + + // Builds the sums cache + for (int i = 0; i <= 2 * max; i++) + sums_cache[i] = sum_digits(i); - return SUCCESS; - } - else - { - return INVALID_INPUT; - } + return counterexpl(max, sums_cache) ? FAIL : SUCCESS; }
diff --git a/c/main.c b/c/main.c @@ -1,6 +1,5 @@ #include <stdlib.h> #include <stdio.h> -#include <pthread.h> // Imports to get system information #ifdef _WIN32 @@ -21,18 +20,6 @@ // Let S: N -> N be the sum of the digits of a positive integer. // For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an integer. -int err = SUCCESS; // Global error condition -int *sums_cache; // Shared memory between threads -unsigned int max = 0; - -// Memory structure to pass arguments to threads using the pthreads library -typedef struct -{ - int start; - int step; - int end; -} range; - int sum_digits(unsigned n) { int parc = n; @@ -43,21 +30,17 @@ int sum_digits(unsigned n) sum += parc % 10; parc /= 10; } + return sum; } // Searches for a counterexample in an specific range. -int counterexempl(range *r) +int counterexempl(int max, int *sums_cache) { - for (int a = r->start; a <= r->end; a += r->step) + for (int a = 0; a <= max; a++) for (int b = a; b <= max; b++) - { if ((sums_cache[a + b] - (sums_cache[a] + sums_cache[b])) % 9 != 0) - { - err = 1; return FAIL; - } - } return SUCCESS; } @@ -72,37 +55,16 @@ int main(int argc, char *argv[]) unsigned int n_threads = strtoul(argv[2], NULL, 10); if (!n_threads) return INVALID_INPUT; - pthread_t thread_ids[n_threads]; - range thread_ranges[n_threads]; - // Create the sums cache - sums_cache = malloc(sizeof(int) * (2 * max + 1)); + int *sums_cache = malloc(sizeof(int) * (2 * max + 1)); for (int i = 0; i <= 2 * max + 1; i++) sums_cache[i] = sum_digits(i); - - // Divide the task into the specified number of threads - for (int i = 0; i < n_threads; i++) - { - thread_ranges[i] = (range){i, n_threads, max}; - err = pthread_create( - &thread_ids[i], - NULL, - counterexempl, - &thread_ranges[i] - ); - - if (err) fprintf(stderr, "Unable to create thread : %d\n", err); - } - - for (int i = 0; i < n_threads; i++) - { - err = pthread_join(thread_ids[i], NULL); - if (err) fprintf(stderr, "Unable to join threads : %d\n", err); - } - - return err; + return counterexempl(max, sums_cache); + } + else + { + return INVALID_INPUT; } - else return INVALID_INPUT; }
diff --git a/rust/main.rs b/rust/main.rs @@ -3,12 +3,7 @@ // Let S: N -> N be the sum of the digits of a positive integer. // For all A and B in N, S(A + B) = S(A) + S(B) - 9k, where k is an integer. -use std::{ - env, - process, - thread, - sync::{Arc, mpsc::{Sender, Receiver, channel}} -}; +use std::{env, process}; const SUCCESS: i32 = 0; const FAIL: i32 = 1; @@ -28,67 +23,23 @@ fn main() { args.next(); let max = parse_arg!(args); - let n_threads = parse_arg!(args); - if counterexempl(max, n_threads) { + if counterexempl(max) { process::exit(FAIL); } else { process::exit(SUCCESS); } } -/// Distributes calculations across threads and collect the results -fn counterexempl(max: usize, n_threads: usize) -> bool { - let sums_cache = Arc::new(get_sums(max)); - - if n_threads > 1 { - let (sender, reciever): (Sender<bool>, Receiver<bool>) = channel(); - let mut child_threads = Vec::with_capacity(n_threads); - - for _ in 0..n_threads { - let thread_countr_sd = sender.clone(); - let thread_sums = sums_cache.clone(); - - let child = thread::spawn( - move || thread_countr_sd.send( - counterexempl_range(thread_sums, max, n_threads) - ).expect( - "Thread was unable to sent a message trought the channel" - ) - ); - - child_threads.push(child); - if let Ok(true) = reciever.recv() { - return true; - } - } +fn counterexempl(max: usize) -> bool { + let sums_cache = get_sums(max); - for child in child_threads { - child.join().expect("Child thread panicked"); - } - - false - } else { - counterexempl_range(sums_cache, max, 1) - } -} - -/// Search for counterexamples among the items of a specif iterator. -fn counterexempl_range( - sums_cache: Arc<Vec<isize>>, - step: usize, - max: usize -) -> bool { - let mut a = 0usize; - - while a <= max { + for a in 0..max { for b in a..max { if (sums_cache[a + b] - sums_cache[a] - sums_cache[b]) % 9 != 0 { return true; } } - - a += step; } false