NNG telefonszam feladat

nng_telefonszam_feladat.c

#include <stdio.h>

int do_original(int num) {
	const int nyolc0 = 100000000;
	unsigned int i;

	for (i = num * 3 + 1; i > 0; --i) {
		//printf(" % *d\ti:%d\n", 12, num, i);
		num = (num % nyolc0) * 10 + num / nyolc0;
	}

	return num;
}

int do_original_mod(int num) {
	const int nyolc0 = 100000000;
	unsigned int i;

	i = (num * 3 + 1);
	//printf("i: %u\n", i);
	for (i = (num * 3 + 1), i %= 9, i+=9; i > 0; --i) {
		//printf(" % *d\ti:%d\n", 12, num, i);
		num = (num % nyolc0) * 10 + num / nyolc0;
	}

	return num;
}

/* Rotate the number right (quasi backwards)
   Num must be a maximum 9 (decimal)digit positive number */
int rotate_right(int num, int val) {
	for (; val > 0; --val)
		num = (num / 10) + (num % 10) * 100000000;
	for (; val < 0; ++val)
		num = (num % 100000000) * 10 + num / 100000000;

	return num;
}

int generate(int goal) {
	int i = 0;
	unsigned int modulo;
	unsigned long int x;
	int num, num_backshifted;

	/* this could (and would!) occure integer overflow
	 * in the original code, let's exploit it! */
	x = goal * 3 + 1;

	/* So the overflow only affect the (mod 9) operation,
	 * basically it screw up the modulo because of the 
	 * (x mod 2^32) mod 9 operation order
	 * A correction term should apply:
	 * (x % 2^32) % 9 == x % 9 - 2^32 * floor(x / 2^32) % 9
	 * And == x % 9 - 4 * (x // 2^32) % 9
	 * It could be written as (x - 4*x//2^32) % 9 but just don't bother
	 * proove its correctness... (but it is, I suppose)
	 * So the new (mod 9) value is: */

	// But to bo honest, this isn't used here...
	// Only input of 9 digit accpedted!
	modulo = ((x % 9) - ((x >> 32) << 2) % 9) % 9;
	//printf("mod: %d\n", modulo);

	/* The goal number should be shifted `modulo` times left to get
	 * the initial number: */
	num = rotate_right(goal, modulo);
	printf("basic sol: % *d\n", 10, num);
	// This is the very basic sollution, but sometimes there's more!

	// Now rotate only (modulo-1) times back, and let's create 
	// a new ending number
	num_backshifted = rotate_right(goal, modulo);

	/* Because int_max is 2147483647, so we have one spare digit
	 * thus we can exploit the `num / nyolc0` part of the original
	 * algorithm.
	 * On the other hand we have >only< one spare digit, so the result
	 * of `num / nyolc0` is restricted to two digits (instead of the
	 * default one!). And furthermore to obey to the int_max, we can
	 * only use number from 00 to 21. */

	/* But we still don't know the shift value (the modulo), because
	 * the shift depends on the initial value. 
	 * (Note: modulo is `unsigned int`, so it can go up to 4294967296,
	 * but `num` max out at 2^31-1 = 2147483647)
	 * The 2^31-1 limited threshold points are followings:
	 * ###########################################
	 * #      num      #  - 4 * (x // 2^32) % 9  #
	 * ###########################################
	 * # > 1431655764  #           -4            #
	 * ###########################################
	 * (these are ranges, not just relations!)
	 */

	/* If we change a number in the following way:
	 *   num_1 = upper * 100000000 + lower;
	 *   num_2 = lower * 10 + upper;
	 * num_1 % 9 == (upper + lower) % 9  and 
	 * num_2 % 9 == (lower + upper) % 9, so they are the same!
	 * So shifting doesn't change mod 9 value of num, and note, that
	 * here we don't use any assumptions on `upper` and `lower`!
	 * So knowing the modulo 9 of the goal number and the range 
	 * (see previous section) we can compute the corrected overflow modulo.
	 */

	// Now for 999999999 < num <= 1431655764: modulo-correction: 0
	// num = rotate_right(num_backshifted, 0);
	num = 1000000000 + num - 1;
	printf("candidate: % *d  ", 10, num);
	if (999999999 < num && num <= 1431655764) {
		// it's feasable just turning the number over the computed modulo
		printf("[OK]\n");
	} else {
		printf("[NOPE]\n");
	}

	// Now for num > 1431655764: modulo-correction: -4
	num = rotate_right(num_backshifted, -4);
	//printf("rotated: %d\n", num);
	num = 1000000000 + num - 1;
	printf("candidate: % *d  ", 10, num);
	if (num > 1431655764) {
		// it's feasable to put a leading `1` to the number
		printf("[OK]\n");
	} else {
		printf("[NOPE]\n");
	}
}

int brute_force(int goal) {
	unsigned count = 0x7fffffff;
	const int nyolc0 = 100000000;
	unsigned int i;
	int num;

	for (; count > 0; --count) {
		if (!(count & 0xffffff)) {
			printf("Currently searching at: %d\n", count);
		}
		num = count;
		for (i = (num * 3 + 1), i %= 9, i+=9; i > 0; --i) {
			//printf(" % *d\ti:%d\n", 12, num, i);
			num = (num % nyolc0) * 10 + num / nyolc0;
		}
		if (num == goal) {
			printf("Alternative: %d\n", count);
		}
	}
	
	return num;
}

int main() {
	int goal_num;

	printf("Write the goal phone number: ");
	scanf("%d", &goal_num);
	generate(goal_num);

	return 0;
}

nng_telefonszam_tetszoleges_loop_count.c

#include <stdio.h>

// Multiplicative inverse of 3 mod 2^32 
// (PowerMod[3, -1, 2^32] or egcd(3, 2**32))
const unsigned int mul_3_inv = 2863311531U;

int do_original(int num) {
	const int nyolc0 = 100000000;
	unsigned int i;

	i = num * 3 + 1;
	printf("i: %d\n", i);
	for (; i > 0; --i) {
		//printf(" % *d\ti:%d\n", 12, num, i);
		num = (num % nyolc0) * 10 + num / nyolc0;
	}

	return num;
}

int do_original_mod(int num) {
	const int nyolc0 = 100000000;
	unsigned int i;

	i = (num * 3 + 1);
	//printf("i: %u\n", i);
	for (i = (num * 3 + 1), i %= 9, i+=9; i > 0; --i) {
		//printf(" % *d\ti:%d\n", 12, num, i);
		num = (num % nyolc0) * 10 + num / nyolc0;
	}

	return num;
}

int main() {
	unsigned int i_desired_value;
	int modded_num;

	printf("Give the desired loop counter initial value: ");
	scanf("%d", &i_desired_value);
	modded_num = (i_desired_value-1) * mul_3_inv;
	printf("Computed num for this i: %d\n", modded_num);

	printf("Modular code:  %d\n", do_original_mod(modded_num));
	printf("Original code: %d\n", do_original(modded_num));

	return 0;
}