Puzzle - RPL and others
05-11-2021, 10:37 PM
Post: #41
 ijabbott Senior Member Posts: 1,304 Joined: Jul 2015
RE: Puzzle - RPL and others
(05-11-2021 02:14 PM)3298 Wrote:
(05-11-2021 11:58 AM)Albert Chan Wrote:  Without typecast, it may already be broken with left shift 31

1 << 31 = -2147483648

If bitset_t is 32-bits, not harm done, digit_bitset = 0x80000000
If bitset_t is 64-bits, it messed up, digit_bitset = 0xffffffff80000000
That would be sign-extension. I typedef'd bitset_t to be unsigned long long, which should as an unsigned type receive zero-extension instead.

Albert is correct. Converting a narrower signed integer value to a wider unsigned type does result in sign extension, although the result will always be positive. For example, assigning a 32-bit signed integer value -1 to a 64-bit unsigned integer will produce the value 0xffffffffffffffff.

Quote:C is certainly happy to stab you in the back when you treat it wrong.

That is true!

— Ian Abbott
05-13-2021, 11:38 PM (This post was last modified: 05-14-2021 09:52 PM by Albert Chan.)
Post: #42
 Albert Chan Senior Member Posts: 2,682 Joined: Jul 2018
RE: Puzzle - RPL and others
(05-10-2021 03:57 AM)Albert Chan Wrote:  Per your advise, I did just that, implemented gcd(2n,d) buckets.
Odd/even stuff all gone ...

For n=60, this smarter version finished in 53 seconds (previously at 3 minutes).

I translated Lua version to C, and added more optimization.
Now it cache intermediate calculations, groups of 6 digits at a time.
Timing is close to my unsigned fastmod version, n=60 timing at 13.3 sec

BTW, Lua version comment about n ≤ ⌊ 2^(53/7) ⌋ = 190 were off.
With double, it should be n ≤ ⌊ 2^(54/7) ⌋ = 210, since even digits are always even.

I did not bother adding code to interpret the output, since solutions are so rare.
This is expected output:

c:\> polydivisible 10
{ 3 38 381 3816 38165 381654 7 72 9 }

c:\> polydivisible 14
{ 9 138 1935 27100 379405 5311674 7 104 1467 20546 287645 4027032 13 }

To convert back to base-14 digits, just recover 1 digit at a time:
These digits does not need correction: (1st, 7th, 13th ...) + last

2nd digit = 138 - 9*14 = 12
3rd digit = 1935 - 138*14 = 3
...

I also use unsigned as little as possible (only gcd(a,b))
Danger – unsigned types used here!

Code:
#include <math.h> #include <stdio.h> #include <stdlib.h> unsigned gcd(unsigned a, unsigned b) {     for(;;) {         if (b == 0) return a;         a %= b;         if (a == 0) return b;         b %= a;     } } void printx(double *x, int n) {     printf("{ ");     for(int i=1; i<n; i++) printf("%.0f ", x[i]);     printf("}\n"); } void recurse(int *a, int n, int k, double *x) {     if (k==n) return printx(x, k);     double D = 0.0;     int i = 6, d = k-1, step = k+k;     for(; i < d; i+=6) D = fmod(D*x[0] + x[i], k);     if (i-5 != d && d) x[d] += x[d-1]*n;    // add new digit     D = D * x[d-i] + x[d];              // D*n^p + last_digit     if (d == i) D = fmod(D, k);         // keep D <= n^6         d = k - (int)fmod(D*n, k);          // valid (mod k)     if (k&1) {      // odd k         if (!(d&1)) d += k;             // k = d = 1 (mod 2)     } else {        // even k         if (!(k&3)) step = k;           // step  = 0 (mod 4)         else if (!((n+d)&3)) d += k;    // n+d+k = 0 (mod 4)     }     for(int bucket = a[2*n+k]; d < n; d += step) {         if (a[d] && a[n+d] == bucket) {             x[k] = d;             a[d] = 0;                   // mark taken             recurse(a, n, k+1, x);             a[d] = d;                   // restore         }     } } void puzzle(int n) {            // polydivisible number, base n     if (n&1) return;            // n must be even     int a[3*n], i, j, g, bad = 0;     double x[n+6];     for(i=1; i < n; i++) {         a[i] = i;               //   +1 to  n-1 = duplicate check         if ((g = a[n+i] = gcd(n,i)) != (a[2*n+i] = gcd(2*n,i))) {             for (x[bad] = g, j=0; x[j] != g; j++) ;             if (j == bad) bad++;    // bad buckets         }     }     for(i=0; i < bad; i++) {        // fix bad buckets         for(g = x[i], j=2*n+1; j < 3*n; j++)             if (g == a[j]) a[j-n] = g+g;     }     for(x[0]=i=1; i<7; i++) x[i] = x[i-1]*n;     recurse(a, n, 1, x+6);          // arrays all 1-based } int main(int argc, char **argv) {     int n = 0;     if (argc > 1) n = atoi(argv[1]);     if (0 < n && n <= 210) {puzzle(n); return 0;}     return printf("Usage %s n, 0 < n <= 210\n", argv[0]); }

Update: fixed a bug
Code:
    D = D * x[d-i] + x[d];              // D*n^p + last_digit     if (d == i) D = fmod(D, k);         // keep D <= n^6     d = k - (int)fmod(D*n, k);          // valid (mod k)

It was possible for agrument inside fmod to reach size n^8.
Added a guard against it, lowered it back down to n^7
Had we remove the guard, code still work, but base ≤ ⌊2^(55/8)⌋ = 117.

Above code snippet had a flaw, but turns out harmless.

if k = 1, then D = 0 * x[-6] + x[0] = 0 * n^0 + n^6 = n^6
This is just gibberish, but fmod() "fixed" it, since with integer x, fmod(x,1) = 0.
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)