C - gregorymorrison/euler1 GitHub Wiki
C is a general purpose programming language introduced in 1972. I grew up on C; my background is in procedural languages. And after not having looked at this language in years, it took me less than five minutes to get back in the saddle and bang out this version of Euler1. Verbose but elegant:
// Euler1 in C
#include <stdio.h>
int euler(int n) {
int retval = 0;
for (int i=0; i<n; i++) {
retval += (i%3 == 0 || i%5 == 0 ? i : 0);
}
return retval;
}
int main() {
printf("euler1 = %i\n", euler(1000));
return 0;
}Here's a functional version that uses tail recursion with an accumulator. One of the main points here is that the function euler() is deterministic - it will always return the same output for a given input. This is accomplished in part by the absence of any variable manipulation - there are instead only functions which return values. The other main point is that this recursion uses tail call optimization - it's written in such a way that an intelligent compiler can optimize its stack usage to be O(n) instead of O(n!). In English, this means that your program will probably not crash even for hugely recursive calls.
// Euler1 in C
#include <stdio.h>
int euler1(int n, int acc) {
return n == 0 ? acc :
euler1( n-1, acc+(n%3==0 || n%5==0 ? n : 0) );
}
int main() {
printf("euler1 = %i\n", euler1(999, 0));
return 0;
}Notice that we are not maintaining any state to solve our problem. No loops, no variables, no mutable state. We simply call euler() recursively to get the solution. This is an important part of the solution of the concurrency problem - how do you keep threads from stepping on each other's states? By eliminating mutable state!
I wanted to try to write a version of my Scheme program where I pass around an array of ints instead of n, peeling off the last one until the array is empty, but C is too low-level and requires assignments for managing memory, which I'll cover later. At any rate, here is my tail-recursion version, albeit with assignments:
// Euler1 in C
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int* range(int start, int end) {
int* ints = (int*)malloc(sizeof(int) * (end-start));
for (int i = start; i < end; i++) {
ints[i-start] = i;
}
return ints;
}
int _euler(int n) {
return n % 3 == 0 || n % 5 == 0 ? n : 0;
}
int euler(int* ints, int size, int acc) {
if (size == 0) {
return acc;
}
acc += _euler(ints[size-1]);
void* new_ptr = realloc(ints, sizeof(int) * (size-1));
return euler(ints, size-1, acc);
}
int euler1(int size) {
int* ints = range(0, size);
int acc = 0;
int sum = euler(ints, size, acc);
// free(ints);
return sum;
}
int main() {
printf("Euler1 = %i\n", euler1(1000));
return 0;
}Oddly, when I tried running this on a newer version of gcc, it complains that free is being called twice, so here I have commented out free(). Perhaps it has implicit garbage collection now?
Here's another version using a Quicksort-based algorithm. Here we recursively break the list up in half and then reassemble it. Instead of sorting each half, though, we’ll filter the pivot value, converting it to 0 if it’s not divisible. Here, euler() returns euler() calculated on the half of the list before the pivot element, euler() calculated on the half of the list after the pivot element, and the pivot element or 0, all added together:
// Euler1 in C
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int *slice(int start, int end) {
int *ints = malloc(sizeof(int) * end-start);
for (int i = start; i < end; i++) {
ints[i-start] = i;
}
return ints;
}
int euler(int *ints, int size) {
if (size == 0) {
return 0;
}
int pivot = size / 2;
int pivotVal = (ints[pivot]%3 == 0 || ints[pivot]%5 == 0) ? ints[pivot] : 0;
int pre = 0;
if (ints[pivot]-ints[0] > 0) {
int *preInts = slice(ints[0], ints[pivot]);
int preSize = ints[pivot] - ints[0];
pre = euler(preInts, preSize);
free(preInts);
}
int post = 0;
if (ints[size-1] - ints[pivot] > 0) {
int *postInts = slice(ints[pivot]+1, ints[size-1]+1);
int postSize = (ints[size-1]+1) - (ints[pivot]+1);
post = euler(postInts, postSize);
free(postInts);
}
return pre + pivotVal + post;
}
int euler1(int size) {
int *ints = slice(0, size);
int sum = euler(ints, size);
free(ints);
return sum;
}
int main() {
printf("euler1 = %i\n", euler1(1000));
return 0;
}This took me a few hours to knock out; I had forgotten about how painful C's nonexistent memory management is. "Yay, pointers!" said nobody ever. C doesn't have array slicing, no surprise, so I had to roll my own. In my function slice, I declare memory from the heap for the array of ints I will construct using malloc. And you reference the array elements by an offset to this physical memory address. That's what the int * syntax is - the memory address that I am passing around. When you're done with the memory, you tell C it can reclaim it using the delete function. If you don't, you could quickly run out of memory from all these recursive calls. This is known as a memory leak. C really forces you to have a lower-level understanding of how the runtime works.
The other part that's awkward is that there is no array end. Since you just have a memory address, you have to keep track of how many elements you put in the array. You can ask C for 10 bytes of memory, and C is happy to let you actually use 20 - it will just return undefined garbage for the other 10. One trick people use is to put a special character, '\0', known as a null terminator, at the end of the memory requested to keep track of where it's supposed to end. This is a built-in convention with strings to let the runtime know when it can stop reading memory to console output, for example.
Here's a version in which I use the canonical functional map/filter/reduce. C doesn't have anything like this, so let's write some quick versions that take a function and an array, and return an array or an int. Of course C being C, we have to pass the array by reference as well as the array size. Now, filter returns a different size array than the one passed in, so we'll have to allocate memory for a new array, deallocate the original, and pass back the new array and the new size. Since we're passing back two things, let's pass them both by reference - note filter()'s size is an int pointer, not an int.
Next, we'll define myMap(), myFilter(), and myReduce() - the "lambdas" implemented as function pointers using C's ugly syntax. Finally, we allocate memory for our ints, call map(), filter(), and reduce(), then free our memory before printing the results. Map() here is used only for illustration; we are not interested in mapping anything in this problem, so myMap() simply returns what was passed in. It's verbose and the syntax is ugly, but it is straightforward:
// Euler1 in C
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int* range(int start, int end) {
int *ints = (int*)malloc(sizeof(int) * (end-start));
for (int i = start; i < end; i++) {
ints[i-start] = i;
}
return ints;
}
int* map(int(*func)(int), int* ints, int size) {
for (int i = 0; i < size; i++) {
ints[i] = func(ints[i]);
}
return ints;
}
int* filter(bool(*func)(int), int* ints, int* size) {
int* newInts = (int*)malloc(sizeof(int) * *size);
int newSize = 0;
for (int i = 0; i < *size; i++) {
if (func(ints[i])) {
newInts[newSize] = ints[i];
newSize += 1;
}
}
void* new_ptr = realloc(newInts, sizeof(int) * newSize);
free(ints);
ints = newInts;
*size = newSize;
return ints;
}
int reduce(int(*func)(int, int), int *ints, int size) {
int result = 0;
for (int i = 0; i < size; i++) {
result = func(ints[i], result);
}
return result;
}
int myMap(int i) {
return i;
}
bool myFilter(int i) {
return i % 3 == 0 || i % 5 == 0;
}
int myReduce(int i, int j) {
return i + j;
}
int euler1(int size) {
int* ints = range(0, size);
ints = map(&myMap, ints, size);
ints = filter(&myFilter, ints, &size);
int sum = reduce(&myReduce, ints, size);
free(ints);
return sum;
}
int main() {
printf("euler1 = %i\n", euler1(1000));
return 0;
}Here’s one more – an elegant algorithm based on an observation by little Carl Friedrich Gauss. It operates in O(1) constant time. Don’t sweat it if this seems inscrutable; click the blog link above for an explanation:
#include <stdio.h>
#include <math.h>
double mySum(int n, int size) {
return (pow(floor(size/n), 2) + floor(size/n)) * n / 2;
}
int euler1(int size) {
return mySum(3, size) + mySum(5, size) - mySum(15, size);
}
int main() {
printf("euler1 = %i\n", euler1(999));
return 0;
}My belated thanks to Dennis Ritchie for giving us such a well-designed language.
To run this, I used the venerable GCC compiler. Simply apt install build-essential. Then compile to object code, enable execute permissions on the resultant object file, then execute:
$ g++ euler1.c -o euler1
$ chmod +x euler1
$ ./euler1
euler1 = 233168
$This is no surprise, but I am finding gcc's compiler error output to be excellent - among the best I've used. This is due no doubt to the decades of maturity it enjoys. C's command-line debugging is also quite mature - again, no surprise. It's a pleasure to use, and lets you set breakpoints, jump between stack frames, examine variables, etc. To use it, apt install gdb.
Then compile your program with debug parameters:
$ gcc -g euler1.c -o euler1.o
$ ./euler1_2.o