• helxi (1/1) Jun 11 2017 Is it possible to sum an array in O(1)?
• Stefan Koch (6/7) Jun 11 2017 No.
• Biotronic (11/18) Jun 11 2017 On a multi-core system we can do better:
• Stefan Koch (3/22) Jun 12 2017 Biotronic how do you arrive at O(log(N)) ??
• H. S. Teoh via Digitalmars-d-learn (24/41) Jun 12 2017 His stated presupposition is arbitrary parallelism, which I assume means
• =?UTF-8?Q?Ali_=c3=87ehreli?= (4/5) Jun 12 2017 It's possible to maintain the sum as elements are added and removed.

helxi <brucewayneshit gmail.com> writes:

Is it possible to sum an array in O(1)?

Stefan Koch <uplink.coder googlemail.com> writes:

On Monday, 12 June 2017 at 01:02:58 UTC, helxi wrote:
 Is it possible to sum an array in O(1)?

No.
If you want to sum the elements you have to at-least look at all 
the elements.
So it'll always be O(N).
it's the best you can do.

Biotronic <simen.kjaras gmail.com> writes:

On Monday, 12 June 2017 at 01:36:04 UTC, Stefan Koch wrote:
 On Monday, 12 June 2017 at 01:02:58 UTC, helxi wrote:
 Is it possible to sum an array in O(1)?

 No.
 If you want to sum the elements you have to at-least look at 
 all the elements.
 So it'll always be O(N).
 it's the best you can do.

On a multi-core system we can do better:

auto nums = iota(10_000_000.0f);
auto sum = taskPool.reduce!"a + b"(nums);

Given arbitrary parallelism (yeah, right!), this will be 
O(log(N)). For real-world systems, it might give a speed-up for 
large arrays, but won't reduce the big-O complexity. Of course, 
there will also be overhead to such a solution, so there is a 
limit to how much one'd actually benefit from it.

--
   Biotronic

Stefan Koch <uplink.coder googlemail.com> writes:

On Monday, 12 June 2017 at 06:15:07 UTC, Biotronic wrote:
 On Monday, 12 June 2017 at 01:36:04 UTC, Stefan Koch wrote:
 On Monday, 12 June 2017 at 01:02:58 UTC, helxi wrote:
 Is it possible to sum an array in O(1)?

 No.
 If you want to sum the elements you have to at-least look at 
 all the elements.
 So it'll always be O(N).
 it's the best you can do.

 On a multi-core system we can do better:

 auto nums = iota(10_000_000.0f);
 auto sum = taskPool.reduce!"a + b"(nums);

 Given arbitrary parallelism (yeah, right!), this will be 
 O(log(N)). For real-world systems, it might give a speed-up for 
 large arrays, but won't reduce the big-O complexity. Of course, 
 there will also be overhead to such a solution, so there is a 
 limit to how much one'd actually benefit from it.

 --
   Biotronic

Biotronic how do you arrive at  O(log(N)) ??
And which logarithm  ?

"H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:

On Mon, Jun 12, 2017 at 06:16:06PM +0000, Stefan Koch via Digitalmars-d-learn
wrote:
 On Monday, 12 June 2017 at 06:15:07 UTC, Biotronic wrote:

[...]
 On a multi-core system we can do better:
 
 auto nums = iota(10_000_000.0f);
 auto sum = taskPool.reduce!"a + b"(nums);
 
 Given arbitrary parallelism (yeah, right!), this will be O(log(N)).
 For real-world systems, it might give a speed-up for large arrays,
 but won't reduce the big-O complexity. Of course, there will also be
 overhead to such a solution, so there is a limit to how much one'd
 actually benefit from it.
 
 --
   Biotronic

 
 Biotronic how do you arrive at  O(log(N)) ??
 And which logarithm  ?

His stated presupposition is arbitrary parallelism, which I assume means
arbitrary number of CPUs or cores that can run in parallel, so then you
can divide the array of N elements into N/2 pairs, sum each pair in
parallel, which gives you N/2 subtotals after one iteration, then you
recursively repeat this on the subtotals until you're left with the
final total. The complexity would be O(log_2(N)) iterations, assuming
that the constant factor hidden by the big-O covers the overhead of
managing the parallel summing operations across the arbitrary number of
cores.

You can also get logarithms of a different base if you divided the
initial array, say, into triplets or j-tuplets, for some constant j.
Then you'd get O(log_j(N)). (Of course, with a slightly larger constant
factor, assuming that each CPU core only has binary summation
instructions. But if your instruction set has multiple-summation
instructions you may be able to get a higher j at little or no
additional cost. Assuming you can produce a machine with an unlimited
number of cores in the first place.)

Of course, his comment "yeah, right!" indicates that he's aware that
this is an unrealistic scenario. :-)


T

-- 
Notwithstanding the eloquent discontent that you have just respectfully
expressed at length against my verbal capabilities, I am afraid that I must
unfortunately bring it to your attention that I am, in fact, NOT verbose.

=?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:

On 06/11/2017 06:02 PM, helxi wrote:
 Is it possible to sum an array in O(1)?

It's possible to maintain the sum as elements are added and removed. 
Then, accessing it would be O(1).

Ali