7

I have a double[] of huge size. (Ex : Eg.double[] array = new double[] {2.0, 3.1, 4.2, 8.9, 10.11, ........})

I want to get the sum of all the elements of that array at once. (Without using a loop).

Do you have any idea to do this?

5
  • you want to add elements in double arraybut from where you wil get those values ? can you please make it clear Commented Nov 4, 2010 at 7:32
  • What is a double array? you mean a two dimensional array? what is your element type? Commented Nov 4, 2010 at 7:33
  • What do you mean by a "double array" ? An array of doubles double[] ? Or some other structure ? To what do you want to add the elements ? Can you add some more informations to your question ? Commented Nov 4, 2010 at 7:34
  • I think by adding elements OP means summing them together, not adding new elements in an array. Commented Nov 4, 2010 at 7:37
  • @Guillaume : yes it is a double[] (Eg.double[] array = new double[] {2.0, 3.1, 4.2, 8.9, 10.11}). And, yes abhin4v, I wanna summing them together Commented Nov 4, 2010 at 7:55

13 Answers 13

10

No, you can't calculate the sum of a list of values in one step. Even if there was an API method or some library that offered a sum function, it would use loops internally. The complexity of the sum algorithm is O(n) (for single CPUs).

A way out could be using parallel computing, but that's a theoretical approach to answer your question. You'd need at least as many CPUs as array cells to calculate the sum in on step. (Or one fictional CPU with as many FP registers as array values).


Before you start looking at API's of Java or other libraries:

 public static double sum(double...values) {
   double result = 0;
   for (double value:values)
     result += value;
   return result;
 }

Usage:

 double sum = sum(array);  // this is in your main code -> no loop (visible)
Sign up to request clarification or add additional context in comments.

4 Comments

Thanks, Andreas_D. I'll go through them
Actually the complexity of the algorithm is O(n) even for multiple CPUs :-)
@paxdiabolo - I bet O(log n) is possible, O(1) maybe not. Thought of adding n/2 value pairs in the first step, then (n/2)/2 pairs of sums and so on. (parallel processing)
Enter in "embarrassingly parallel" GPUs! :-)
9

Yes, use a loop. That's what they're for. Hundreds of elements is a piddling little size for an array and will take almost no time to process.

Comments

7

In Java 8:

Arrays.stream(array).sum();

And if you want parallel on multiple CPUs:

Arrays.stream(array).parallel().sum();

Comments

4

First of all, 'hundreds' is not 'huge' ('millions' is) and second, adding the elements without looping is not possible unless you have some prior information about the elements (like if they are a part of a particular series).

3 Comments

That is true. Previously I used the word 'hundreds' just as a word. And I know that it can be done by using a loop. Any way the thing that I wanna know is how to get the sum of a double array without using a loop.
Actually millions isn't huge these days either. Billions is huge.
Summing a milion doubles takes ~0.003 seconds. :D
3

I would prefer the following approach.

package rfcampusdata;

public class TestClass {
  public static void main(String[] args) {
    String str = "1,2,3,4,5";
    String[] arr = str.split(",");
    int length = arr.length;

    System.out.println(sum(length, arr));
  }

  static Double temp = new Double(0);

