Puzzle - RPL and others - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html) +--- Forum: General Forum (/forum-4.html) +--- Thread: Puzzle - RPL and others (/thread-16722.html) Pages: 1 2 3 RE: Puzzle - RPL and others - ijabbott - 05-11-2021 10:37 PM (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! RE: Puzzle - RPL and others - Albert Chan - 05-13-2021 11:38 PM (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  #include  #include  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 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.