On second thought it probably won't be that efficient, since R2 is not a contiguous range :-( But maybe the method can be adjusted a little by having a table of booleans of points inside R1 that satisfies C2,C3,C4 etc. Other speed-up tricks could be to have 10 tables, with the high order bits taken from T1, T2, T3 in a cyclical fashion. The searching can be started from the sorted table that corresponds to the the narrowest set of criteria (fewest start points) This sounds like a fun problem that I could even contribute some time to do some programming if you are interested. Cheers, Frank On Sat, Oct 12, 2019 at 6:38 PM Mike Stay <metaweta@gmail.com> wrote:
Thanks, that's an excellent idea!
On Sat, Oct 12, 2019 at 7:12 AM Frank Stevenson <frankstevensonmobile@gmail.com> wrote:
Throwing out some thoughts here...
Set T1 = ((x * 0x000001) mod 2^24) and T2 = ((x * 0x088405) mod 2^24)
etc.
Then for each x, compute a T by bitwise concatenating T1,T2...T10 , which should be a 240 bit number. Granted 0 <= x < 2^24, there will be 2^24
such
numbers.
Sort all Ts into a list. Then the numbers that satisfy the first constraint (C1 from lower1, upper1) can be found within a range R1 in this list, Numbers that satisfy both C1 and C2 are found in a range R2 which is inside R1 etc.
Test all 2^40 constraints against this sorted list, when the range is empty, the test has failed. I think this can be done in O= 2^40 * 2 * 24 * 10 ( Worst case using binary search to identify the ranges ) and should be doable with relative modest computing power.
Or have I misinterpreted the problem ?
/f
On Fri, Oct 11, 2019 at 8:52 PM Mike Stay <metaweta@gmail.com> wrote:
I'd like to efficiently find solutions to constraints of the form
lower1 <= ((x * 0x000001) mod 2^24) < upper1 && lower2 <= ((x * 0x088405) mod 2^24) < upper2 && lower3 <= ((x * 0x652819) mod 2^24) < upper3 && ... where the constants are consecutive powers of 0x088405. Brute-forcing the space isn't much work to do for a single set of upper and lower bounds, but when I've got 2^40 such sets, it's daunting.
Any ideas? -- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun