# Looking for efficient solution to problem

1. Jul 24, 2004

### '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?

Code (Text):
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.

Last edited: Jul 24, 2004