hash_val_4_Bloom Code
search for hash values used in Bloom filter for QNR membership
Brought to you by:
mdeale
Menu
▾
▴
Tree [8171cc] default tip / History
Read Me
Background As the Summary states, FenderBender came up with using Bloom filters. Usually those are employed on strings. Here they are used to determine membership between Quadratic Residues (QR) and Quadratic Non-Residues (QNR). Briefly, number theory says given the residues of a number-under-test modulo a small prime, then if that's a QNR then the number-under-test is definitely not a square. Uhuh. If it is in QR then we try another small prime. Etc. The original purpose in seeking an efficient square_root() function was that the Frobenius primality test as described by Grantham requires that we're not testing a square. Simple, right? Well, the Newton-Raphson iterative approach as developed by, say, Dijkstra is quite efficient. Especially when paired with Tomiska's initial-guess routine. The Tomiska routine started at 16-bits, then I tested for 32-, 64- and 128-bit initial guesses. So we're asking if a supplied prime-candidate IsSquare(). Even with the above described routines, as efficient as they are, it is still slow. FenderBender recognized that and developed his routine. Did he make optimal choices however? could we not use different small primes and shave off some runtime? or perhaps adjust the order of the small primes and save some time? and how much better is his second-round of filtering? Having tested numerous permutations and untold combinations of differing small primes, it is extremely likely that FenderBender's routine is optimal. Why? I dunno, but when he uses exactly "3*3" and "5*5" that is incredibly efficient. He also suggests, when working on larger (number under test) primes, to use a second round of filtering. His choices for 2nd rd. small primes are very good, though if you go with a 64-bit modulo then an 8% reduction in runtime appears to be likely (vs his 32-bit). FenderBender's code does about 1 square-root evaluation for (about) every 9982 numbers-under-test. If we add the 2nd rd (using 64-bit) we get about 1 in 3 million. Before Compiling convoluted steps. Huge search space requires heuristic approach in order to make manageable. Here are SOME of the variables that NEED to be set for each run. 1) set the appropriate command flags, e.g. bRun32 = true; bool bVerify = false; RunType eRun = RunType.Graded; int maxIter = 5050; # which is a lot for 'graded', since every hash fcn is tried int ModTblIdx = 2; index for 'superLgMod' ... but then set your target primes in that data struct, ie '1155,1575' # since this is a 'Graded' run 'specModLgFcnSched' is ignored. # furthermore, since 1155 has over 900 qnr's, going for 5000 iterations will take hours (10?) on a 3700x cpu. # but we get a good idea of which hash fcn's will do ok. I suggest to pick 3 fcn's of the top performers. # N.B. f10/f11/f12 seem to always do better, but often do not actually converge, since they are 'shallow' # 'shallow' is exposed when we do a 'ParTree' run. # when you have some good fcn's, then go to RunType eRun = RunType.Min; # since it's a 'min' run then must specify 'specModLgFcnSched' int maxIter = 125050; # if doing 3 fcn's then this can be a reasonable choice, but doesn't get too far # so have to do multiple runs over multiple days # so go into "cell 32.cs", find "public static void marchMixed32min()" then find "if (RR.Count > (16777216 + 4194304) )" # use 'strtIdx' to count down, ie. decrement tween runs, e.g. # strtIdx = 30463801; // 32589052; // 34714303; //36589554; // 37814805; ... // 66474800; # sorry 8) # if you happened to find a "perfect" filter ... great. Most likely not. # the min nrl's will be listed at the end of the run. Copy those, conveniently formatted for just this purpose, # into an appropriate data structure in "foundData.cs" int ModTblIdx = 13; # will point to 'testMods' RunType eRun = RunType.ParTree; int parDepth = 6; # start low then work up to 10 or 20, as necessary. This doesn't always work # which is why the 'diff' RunType was created. But it doesn't work at all yet. # if you've found a perfect filter, do test that out. bool bVerify = true; RunType eRun = RunType.Verify; int ModTblIdx = 11; # which is the 'foundMods' and update it with the number you found a filter for. # good luck .... How To Run dotnet clean -v n -c Release # it's good to make sure we're clean before building dotnet build -c Release # then ... dotnet run -c Release # or even ... time dotnet run -c Release &> temp_file # if perchance you're doing an 18 hour run, let's not cripple your main-driver # instead we publish, copy it over to the server and run it there. dotnet publish --configuration Release --runtime linux-x64 --self-contained -p:PublishReadyToRun=true # server only needs the DotNet-runtime environment installed. Much lighter than SDK. # development started under DotNet 6.0, but worked under 7 and now 8. # the executable consistently uses 93-95% cpu ... tho haven't been blessed with EPYC time yet. # if you have to share a server, perhaps you're using ProxMox and can limit the VM to, say, half the cores.
