Some further analysis.

Consider the last hashing step. Xor with q8 was a ±127 adjustment at most. Multiplied by hp=1000003, the difference is less than 2**27. It is therefore unlikely that a change in q8 would carry into sign of d8. Now, hp % 1001 == 4, which is like a shift. In a sense, all the magic bits have a weight of a power of two.

> perl -e 'print join q( ), map 1000003*(1<<$_) % 1001 % 4, (0..7)'
0 0 0 0 0 0 0 0

[download]
What this means is q8 can be stepped without altering 2 lowest result bits, provided d8 does not change sign and d >= 4*step && d < 1001-4*step.

// C D M values are all 0 (modulo 4).
int step_cdm[1001] = { 0,0,0,0, 0,1,1,1, 0,2,2,2, 0,3, ... , 0,2,2,2, 
+0,1,1,1, 0,0,0,0, 0 };
int step_cdm2[2002] = {...};                             // (above)x2
#define step_ok(v) (2U* ((v) & ~127)*hp < -2U* 127*hp)   // *2 to disc
+ard sign
...
step = step_cdm2[d9 % 1001 + 1001];
if (step && step_ok(d7)) { q8 += step - 1; continue; }   // loop q8
if (d != 500) continue;
...

[download]
Note that if this heuristic is enabled, it may leave no time for prefetching. Try without lookups. Perhaps some other modulus might have better karma, a modulus that reduces hp to odd value (e.g. 1000003 % 1039 == 485)?

Update: Actually, scratch that. I forgot q8 selects q9, which of course toggles the low bits. There might be a way to set further restrictions on allowed q8's, but this is getting pretty convoluted.

In reply to Re: The 10**21 Problem (Part 3) by oiskuu
in thread The 10**21 Problem (Part 3) by eyepopslikeamosquito

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.