mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Lone Mersenne Hunters > LMH > 100M

Reply
 
Thread Tools
Old 2004-01-24, 18:25   #1
nfortino
 
nfortino's Avatar
 
Nov 2003

3×5×11 Posts
Default Reverse Decomp Program

I have been working on a reverse decomp program to allow LMH>79M to operate in a more similar fashion to normal LMH. Since I don't have much time, I have only completed my work for the nofactor data (which is no longer produced, but these programs will still be useful once we get that process automated). I had to change the sieve limit on decomp to allow it to go beyond 79300000, and it now goes to 1000000000. I also wrote a program called missed.exe, which prints the primes above 79300000 in neither factor nor nofactor into a file called primes. This allows the compression program (compress.exe) to account for the fact that the primes aren’t there. (Note: as it stands, this program needs 125MB of memory, and writes a 125MB file to the disk. The memory is proportional to the upper bound; the file size is of course dependant on what is missing from the data files.) The reason I do this is it allows compress to work without a sieve, making it fast and still effective. Ideally, the data files would have all primes; with the ones with no work done on them in nofactor with fact bits equal to 10 (as we know there are no factors below 1024). Once this is done, missed.exe will not be needed, and the compression operation will take less than a minute. Finally, I would like to note that currently these programs are very picky about the data files, and will fail (sometimes discreetly) if they are not exactly as expected. For example, the most recent factor data has an invalid line after 129999929, causing it to give a false result for exponents larger than 129999929 without an error message. I gave brief instructions in the readme on how to use these programs. Questions, comments, and improvements are welcome. I have the Dec 11 version of the nofactor data if anyone would like to make it available somewhere so people can use it.

Since nothing can be done without the nofactor data, I am going to try to automate the process of creating it, but I can only do work on weekends. Xyzzy, I think you should put the raw data on opteron so many people can try to convert it into usable data.
Nick
Attached Files
File Type: zip compress.zip (21.9 KB, 138 views)
nfortino is offline   Reply With Quote
Old 2004-01-24, 18:43   #2
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

7,559 Posts
Default

Okay, the raw data files are here:

http://opteron.mersenneforum.org/lmh/
Xyzzy is offline   Reply With Quote
Old 2004-01-30, 22:38   #3
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

2·3·1,151 Posts
Default

The compress program I use:


#include "stdio.h"
#include "math.h"
#include "malloc.h"
#include "memory.h"

int COMPRESS_FACTORS = 0;
int COMPRESS_NOFACTORS = 0;

#define bitset(a,i) { a[(i) >> 3] |= (1 << ((i) & 7)); }
#define bitclr(a,i) { a[(i) >> 3] &= ~(1 << ((i) & 7)); }
#define bittst(a,i) (a[(i) >> 3] & (1 << ((i) & 7)))

/* Return TRUE if arg is a prime */

int isprime (
unsigned long p)
{
unsigned long f, fmax;
if ((p & 1) == 0) return (p == 2);
if (p % 3 == 0) return (p == 3);
fmax = sqrt (p);
for (f = 5; f <= fmax; f += 6) {
if (p % f == 0) return (0);
if (p % (f+2) == 0) return (0);
}
return (1);
}

/* Use a simple sieve to find prime numbers */

#define MAX_PRIMES 6600
static unsigned int num_primes = 0;
static unsigned int *primes = NULL;
static struct sieve_info {
unsigned long first_number;
unsigned int bit_number;
unsigned int num_bits;
unsigned long start;
unsigned long end;
char array[4096];
} si;

/* Start sieve by allocate a sieve info structure */

