Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So I have a list of values like so

L1 = [-4 -3 5 8 ];

Note the sum of each element in L1 will always be > 0.

The operation I am performing on L1 is as follows

 function applyRule:
  1) Pick lowest value [ ex. -4 ]
  2) Add it to its left and right neighbor [ left(-4) += -4; right(-4) += -4; ]
  3) Invert sign picked in #1 [ invertSign(-4) ]
  4) Repeat from step 1, until each element in L1 is non-negative
  5) return the number of iterations taken
 end applyRule;`

A side note, the left and right neighbor of a element X at index i, is (i-1) and (i+1). In the case the rule is applied to the first element, its left neighbor is the last element, and in the case of the last element, its right neighbor is the first element. Like a circular list.

The problem I am having is counting the number of iteration the function applyRule will take efficiently for large list( ex. list of size > 10,000 with values ranging from -200,000 < x < 200,000 )

The idea I had was to create a function T, which would transform L1, and the proceed to apply the function applyRule, which returns the number of iteration take, which I could use to transform into the actual result. Hope the idea is clear. here is an example:

A = [-100 101 0]

Note: applyRule( A ) -> 200

The transform function maps A into this list

T(A)-> [-10 11 0] #note each element is divided by 10 and ceiled up

Then we apply the rule function:

applyRule( T(A) ) -> 20 #assume its true for now

Then we transform 20 into the actual result F(20) -> 200 #note we multiplied 20 by 10, since the function T divided by 10

Unfortunately, the above doesn't work for all cases. Can someone help me develop a transform function that works efficiently, for large list, or even list that meets certain requirements.

share|improve this question
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.