Programming methods to find a sum.

['Tex]

I need to take input values, and in the most efficient manner possible find a sum closest to a value X, between value X and Y.

The number of input values is variable, and all input is negative. X doesn't have to be lower than Y, and vice versa. That is, X can be -8388608 or -(2^23) and Y can be 0, or X can be -8388609 and Y can be -16777216 or -(2^24).

I am using VBA for quick testing which will be put into a VB.Net application.


Remember, efficiency... the number of tests that would have to be performed via loops would range from around 32768 to well over 16777216 (32^3 and 256^3, respectively)...



The values inputted will be applied to an array. The input may occur as "45" and "63" and mean 45 through 63 as input values, but the array that is calculated, Array(45) maybe -8388600 or some other negative number.


Because of the huge number of calculations that may unnecessarily performed, I need either an efficient way to loop through common values (ergo, the sum value of 0, 0, 1 shouldn't be recalculated later as as 0, 1, 0 or 1, 0, 0) or a simple mathematical approach to finding a sum of appropriate value.

This help would be greatly appreciated. Thank you.



The arithmatic is usually modular, and related to level (game is Diablo 2, although this is the hacking side of it involving 1.09d and extraordinarily large numbers.)

For example, the BoCL value 8 for level X is Level * 8 / x

The math is modular, and signed, for -8,388,608 to positive 8,388,607. So having two BoCL(8) is the same as BoCL(16), but I am using a derivative arithmatic in the game that only applies to the negative values. The sum of these values must be negative, and is not modular. Moreover, let's say I have the values:

10, 10, 0

Well, that isn't BoCL(20) but rather the sum of the modular values for BoCL(10) and BoCL(10). If BoCL(10) = -8388608, then (10, 10, 0) is -16,777,216.

This presents a unique problem, as I cannot simply perform a loop check on the values 1 to X, X being the highest possible value times three. Let's say it's 63 normally.

(63, 0, 0) is not necessarily equal to (32, 31, 0) and thus any operation that derives the answer must take that into account, it cannot simply do BoCL(1) through BoCL(189).



Edit: An efficient implementation could also occur so that the values BoCL(1) to BoCL(Limit * 3)... such that you could take the modular sum you want, say, -8388609, and specify the closest value to 8388607 (that value taken modular). So you could specify that if 8388607 is BoCL(100) then any number of negative values that sum to 100, such as BoCL(25) + BoCL(25) + BoCL(50) would sum to -8388609. Does this make sense?

BoCL	Value
22	-8126464
23	-7733248
24	-7340032
25	-6946816
26	-6553600
27	-6160384
28	-5767168
29	-5373952
30	-4980736
31	-4587520
32	-4194304
33	-3801088
34	-3407872
35	-3014656
36	-2621440
37	-2228224
38	-1835008
39	-1441792
40	-1048576
41	-655360
42	-262144
43	131072
44	524288
45	917504
46	1310720
47	1703936
48	2097152
49	2490368
50	2883584
51	3276800
52	3670016
53	4063232
54	4456448
55	4849664
56	5242880
57	5636096
58	6029312
59	6422528
60	6815744
61	7208960
62	7602176
63	7995392

So, for the sake of simplicity using 63 as the new limit just for ease... you can say that any two negative values that sum to the value 63, will have a value equal to the negative 63 which is -8,781,824. And this can be tested, using the values 31 and 32, which are -4,587,520, and -4,194,304 respectively.

However, there will be impossible values, such as the values of BoCL(1) to BoCL(21), as that range is positive there are no negative sums for 1 to 21.

 

[anorlunda]

You might find a library function SUM(), that will do the looping as efficiently as possible on your hardware. But it will probably not handle all your special cases.

Just go ahead and do the loops, add one element at a time.