  public static Double sum(int length, String[] arr) {
    int length_m = length - 1;
    String[] arr_m = arr;
    temp += Double.parseDouble(arr[length_m]);
    if (length_m != 0) {
      sum(length_m, arr_m);
    } else {
      // temp += Integer.parseInt(arr[0]);
      // System.out.println(temp);
    }
    return temp;

  }

Comments

2

A loop is the simplest and most efficient way to do things like summing the elements of an array or collection in Java.

There are ways to sum arrays that don't involve explicit loops, but they involve using simulated higher order functions, and they are complicated and ugly when written in Java. (And they are expensive and use loops under the hood.)

Java is not a functional programming language. If you want / need to do functional programming on the Java platform, use Scala or Clojure.

Comments

2

If you're really concerned with accuracy, a simple loop might cause some problems. Doubles do not contain arbitrary precision. Here's a simple example to show the flaw of just using a loop.

float f = 0;
for(int i = 0; i < 1000*1000*1000; ++i){
    ++f;
}
System.out.println(f);

We would hope that f would be 1 billion, or 1.0E9, but instead we get 1.6777216E7. This is because the float can only hold about 6-7 digits of precision. A double can hold about 16-17 digits of precision which means it is less likely to have an issue, but it doesn't solve the problem.

To work around this, we need to not add two numbers when there is a large magnitude difference between them. This can simply be done using a PriorityQueue. We'll take out the first 2 numbers, add them, then put them back into the queue. When the queue only has 1 number left, we return it.

public static double queueSum(double[] da){
    PriorityQueue<Double> pq = new PriorityQueue<Double>(da.length);
    for(double d : da)
        pq.add(d);
    while(pq.size() > 1)
        pq.add(pq.poll() + pq.poll());
    return pq.poll();
}

Of course accuracy does come at the cost of time. This goes from the loop sum's O(n) to a O(n lg(n)) not to mention the overhead of the objects involved.

Because doubles have much more precision than a float, you probably won't need to use this unless you have a huge number of doubles (millions/billions) and/or you have a large difference in magnitudes between your numbers.

Edit: If all the numbers have approximately the same magnitude, this code will help avoid the problem as well as maintain O(n) time. If there is a large magnitude difference between two samples or the numbers are distributed in a fashion that could cause a large magnitude difference, it could suffer the same problems as before.

public static double treeSum(double[] da){
    double[] dc = da.clone();
    int len = dc.length;
    while(len > 1){
        len = (len + 1) / 2;
        for(int i = 0; i < len; ++i)
            dc[i] += dc[i + len];
        dc[len] = 0;
    }
    return dc[0];
}

Comments

2

If your array is assigned to a DoubleMatrix1D object in cern.colt.matrix library you can use the zSum() method and it will return the sum of all elements in your array without having to loop

your_sum=your_array.zSum()

Comments

2

if the data type in your array is the object type Double ,not the primitive type double,then you can use stream in java 8 like this:

Double[] test = new Double[] {2.0, 3.1, 4.2, 8.9, 10.11};
List<Double> list = Arrays.asList(test);
double sum = list.stream().mapToDouble(p -> p).sum();
System.out.println(sum);

Comments

1

Anyone who has an actually huge array of doubles might look up cern.colt.list.AbstractDoubleList, which is built to optimize operations like adding (elements).

As others have said, if you want the summation of all elements in your array, you should write a loop.

2 Comments

There's no way that this "DoubleList" classes can be faster than just looping over an array directly and adding the elements, unless it is implemented as native code (which it isn't).
I agree, if you are willing to work exclusively with primitive arrays. If you want something that functions like a List object then the package I mention does a great job (I've used it to shuffle a large array).
1

Looping is the simplest way for this, but since you asked for a different one:

Recursion:

double sumResult = sum(data, 0, 0);

double sum(double [] d, int sum, int index) {
  if ( index > d.length ) return sum;
  else return sum(d, sum + d[index], index+1);
}

I haven't tested that, but it should work somewhere along the above.

EDIT: It is not recommended to use such a construct, since for huge array you may hit the StackOverflowException very fast.

4 Comments

+1 for out of the box thinking. But I'm not sure I would recommend to use it in a real project ;-)
it should be d.length...not double.length
I understand you're trying to perform a tail call optimization, bt AFAIK, java doesn't support it....so this can be done with just 2 parameters.
@st0le: Yeah, i noted that myself after I had written it. To much erlang in the last time. But I let it stay, since this is example code ;)
1

You need to create a nested class inside of the function and use recursion inside of the nested class to do the addition:

public double sumArrayNoLoop(double[] v){
 class compute {
            double  total = 0.0;
            public void sumArray(double[] v,int offset){
                if((offset - 1) < 0) return;
                if(offset > (v.length - 1)) offset = v.length;
                total += v[offset - 1];
                sumArray(v,offset - 1);

            }

        }

    compute c = new compute();
    c.sumArray(v, v.length);
    return c.total;
}

I

Comments

1

Friends this is the perfect solution that i have done.I am taking complex condition with string. we can used directly double array.

public class TestClass {
  public static void main(String[] args) {
    String str = "1,2,3,4,5";
    String[] arr = str.split(",");
    int length = arr.length;

    System.out.println(sum(length, arr));
  }

  static Double temp = new Double(0);

  public static Double sum(int length, String[] arr) {
    int length_m = length - 1;
    String[] arr_m = arr;
    temp += Double.parseDouble(arr[length_m]);
    if (length_m != 0) {
      sum(length_m, arr_m);
    } else {
      // temp += Integer.parseInt(arr[0]);
      // System.out.println(temp);
    }
    return temp;

  }

good day!!!!

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.