Re: FINAL Encoding a packed set

allan_w@my-dejanews.com wrote in
news:1117236797.175686.62360@f14g2000cwb.googlegroups.com:

I coded the simle enconding using no carry and only 32 bit
arithmetic it takes a few to check every combination but the
simple arithmetic reduces it to 21 bits in every case. I
checked encoding and the reverse for every case. The left
most 21 bits of ANS is all you need. Here is test code

#include <stdio.h>
#include <stdlib.h>
/* to test every case of 47c5 */
int
main()
{
unsigned long   i, dif, tot;
unsigned long   lo, hi, ans;
char            a[47] = {0};
int             numz = 42;
int             numo = 5;
int             z, b, c, d, e;
long            id;
int             err20, err21, p20, p21;
err20 = 0;
err21 = 0;
p20 = 0;
p21 = 0;
id = 0;
for (z = 1; z < 44;) {
for (b = z + 1; b < 45;) {
for (c = b + 1; c < 46;) {
for (d = c + 1; d < 47;) {
for (e = d + 1; e < 48;) {
++id;
if (id > 1533900 || id < 5)
printf("\n %d : %d %d %d %d %d", id, z, b, c, d, e);
hi = 0xFFFFFFFF;
lo = 0;
numz = 42;
numo = 5;
for (i = 47; i-- > 0;) a[i] = 0;
a[z - 1] = 1;
a[b - 1] = 1;
a[c - 1] = 1;
a[d - 1] = 1;
a[e - 1] = 1;
i = 0;

/* encode */
for (;;) {
tot = numz + numo;
dif = hi - lo;
dif = (dif / tot) * numz;
if (a[i] == 1)
lo = lo + dif + 1;
else
hi = lo + dif;
if (a[i] == 0)
numz--;
else
numo--;
i++;
if (numo * numz == 0) break;
}
ans = hi & 0xFFFFF000;      /* if twenty bits allowed */
if (ans > hi || ans < lo)
err20++;
else
p20++;
ans = hi & 0xFFFFF800;	/* to limit to twenty 21 bits */
if (ans > hi || ans < lo)
err21++;
else
p21++;

/* reverse */
hi = 0xFFFFFFFF;
lo = 0;
i = 0;
numz = 42;
numo = 5;
for (;;) {
tot = numz + numo;
dif = hi - lo;
dif = (dif / tot) * numz;
if (ans > (lo + dif)) {
lo = lo + dif + 1;
numo--;
if (a[i] != 1) {
printf(" ERROR %d ", id);
exit(-1);
}
} else {
hi = lo + dif;
numz--;
}
i++;
if (numo * numz == 0)
break;
}
for (; numo != 0;) {
if (a[i] != 1) {
printf(" ERROR %d ", id);
exit(-1);
}
if (numo-- == 0) break;
i++;
} e++;
} d++;
} c++;
} b++;
} z++;
}
printf(" err21 = %d err20 = %d \n", err21, err20);
printf(" pas21 = %d pas20 = %d \n", p21, p20);
}


It was a very interesting problem, I am real surprised
as what seems to me to be an over simplifed arithmetic
completely reducing it to 21 bits. The encode and decode
would be very fast and simple.

David A. Scott
--
My Crypto code
http://bijective.dogma.net/crypto/scott19u.zip
http://www.jim.com/jamesd/Kong/scott19u.zip old version
My Compression code http://bijective.dogma.net/
**TO EMAIL ME drop the roman "five" **
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged.
As a famous person once said "any cryptograhic
system is only as strong as its weakest link"