How the fuck do I write a sum function for an array that is O(log n) or better? I don't see any other way around it without recursion or looping
>>7883502
I don't know. You could instead get educated on race and iq.
http://www.amazon.com/Bell-Curve-Intelligence-Structure-Paperbacks/dp/0684824299
Wtf did you read the question right?
There is no way to get better than O(n) because you have to look at each element.
>>7883512
/pol/ apparently cause of all of these bigots...
>>7883513
That's what I thought... a trick question?
>>7883502
Definitely impossible.
>>7883521
NIGGER
I
G
G
E
R
>>7883598
Read up on your eugenic.
>>7883746
>>7883753
>knows he's being baited
>still replies
this is why /pol/ raids /sci/ you newfag. you deserve everything you get
>>7883513
O(1) is the best. O(logn) is 2nd best. get educated you numb skull
>>7883757
We must stand up to white genocide. Anti-racist is codeword for anti-white.
>>7883502
for i=1:log2(n)
parallel_for j=1:1<<i:log2(n)
A(j)=A(j)+A(j+1<<i);
parallel end
end
>>7883763
>>7883502
>partition the array into subarrays
>have a multiple threads work on each subarray.
>profit!
but on a serious note. You can't get any better than O(nlogn) algorithmically speaking. This is because you have to deal with n amount of elements. and splitting/partitioning the array is just log(n)
Thus why can't get any better than O(nlogn)
>>7883785
Why is the algorithm that just linearly goes through the list cumulatively adding not O(n)?
>>7883799
Faggots don't care about white genocide.
>>7883792
You <i>can</i> do it this way, but it's highly inefficient. It's far better to utilize multithreading to something like this.
I recommend utilizing Java, as it comes with Thread object. Just remember to synchronization, or you'll get race conditions. This is the honestly the best you can do
>>7883785
what the fuck? you just iterate, genius
>>7883807
Yes yes, nice false flag making /pol/ look bad. You can leave reddit
>>7883813
>utilizing Java
>>7883785
Would using multiple threads count as reducing the complexity? The number of basic operations is still the same. And how many threads can be used at once? Unless it's arbitrarily high, it won't scale with the growth of input size.
>>7883813
>java
>html tags
>>7883815
Iteration takes a fuck long time, but hey if you want to waste time iterating longer than you need to, go for it.
>>7883828
You're correct on this. But at least it would minimize ETA.
think of it this way.
if it takes 10 minutes to do one task done by one thread.
but it takes 5 minutes to do two tasks done by two threads.
>take the multi-threaded solution.
>>7883850
Granted I'm making a very broad assumption and i'm not accounting for context switching in a single processor CPU. So lets just assume that we're not living in the stone age with single core processors and actually are utilizing multicore CPUs
Utilize Pthreads. This is a summation program!
[code]
#include <pthread.h>
#include <stdio.h>
int sum; /* this data is shared by the thread(s) */
void *runner(void *param); /* threads call this function */
int main(int argc, char *argv[])
{
pthread_t tid; /* the thread identifier */
pthread_attr_t attr; /* set of thread attributes */
if (argc != 2) {
fprintf(stderr,"usage: a.out <integer value>\n");
return -1;
}
if (atoi(argv[1]) < 0) {
fprintf(stderr,"%d must be >= 0\n",atoi(argv[1]));
return -1;
}
/* get the default attributes */
pthread_attr_init(&attr);
/* create the thread */
pthread_create(&tid,&attr,runner,argv[1]);
/* wait for the thread to exit */
pthread_join(tid,NULL);
printf("sum = %d\n",sum);
}
/* The thread will begin control in this function */
void *runner(void *param)
{
int i, upper = atoi(param);
sum = 0;
for (i = 1; i <= upper; i++)
sum += i;
pthread_exit(0);
}
[/code]
>>7883866
>pthreads
>not std::threads
What the fuck are you doing? It's 2011+5
>>7883894
just staying current and up to date.
get on my level you scrub!
>>7883502
After reading this thread, I think I understand what your book or whatever had in mind.
Assuming the processor is multi-core, you can recursively partition the list and assign the summing of each partition to a different core, and then add the results.
Of course, each of the two cores would do the same, slipping the array in half and assigning each to two more cores and summing the results. When a core receives an array with only one number, it returns that number.
This sums the array in log(n) time.
>>7883502
Well if you know how long the array is you can write a function with input (begin, mid, end), which splits the array in (begin, secondMid, mid) and (mid, thirdMid, end), sums them up, and then goes on like this. If the length of the array is 1, it just returns the element.
>>7884011
you've got it.
But remember that the amount of processors needed is log(n) amount. So for 32 elements alone you'll need 5 processors, to pull off exactly log(n) time
>>7884018
Even for an array with a quintillion elements, you need only 60 processors.
It really is completely reasonable to assume there are enough processors.
>>7884026
Yeah, I was thinking that as well.
>>7884018
>processors needed is log(n)
No, it's 2n-1 (or n/2 if you're less retarded with how you create and remove threads).
It's a tree where each node is a thread and the leaves are the elements in the array being added. Each level is done at the same time so the time is log2(n).
>>7884030
>>7884026
>and CS majors will deny they are retarded.
>>7884026
If you know that your array has at most a quintillion elements then there is an O(1) algorithm.
>>7883850
>if it takes 10 minutes to do one task done by one thread.
>but it takes 5 minutes to do two tasks done by two threads.
Would multithreading really achieve that? Seems to me that two threads would do twice as many tasks in the same time, or the same number of tasks in half the time. Wouldn't you need four threads to do twice the work in half the time?
>>7883502
if you need it for a exercise, you can't. if you need it because you have 1kk elements and the program is not fast enough, just create a wraparound the array that keeps track of the sum every time it's changed
1 2
2 4
3 8
4 16
5 32
6 64
7 128
8 256
9 512
10 1024
11 2048
12 4096
13 8192
14 16384
15 32768
16 65536
17 131072
18 262144
19 524288
20 1048576
21 2097152
22 4194304
23 8388608
24 16777216
25 33554432
26 67108864
27 134217728
28 268435456
29 536870912
30 1073741824
31 2147483648
32 4294967296
33 8589934592
34 17179869184
35 34359738368
36 68719476736
37 1.37439E+11
38 2.74878E+11
39 5.49756E+11
40 1.09951E+12
41 2.19902E+12
42 4.39805E+12
43 8.79609E+12
44 1.75922E+13
45 3.51844E+13
46 7.03687E+13
hehe numbers
OP here, this is just for a simple intro to Algorithms class. This thread was very interesting, thanks for all who contributed!
>>7884684
>using scientific notation for integers
37 137438953472
38 274877906944
39 549755813888
40 1099511627776
41 2199023255552
42 4398046511104
43 8796093022208
44 17592186044416
45 35184372088832
46 70368744177664
47 140737488355328
48 281474976710656
49 562949953421312
50 1125899906842624
51 2251799813685248
52 4503599627370496
53 9007199254740992
54 18014398509481984
55 36028797018963968
56 72057594037927936
57 144115188075855872
58 288230376151711744
59 576460752303423488
60 1152921504606846976
61 2305843009213693952
62 4611686018427387904
63 9223372036854775808
64 18446744073709551616
>>7883763
Where does O(2) fit in?
>>7885102
O(2) = O(1)
>>7885102
>>>/middleschool/
>>7885102
When it comes to complexity, any constant multipliers/coefficients are dropped, so 2 is really just 1X (with x = 2) which is the same as 1.
>>7885140
That can't possibly be true. Since [math]O(n) \ne O(n^2)[/math], we have that [math]O \ne 0[/math].
It then follows that if [math]O(2) = O(1)[/math], then [math]\frac{O(2)}{O} = \frac{O(1)}{O}[/math], but since [math]O[/math] is not 0, we have that [math]1 = 2[/math], which is a contradiction. Therefore, [math]O(2) \ne O(1)[/math].
[math]Q.E.D.[/math]
>>7883502
I think there needs to be a different architecture of programming to get anything better than log n. Its just not possible with what we have.
Make your own language
