Skip to content

Instantly share code, notes, and snippets.

@bgotink
Created September 7, 2012 02:02
Show Gist options
  • Save bgotink/3662558 to your computer and use it in GitHub Desktop.
Save bgotink/3662558 to your computer and use it in GitHub Desktop.
Collatz conjecture program in C, depends on libgmp
#include <stdio.h>
#include <string.h>
#include <gmp.h>
/*
* Dependency: libgmp
* Compile using:
* gcc -o collatz -l gmp collatz.c
*/
typedef enum { false, true } bool;
bool quiet;
void log_(unsigned long int count, mpz_t * number) {
if (!quiet) {
printf("%-8lu - \t", count);
mpz_out_str(NULL, 10, *number);
printf("\n");
}
}
int main(int argc, char ** argv) {
if (argc < 1) {
printf("Argument required.\n");
fflush(stdout);
return 1;
}
int offset = 1;
quiet = false;
if (argc >= 2 && strcmp(argv[1], "--quiet") == 0) {
offset++;
quiet = true;
}
mpz_t number;
mpz_init(number);
mpz_set_str(number, argv[offset], 10);
long int count = 0;
log_(count, &number);
mpz_t zero, one, tmp, tmp2;
mpz_init(zero);
mpz_init(one);
mpz_set_si(one, 1);
mpz_init(tmp);
mpz_init(tmp2);
if (mpz_cmp(number, zero) <= 0) {
printf("Please enter a positive number, instead of %s\n", argv[offset]);
fflush(stdout);
return 2;
}
while (mpz_cmp(number, one) != 0) {
count++;
mpz_and(tmp, number, one);
if (mpz_cmp(tmp, zero) == 0)
mpz_fdiv_q_2exp(tmp, number, 1); // tmp := number >> 1 = number / 2
else {
mpz_mul_2exp(tmp2, number, 1); // tmp := number << 1 = 2 * number
mpz_setbit(tmp2, 0); // tmp2 := tmp + 1 = 2 * number + 1
mpz_add(tmp, tmp2, number); // tmp := tmp2 + number = 3 * number + 1
}
mpz_swap(number, tmp); // number := tmp
log_(count, &number);
}
if (quiet)
printf("%ld iterations needed\n", count);
return 0;
}
#!/bin/bash
if [ -z $DIGIT ]; then
DIGIT=9
fi
repeat() {
if [ $1 -eq 1 ]; then
echo $DIGIT;
elif [ $(( $1 % 2 )) -eq 0 ]; then
local t=$(repeat $(($1 / 2)));
echo $t$t
else
local t=$(repeat $(( ($1 - 1) / 2)));
echo $DIGIT$t$t;
fi
}
NB=$(repeat $1)
CHARS=$(echo $NB | wc -m)
CHARS=${CHARS/ /}
CHARS=$(( $CHARS - 1 )) # EOL is counted by wc ;)
echo $CHARS digits
time ./collatz --quiet $NB
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment