Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Looking for efficient solution to problem

  1. Jul 24, 2004 #1
    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
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?
Draft saved Draft deleted



Similar Discussions: Looking for efficient solution to problem
  1. Looks like (Replies: 4)

  2. Looking for an app (Replies: 3)

  3. Looking for a program. (Replies: 2)

  4. It's ,solution please (Replies: 4)

  5. IT Solutions (Replies: 1)

Loading...