Fastest method to calculate sum of an array of integers?

[anyone]

I know 32-bit integer can be split into 4x Byte array using "absolute" and pointer (as shown by @Handoko in one of his recent reply)

But what about opposite approach? Given an array of multiple integers, is there any faster way to calculate the sum of it? Maybe some sort of BigInteger in Pascal, which interpret an array of integers as continuous memory allocation of a BigInteger?

This is an example code to calculate the sum from 1 to 4.

Code: Pascal  [Select][+][-]

1. var
2.   arr:array[1..4] of integer=(1,2,3,4);
3.   i:integer;
4.   sum:integer;
5.  
6. begin
7.   for i:=1 to 4 do
8.     sum:=sum+arr[i];
9.  
10.   WriteLn(sum);
11.   ReadLn;
12. end.
13.  

Surprisingly, the code above can be solved by this math formula (substitute 4 for "n", in this case)

Code: Pascal  [Select][+][-]

1. WriteLn((n * (n+1)) div 2);

But what I mean is, what if the array of integers has random numbers?

[lucamar]

What you're asking has nothing to do with the premise from which you start: this last "splits" a 32 bit integer into its separated bytes but you're asking for a sum of integers?

For this last task a loop like you show is probably the best option, though note that if you use Integer for all your values you may run into overflow problems, as you probably know already.

If instead you want to "join" 4 bytes to build an integer then a solution like Handoko's is probably the best, though instead of using absolute and pointers I would probably use a variant record ...

[Blaazen]

There are some instructions for sum of 4 integers in SSE or SSE2.

[anyone]

What you're asking has nothing to do with the premise from which you start: this last "splits" a 32 bit integer into its separated bytes but you're asking for a sum of integers?

For this last task a loop like you show is probably the best option, though note that if you use Integer for all your values you may run into overflow problems, as you probably know already.

If instead you want to "join" 4 bytes to build an integer then a solution like Handoko's is probably the best, though instead of using absolute and pointers I would probably use a variant record ...

Yes, noted. I meant an opposite approach:

The following supposed to print "65535" but it just did not work.

Code: Pascal  [Select][+][-]

1. type
2.   T8Bytes = array[0..7] of Byte;
3. var
4.   PInt64: ^Int64;
5.   P8Bytes:  ^T8Bytes absolute PInt64;
6.   i:        Integer;
7. begin
8.   for i := 0 to 7 do
9.     P8Bytes^[i]:=0;
10.  
11.   P8Bytes^[0]:=255;
12.   P8Bytes^[1]:=255;
13.  
14.   WriteLn(PInt64^);
15.  
16.   ReadLn;
17. end.
18.  
19.  

Any idea?

[anyone]

There are some instructions for sum of 4 integers in SSE or SSE2.

Looks nice.

[Blaazen]

In your code you declared one type and two pointers but actually no variable (except i, but it is for loop only).

EDIT:

Code: Pascal  [Select][+][-]

1.   getmem(PInt64, 8);
2.   for i := 0 to 7 do
3.     P8Bytes^[i]:=0;
4.  
5.   P8Bytes^[0]:=255;
6.   P8Bytes^[1]:=255;
7.  
8.   WriteLn(PInt64^);
9.   freemem(PInt64, 8);

[anyone]

In your code you declared one type and two pointers but actually no variable (except i, but it is for loop only).

Thank you.

Code: Pascal  [Select][+][-]

1. type
2.   T8Bytes = array[0..7] of Byte;
3. var
4.   PInt64: ^Int64;
5.   P8Bytes:  ^T8Bytes absolute PInt64;
6.   i:        Integer;
7.   Test: Int64; {Added this line}
8.  
9. begin
10.   PInt64:=@Test; {Added this line}
11.  
12.   for i := 0 to 7 do
13.     P8Bytes^[i]:=0;
14.  
15.   P8Bytes^[0]:=255;
16.   P8Bytes^[1]:=255;
17.  
18.   WriteLn(Test); {65535}
19.  
20.   ReadLn;
21. end.
22.  
23.  

So it is actually working! But I just need large enough BigInteger to be referenced from an array of Integer (instead of Byte).

Also, this does not solve the problem, because sum of an array of integers from  1..4 is not the same as declaring P8Bytes[0]:=1, P8Bytes[1]:=2; P8Bytes[2]:=3 and P8Bytes[3]:=4. The result would be different though.

[lucamar]

I don't understand why people keep making things so convolved, hence prone to error; isn't this easier?

Code: Pascal  [Select][+][-]

1. type
2.   { Custom type for clarity's sake }
3.   TConvRec = packed record
4.     case Boolean of
5.     True : (AsBytes: array[0..7] of Byte);
6.     False: (AsInt: Int64);
7.   end;
8.  
9. var
10.   ConvRec: TConvRec;
11.  
12. begin
13.   FillByte(ConvRec, SizeOf(ConvRec), 0);
14.   { or just: ConvRec.AsInt := 0; }
15.  
16.   ConvRec.AsBytes[0] := $FF;
17.   ConvRec.AsBytes[1] := $FF;
18.  
19.   WriteLn(ConvRec.AsInt); {65535}
20.  
21.   ReadLn;
22. end.

  

Also, this does not solve the problem, because sum of an array of integers from  1..4 is not the same as declaring P8Bytes[0]:=1, P8Bytes[1]:=2; P8Bytes[2]:=3 and P8Bytes[3]:=4. The result would be different though.

Of course. You have to specify exactly what you want to do; we can't help otherwise. What do you want: Be able to specify each byte that goes inside an integer or add an array of integers?

[anyone]

@Blaazen

Thanks for the getmem and freemem keyword, learned something new today!

 @Lucamar

Wow, this is nice, also something new to me. Looks a lot more convenient.

Besides this, do you have any idea to calculate sum in an array of byte/integer: (I mean using memory addressing, quickest way)

255+255=510 (instead of 65535)?

Anyway, I am glad it works both way (in original @Handoko example, @Blaazen modified code, and @Lucamar new example).

[lucamar]

Besides this, do you have any idea to calculate sum in an array of byte/integer: (I mean using memory addressing, quickest way)

IMHO, the quickest is to use a normal, tightest-as-possible loop, like you were doing, and let the compiler optimize that however it thinks best.

[anyone]

Besides this, do you have any idea to calculate sum in an array of byte/integer: (I mean using memory addressing, quickest way)

IMHO, the quickest is to use a normal, tightest-as-possible loop, like you were doing, and let the compiler optimize that however it thinks best.

I think you're right. I'll just leave it to compiler optimization. Thank you!

[MarkMLl]

I think you're right. I'll just leave it to compiler optimization. Thank you!

He's definitely right. Somebody was asking similar questions a few weeks ago but in his case the values couldn't be guaranteed to be contiguous: it's the sort of thing that in principle the compiler can sort out much more easily than you can do it by hand.

If for some reason you find it taking longer than is reasonable, or examining the generated code suggests that the compiler is making some bad choices, /then/ you start looking for ways to improve it. But more often than not manual optimisations will mean fixing badly-chosen data structures rather than manual code generation.

MarkMLl

[marcov]

Besides this, do you have any idea to calculate sum in an array of byte/integer: (I mean using memory addressing, quickest way)

IMHO, the quickest is to use a normal, tightest-as-possible loop, like you were doing, and let the compiler optimize that however it thinks best.

The compiler doesn't vectorize, so for large arrays sse2/avx2 will be faster. On 64-bit the definition of "large" is smaller.