void start_sieve (
unsigned long start,
unsigned long end)
{
unsigned int i, fmax;

if (start < 3) start = 3;
si.start = start;
si.end = end;
si.first_number = start | 1;
si.bit_number = 1;
si.num_bits = 0;

if (primes == NULL) {
unsigned int f;
primes = (unsigned int *) malloc (MAX_PRIMES * 2 * sizeof (unsigned int));
for (i = 0, f = 3; i < MAX_PRIMES * 2; f += 2)
if (isprime (f)) primes[i] = f, i += 2;
}

/* Determine the first bit to clear */

fmax = (unsigned int) sqrt ((double) end);
for (i = 0; i < MAX_PRIMES * 2; i += 2) {
unsigned long f, r, bit;
f = primes[i];
if (f > fmax) break;
if (si.first_number == 3) {
bit = (f * f - 3) >> 1;
} else {
r = (unsigned long) (si.first_number % f);
if (r == 0) bit = 0;
else if (r & 1) bit = (f - r) / 2;
else bit = (f + f - r) / 2;
if (f == si.first_number + 2 * bit) bit += f;
}
primes[i+1] = bit;
}
num_primes = i;
}

/* Return next prime from the sieve */

unsigned long sieve ()
{
unsigned int i;

/* Return next prime in the sieve */

ret: while (si.bit_number < si.num_bits) {
unsigned int bit = si.bit_number++;
if (bittst (si.array, bit))
return (si.first_number + 2 * bit);
}

/* See if we are done */

si.first_number += 2 * si.num_bits;
if (si.first_number > si.end)
return (0xFFFFFFFF);

/* Fill the sieve with ones, then zero out the composites */

memset (si.array, 0xFF, sizeof (si.array));
si.num_bits = (unsigned int) (si.end - si.first_number) / 2 + 1;
if (si.num_bits > sizeof (si.array) * 8)
si.num_bits = sizeof (si.array) * 8;
for (i = 0; i < num_primes; i += 2) {
unsigned int f, bit;
f = primes[i];
for (bit = primes[i+1]; bit < si.num_bits; bit += f)
bitclr (si.array, bit);
primes[i+1] = bit - si.num_bits;
}
si.bit_number = 0;
goto ret;
}

void end_sieve ()
{
}

/* Do a subtraction on an ascii number */

void ascsub (char *n, unsigned long amt)
{
unsigned long digit;
char *p;

p = n + strlen (n);
for ( ; ; ) {
digit = *--p - '0';
if (digit < amt) {
*p = (char) (10 + digit - amt + '0');
amt = 1;
} else {
*p = (char) (digit - amt + '0');
break;
}
}
if (n[0] == '0' && n[1] != 0) strcpy (n, n+1);
}

/* Do a division on an ascii number */

void ascdiv (char *fac, unsigned long p, char *res)
{
int leadzero = 1;
unsigned long n, q;

for (n = 0; *fac; fac++) {
n = n * 10 + *fac - '0';
if (leadzero) {
if (n < p) continue;
leadzero = 0;
}
q = n / p;
*res++ = (char) (q + '0');
n = n - q * p;
}
*res = 0;
}

/* Compress one file of factoring data */

void compress_factors (char *fname)
{
static unsigned long group = 999999999;
static FILE *out = NULL;
FILE *factors;
unsigned long p, count;
char fac[200], k[200];

factors = fopen (fname, "r");
if (factors == NULL) {
printf ("Error opening %s\n", fname);
return;
}

if (out == NULL) {
out = fopen ("factors.cmp", "w");
if (out == NULL) {
printf ("Error opening factors.cmp\n");
return;
}
}

for ( ; ; ) {
p = 0;
fscanf (factors, "%lu,%s\n", &p, &fac);
if (p == 0) break;

for (count = 0; sieve () != p; count++);
if (count > 500) {printf ("Fac not found: %lu?\n", p); return;}

ascdiv (fac, p + p, k);
if ((p & 3) == 1) {
ascsub (k, 2);
ascdiv (k, 2, k);
} else {
ascsub (k, 1);
ascdiv (k, 2, k);
}

if (p / 100000 != group) {
group = p / 100000;
fprintf (out, "%lu,%s\n", p, k);
}

else if (count == 0 && k[0] == 0)
fprintf (out, "\n");
else if (count < 10)
fprintf (out, "%lu%s\n", count, k);
else if (count < 36)
fprintf (out, "%c%s\n", count - 10 + 'A', k);
else if (count < 62)
fprintf (out, "%c%s\n", count - 36 + 'a', k);
else
fprintf (out, "%lu,%s\n", count - 62, k);
}

fclose (factors);
}

