Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

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

by oiskuu (Friar)
on May 05, 2014 at 20:08 UTC ( #1085114=note: print w/ replies, xml ) Need Help??


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

Regarding the hash function and the modulus.

Firstly, the if (m9 == -1) continue; clause could just as well be omitted—this may only result in false positives, not a false negative. Unlikely to matter though. I would also test if skipping the 10/13 cmps in the innermost loop(s) might improve performance!

Apart from the oddball -1 case, the py_hash() function does not feed high order bits back into the register. Bits propagate higher; low bits of the hash value depend on low bits of input only. The python modulus is trickier. It ((1001+v%1001) % 1001) can be evaluated via unsigned modulus: ((v-(v<0)*620U) % 1001). The sign bit therefore mixes into the 3rd lowest bit.

Compilers know how to replace a divide-by-constant with multiplication by its reciprocal. (Div operation typically has a very high latency.) A division by 10, for example, may be substituted with mul 0xcccccccd; shift right by 3(+32). The shift size varies:

udiv by 9993: magic=2746836385 (0xa3b965a1); shift=14; udiv by 8089: magic=2174828291 (0x81a13f03); shift=12 udiv by 1001: magic=98685563 (0x05e1d27b); shift=10; udiv by 1419: magic=24214051 (0x01717a23); shift=3 udiv by 6019: magic=2854273 (0x002b8d81); shift=2 udiv by 4765: magic=3605429 (0x003703b5); shift=2 udiv by 6147: magic=1397419 (0x001552ab); shift=1 udiv by 2049: magic=4192257 (0x003ff801); shift=1
Evidently, the choice of modulus can strengthen the hash function. Mod=2049 is particularly weak: (-1U%2049 +1) == 1024. Sign mixes into 10th lowest.

Update: it is easily shown that modulus must be odd. Hash function either preserves or inverts the lowest bit of r. Even modulus would also preserve it, making (r^v)&1 constant. But that does not fit the problem.


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

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (4)
As of 2015-07-04 23:33 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (60 votes), past polls