Multiplicative.c - Revision history

Teorth at 16:43, 2 February 2010

2010-02-02T16:43:45Z

← Older revision		Revision as of 09:43, 2 February 2010
Line 5:		Line 5:
	#include <string.h>		#include <string.h>

	#define SIZE ~~200~~ // how many numbers the computer will look at;		#define SIZE 400 // how many numbers the computer will look at;
	// in principle, increasing this number makes the computer smarter		// in principle, increasing this number makes the computer smarter

Line 17:		Line 17:
	void exit_display(void);		void exit_display(void);

			int abs( int i )
			{
			if (i > 0) return i;
			else return -i;
			}

			int sgn(int i)
			{
			if (i > 0) return +1;
			if (i < 0) return -1;
			return 0;
			}

	void init( void )		void init( void )
Line 139:		Line 151:


	void deduce( void )		void deduce( void ) // make simple deductions based on existing knowledge
	{		{
	int i, j;		int i, j;
Line 149:		Line 161:
	modified = 0;		modified = 0;

	// begin forward scan to update up,low		// begin forward scan to update up,low by deducing bounds on f[1,i] from f[1,i-1]

	for (i=1; i < SIZE; i++)		for (i=1; i < SIZE; i++)
	if (vals[i] == ~~1 \|\| vals[i] == -~~1)		if (abs(vals[i]) == 1)
	{		{
	newup(i, up[i-1]+vals[i]);		newup(i, up[i-1]+vals[i]);
	newdown(i, low[i-1]+vals[i]);		newdown(i, low[i-1]+vals[i]);
	}		}
			else
			{
			newup(i, up[i-1]+1);
			newdown(i, low[i-1]-1);
			}

	// begin backward scan to update up,low		// begin backward scan to update up,low by deducing bounds on f[1,i-1] from f[1,i]

	for (i=SIZE-1; i > 0; i--)		for (i=SIZE-1; i > 0; i--)
	if (vals[i] == ~~1 \|\| vals[i] == -~~1)		if (abs(vals[i]) == 1)
	{		{
	newup(i-1, up[i] - vals[i]);		newup(i-1, up[i] - vals[i]);
	newdown(i-1, low[i] - vals[i]);		newdown(i-1, low[i] - vals[i]);
	}		}
			else
			{
			newup(i-1, up[i] + 1);
			newdown(i-1, low[i] - 1);
			}

	// look for cuts		// look for cuts (though this is redundant from the previous two scans

	for (i=1; i < SIZE; i++)		for (i=1; i < SIZE; i++)
Line 187:		Line 209:
	for (j=2; j*i<SIZE; j++)		for (j=2; j*i<SIZE; j++)
	{		{
	if (vals[i]~~== -1 \|\| vals[i]~~==1)		if (abs(vals[i]) == 1)
	if (vals[j] ~~== -1 \|\| vals[j]~~ == 1)		if (abs(vals[j]) == 1)
	if (vals[ij] > ~~1 \|\| vals[ij] < -~~1)		if (abs(vals[i*j]) > 1)
	{		{
	printf("f(%d)=f(%d)f(%d)=%d... ", ij,i,j,vals[i]vals[j]);		printf("f(%d)=f(%d)f(%d)=%d... ", ij,i,j,vals[i]vals[j]);
Line 195:		Line 217:
	}		}

	if (vals[i]~~== -1 \|\| vals[i]~~==1)		if (abs(vals[i])== 1)
	if (vals[ij] ~~== -1 \|\| vals[ij]~~ == 1)		if (abs(vals[i*j]) == 1)
	if (vals[j] > ~~1 \|\| vals[j] < -~~1)		if (abs(vals[j]) > 1)
	{		{
	printf("f(%d)=f(%d)/f(%d)=%d... ", j,ij,j,vals[ij]*vals[i]);		printf("f(%d)=f(%d)/f(%d)=%d... ", j,ij,j,vals[ij]*vals[i]);
Line 239:		Line 261:


	void main()		void main(int argc, char *argv[])
	{		{
	init();		int i, m;
	// set(2, -1);
			init();
			for (i=1; i < argc; i++)
			{
			m=0;
			sscanf(argv[i],"%d",&m);
			if (m==0)
			{
			printf("Arguments must be numbers!\n");
			exit(0);
			}
			set( abs(m), sgn(m) );
			}

	deduce();		deduce();
	display();		display();
	}		}

	</pre>		</pre>

Thomas: added HTML tags to make code better displayed on wiki, no changes to code itself

2010-02-02T04:39:44Z

added HTML tags to make code better displayed on wiki, no changes to code itself

← Older revision		Revision as of 21:39, 1 February 2010
Line 1:		Line 1:
			<pre>
	/* --- The following code comes from C:\lcc\lib\wizard\textmode.tpl. */		/* --- The following code comes from C:\lcc\lib\wizard\textmode.tpl. */
	#include <stdio.h>		#include <stdio.h>
Line 245:		Line 246:
	display();		display();
	}		}
			</pre>

Teorth at 23:53, 1 February 2010

2010-02-01T23:53:52Z

← Older revision		Revision as of 16:53, 1 February 2010
Line 29:		Line 29:
	{		{
	vals[i] = i;		vals[i] = i;
	for (j=1; j<40; j++)		for (j=2; j<40; j++)
	{		{
	if (vals[i] % (jj) == 0) vals[i] /= jj;		while (vals[i] % (jj) == 0) vals[i] /= jj;
	}		}
	if (i % 2 == 0)		if (i % 2 == 0)
Line 241:		Line 241:
	{		{
	init();		init();
	set(2~~, 1);~~		// set(2, -1);
	~~set(19~~, -~~1);~~
	~~set(37,~~ 1);
	deduce();		deduce();
	display();		display();
	}		}

Teorth at 23:44, 1 February 2010

2010-02-01T23:44:07Z

← Older revision		Revision as of 16:44, 1 February 2010
Line 4:		Line 4:
	#include <string.h>		#include <string.h>

	#define SIZE 200		#define SIZE 200 // how many numbers the computer will look at;
			// in principle, increasing this number makes the computer smarter

	// our knowledge is encoded in the following array		// our knowledge is encoded in the following array

Teorth at 23:37, 1 February 2010

2010-02-01T23:37:19Z

← Older revision		Revision as of 16:37, 1 February 2010
Line 4:		Line 4:
	#include <string.h>		#include <string.h>

	#define SIZE ~~500~~		#define SIZE 200

	// our knowledge is encoded in the following array		// our knowledge is encoded in the following array
Line 50:		Line 50:
	int pred, sred;		int pred, sred;

	if (~~vals[~~p~~] =~~= s) ~~return;~~		// need to reduce f(p)=s to f(pred)=sred

	if (vals[p] == -s)		if (vals[p] > 0)
			{
			pred = vals[p]; sred = s;
			}
			else
			{
			pred = -vals[p]; sred = -s;
			}

			if (vals[pred] == sred) return;

			if (vals[pred] == -sred)
	{		{
	printf("Contradiction! f(%d) = 1 and f(%d) = -1\n", p, p);		printf("Contradiction! f(%d) = 1 and f(%d) = -1 (from f(%d)=%d)\n", pred, pred, p, s);
	exit_display();		exit_display();
	}		}

	~~if (vals[p] == p)~~
	{
	~~pred = p; sred = s;~~
	}
	~~else // need to reduce f(p)=s to f(pred)=sred~~
	{
	~~if (vals[p] > 0)~~
	{
	~~pred = vals[p]; sred = s;~~
	}
	~~else~~
	{
	~~pred = -vals[p]; sred = -s;~~
	}
	}

	printf("Setting f(%d)=%d...\n",pred,sred);		printf("Setting f(%d)=%d...\n",pred,sred);
Line 144:		Line 139:
	void deduce( void )		void deduce( void )
	{		{
	int i;		int i, j;


Line 185:		Line 180:
	set(i, 1);		set(i, 1);
	}		}

			// look for multiplicativity opportunities
			for (i=2; i <SIZE; i++)
			for (j=2; j*i<SIZE; j++)
			{
			if (vals[i]== -1 \|\| vals[i]==1)
			if (vals[j] == -1 \|\| vals[j] == 1)
			if (vals[ij] > 1 \|\| vals[ij] < -1)
			{
			printf("f(%d)=f(%d)f(%d)=%d... ", ij,i,j,vals[i]vals[j]);
			set(ij, vals[i]vals[j]);
			}

			if (vals[i]== -1 \|\| vals[i]==1)
			if (vals[ij] == -1 \|\| vals[ij] == 1)
			if (vals[j] > 1 \|\| vals[j] < -1)
			{
			printf("f(%d)=f(%d)/f(%d)=%d... ", j,ij,j,vals[ij]*vals[i]);
			set(j, vals[i]vals[ij]);
			}
			}


	}		}
	while(modified);		while(modified);
Line 197:		Line 215:
	for (i=0; i < SIZE; i++)		for (i=0; i < SIZE; i++)
	{		{
	if (up[i-1] == 0 && low[i-1] == 0) printf("\|");		if (up[i-1] == 0 && low[i-1] == 0) printf(" \|");
	else		else
	if (low[i-1] == 2) printf("^");		if (low[i-1] == 2) printf(" ^");
	else		else
	if (up[i-1] == -2) printf("v");		if (up[i-1] == -2) printf(" v");
	else printf(" ");		else printf(" ");

	printf(" %4d ", vals[i]);		printf(" %4d", vals[i]);

	if (i % 10 == 9) printf("\n");		if (i % 10 == 9) printf(" [%d-%d]\n", i-9,i);
	}		}

Line 222:		Line 240:
	{		{
	init();		init();


	set(2, 1);		set(2, 1);
			set(19, -1);
			set(37, 1);
	deduce();		deduce();
	display();		display();
	}		}

Teorth: New page: /* --- The following code comes from C:\lcc\lib\wizard\textmode.tpl. */ #include #include #include #define SIZE 500 // our knowledge is encoded in the fol...

2010-02-01T23:09:59Z

New page: --- The following code comes from C:\lcc\lib\wizard\textmode.tpl.: #include <stdio.h> #include <stdlib.h> #include <string.h> #define SIZE 500 // our knowledge is encoded in the fol...

New page

/* --- The following code comes from C:\lcc\lib\wizard\textmode.tpl. */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 500

// our knowledge is encoded in the following array

int vals[SIZE+1]; // vals[i] = +a means f(i) = +f(a); vals[i] = -a means f(i) = -f(a).
int up[SIZE+1]; // best known upper bound for f[1,n]
int low[SIZE+1]; // best known lower bound for f[1,n]

void deduce(void);
void exit_display(void);

void init( void )
{
int i;
int j;

vals[0] = 0;
up[0] = 0;
low[0] = 0;

for (i=1; i <= SIZE; i++)
{
vals[i] = i;
for (j=1; j<40; j++)
{
if (vals[i] % (j*j) == 0) vals[i] /= j*j;
}
if (i % 2 == 0)
{
up[i] = 2; low[i] = -2;
}
else
{
up[i] = 1; low[i] = -1;
}
}
}

int modified=0;

void set( int p, int s ) // set f(p) = s
{
int i;
int pred, sred;

if (vals[p] == s) return;

if (vals[p] == -s)
{
printf("Contradiction! f(%d) = 1 and f(%d) = -1\n", p, p);
exit_display();
}

if (vals[p] == p)
{
pred = p; sred = s;
}
else // need to reduce f(p)=s to f(pred)=sred
{
if (vals[p] > 0)
{
pred = vals[p]; sred = s;
}
else
{
pred = -vals[p]; sred = -s;
}
}

printf("Setting f(%d)=%d...\n",pred,sred);

for (i=1; i<SIZE; i++)
while (vals[i] % pred == 0)
{
vals[i] /= pred; vals[i] *= sred;
}

modified=1;
}

void newup( int i, int new) // add f[1,i] <= new to knowledge
{
if (up[i] <= new) return; // is redundant

if (low[i] > new)
{
printf("Contradiction! %d <= f[1,%d] <= %d\n", low[i], i, new);
exit_display();
}

// printf(" (up[%d] = %d)", i, new);

up[i] = new;
modified = 1;
}

void newdown( int i, int new) // add f[1,i] >= new to knowledge
{
if (low[i] >= new) return; // is redundant

if (up[i] < new)
{
printf("Contradiction! %d >= f[1,%d] >= %d\n", up[i], i, new);
exit_display();
}

// printf(" (low[%d] = %d)", i, new);

low[i] = new;
modified = 1;
}

void cut(int i) // we learn that f[1,i] = 0
{
if (up[i] == 0 && low[i] == 0) return;

if (up[i] < 0)
{
printf("Contradiction! f[1,%d]=-2 but f(%d)=f(%d+1)\n", i, i, i);
exit_display();
}
if (low[i] > 0)
{
printf("Contradiction! f[1,%d]=+2 but f(%d)=f(%d+1)\n", i, i, i);
exit_display();
}

// printf(" (cut[%d])", i);

up[i]=0;
low[i]=0;
modified=1;
}

void deduce( void )
{
int i;

do
{
printf("Deducing...\n");
modified = 0;

// begin forward scan to update up,low

for (i=1; i < SIZE; i++)
if (vals[i] == 1 || vals[i] == -1)
{
newup(i, up[i-1]+vals[i]);
newdown(i, low[i-1]+vals[i]);
}

// begin backward scan to update up,low

for (i=SIZE-1; i > 0; i--)
if (vals[i] == 1 || vals[i] == -1)
{
newup(i-1, up[i] - vals[i]);
newdown(i-1, low[i] - vals[i]);
}

// look for cuts

for (i=1; i < SIZE; i++)
if (i % 2 == 1 && vals[i] == vals[i-1])
cut(i-1);

// look for peaks and troughs

for (i=1; i < SIZE-1; i++)
{
if (up[i] <= low[i-1])
set(i,-1);
if (low[i] >= up[i-1])
set(i, 1);
}
}
while(modified);
}

void display( void )
{
int i;

printf("\n");
for (i=0; i < SIZE; i++)
{
if (up[i-1] == 0 && low[i-1] == 0) printf("|");
else
if (low[i-1] == 2) printf("^");
else
if (up[i-1] == -2) printf("v");
else printf(" ");

printf(" %4d ", vals[i]);

if (i % 10 == 9) printf("\n");
}

printf("\n");
}

void exit_display(void)
{
display();
exit(1);
}

void main()
{
init();

set(2, 1);
deduce();
display();
}