/* Compress one file of nofactoring data */

void compress_nofactors (char *nofname)
{
static unsigned long group = 999999999;
static FILE *out = NULL;
FILE *nofactors;
unsigned long p, count, limit, b1, b2, last_limit = 0;

nofactors = fopen (nofname, "r");
if (nofactors == NULL) {
printf ("Error opening %s\n", nofname);
return;
}

if (out == NULL) {
out = fopen ("nofactor.cmp", "w");
if (out == NULL) {
printf ("Error opening nofactor.cmp\n");
return;
}
}

for ( ; ; ) {
p = 0;
fscanf (nofactors, "%lu,%lu\n", &p, &limit);
if (p == 0) break;
fscanf (nofactors, ",%lu\n", &b1);
fscanf (nofactors, ",%lu\n", &b2);

for (count = 0; sieve () != p; count++);
if (count > 500) {printf ("Fac not found: %lu?\n", p); return;}

if (p / 100000 != group) {
group = p / 100000;
fprintf (out, "%lu,%lu\n", p, limit);
last_limit = limit;
continue;
}

else if (count == 0 && limit == last_limit)
;
else if (count < 10)
fprintf (out, "%lu", count);
else if (count < 36)
fprintf (out, "%c", count - 10 + 'A');
else if (count < 62)
fprintf (out, "%c", count - 36 + 'a');
else
fprintf (out, "%lu,", count - 62);

if (limit != last_limit) {
if (limit > last_limit && limit - last_limit <= 5)
fprintf (out, "%c\n", limit-last_limit-1+'0');
else if (last_limit > limit && last_limit - limit <= 5)
fprintf (out, "%c\n", last_limit-limit-1+'5');
else
fprintf (out, "%lu\n", limit);
last_limit = limit;
} else
fprintf (out, "\n");
}

fclose (nofactors);
}

/* Compress factoring data */

void compress ()
{
if (COMPRESS_FACTORS) {
start_sieve (3, 79300000);
compress_factors ("c:\\database\\factors");
compress_factors ("c:\\database\\fac2");
end_sieve ();
}
if (COMPRESS_NOFACTORS) {
start_sieve (3, 79300000);
compress_nofactors ("c:\\database\\nofactor");
compress_nofactors ("c:\\database\\nofac2");
end_sieve ();
}
}

/* Compress/decompress factoring data */

void main (int argc, char **argv)
{
int i;
char *p;

/* Process command line switches */

for (i = 1; i < argc; i++) {
p = argv[i];

if (*p++ != '-') break;
switch (*p++) {

case 'F':
case 'f':
COMPRESS_FACTORS = 1;
break;

case 'N':
case 'n':
COMPRESS_NOFACTORS = 1;
break;

/* Otherwise unknown switch */

default:
printf ("Invalid switch\n");
}
}

compress ();
}
Prime95 is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Where can I find a Reverse and Add program? I can't find any! Stargate38 Programming 18 2015-07-10 06:08
Reverse memory lookup ewmayer Programming 6 2012-11-12 00:25
compiling decomp under linux James Heinrich Data 2 2006-08-27 15:59
decomp sorted <61 moo Lone Mersenne Hunters 0 2005-03-24 22:38
Decomp.exe bayanne Lone Mersenne Hunters 2 2003-06-03 12:41

All times are UTC. The time now is 03:41.

Sat Jul 4 03:41:25 UTC 2020 up 101 days, 1:14, 1 user, load averages: 1.13, 1.14, 1.21

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.