Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

Re: The 10**21 Problem (Part 3)

by oiskuu (Pilgrim)
on May 16, 2014 at 12:35 UTC ( #1086299=note: print w/ replies, xml ) Need Help??


in reply to The 10**21 Problem (Part 3)

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
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; ...
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.


Comment on Re: The 10**21 Problem (Part 3)
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1086299]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (16)
As of 2014-09-18 18:56 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (121 votes), past polls