Fastest method to calculate sum of an array of integers? lazarus / 62-General ---------------------------------------------------------------------- anyone · 2020-10-14 14:22 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][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i var  arr:array[1..4] of integer=(1,2,3,4);  i:integer;  sum:integer; begin  for i:=1 to 4 do    sum:=sum+arr[i];   WriteLn(sum);  ReadLn;end.  Surprisingly, the code above can be solved by this math formula (substitute 4 for "n", in this case) Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i WriteLn((n * (n+1)) div 2); But what I mean is, what if the array of integers has random numbers? ---------------------------------------------------------------------- lucamar · 2020-10-14 14:35 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 · 2020-10-14 14:50 There are some instructions for sum of 4 integers in SSE or SSE2. ---------------------------------------------------------------------- anyone · 2020-10-14 14:53 Quote from: lucamar on October 14, 2020, 04:35:25 pmWhat 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][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i type  T8Bytes = array[0..7] of Byte;var  PInt64: ^Int64;  P8Bytes:  ^T8Bytes absolute PInt64;  i:        Integer;begin  for i := 0 to 7 do    P8Bytes^[i]:=0;   P8Bytes^[0]:=255;  P8Bytes^[1]:=255;   WriteLn(PInt64^);   ReadLn;end.   Any idea? ---------------------------------------------------------------------- anyone · 2020-10-14 14:55 Quote from: Blaazen on October 14, 2020, 04:50:30 pmThere are some instructions for sum of 4 integers in SSE or SSE2. Looks nice. ---------------------------------------------------------------------- Blaazen · 2020-10-14 15:09 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][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i   getmem(PInt64, 8);  for i := 0 to 7 do    P8Bytes^[i]:=0;   P8Bytes^[0]:=255;  P8Bytes^[1]:=255;   WriteLn(PInt64^);  freemem(PInt64, 8); ---------------------------------------------------------------------- anyone · 2020-10-14 15:15 Quote from: Blaazen on October 14, 2020, 05:09:44 pmIn 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][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i type  T8Bytes = array[0..7] of Byte;var  PInt64: ^Int64;  P8Bytes:  ^T8Bytes absolute PInt64;  i:        Integer;  Test: Int64; {Added this line} begin  PInt64:=@Test; {Added this line}   for i := 0 to 7 do    P8Bytes^[i]:=0;   P8Bytes^[0]:=255;  P8Bytes^[1]:=255;   WriteLn(Test); {65535}   ReadLn;end.   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 · 2020-10-14 15:30 I don't understand why people keep making things so convolved, hence prone to error; isn't this easier? Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i type  { Custom type for clarity's sake }  TConvRec = packed record    case Boolean of    True : (AsBytes: array[0..7] of Byte);    False: (AsInt: Int64);  end; var  ConvRec: TConvRec; begin  FillByte(ConvRec, SizeOf(ConvRec), 0);  { or just: ConvRec.AsInt := 0; }   ConvRec.AsBytes[0] := $FF;  ConvRec.AsBytes[1] := $FF;   WriteLn(ConvRec.AsInt); {65535}   ReadLn;end.    Quote from: anyone on October 14, 2020, 05:15:08 pmAlso, 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 · 2020-10-14 15:40 @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 · 2020-10-14 15:45 Quote from: anyone on October 14, 2020, 05:40:15 pmBesides 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 · 2020-10-14 15:53 Quote from: lucamar on October 14, 2020, 05:45:39 pmQuote from: anyone on October 14, 2020, 05:40:15 pmBesides 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 · 2020-10-14 18:31 Quote from: anyone on October 14, 2020, 05:53:12 pmI 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 · 2020-10-14 18:33 Quote from: lucamar on October 14, 2020, 05:45:39 pmQuote from: anyone on October 14, 2020, 05:40:15 pmBesides 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.