Scribd
Upload
6 views3 pages

Prob-Popcount Stream Aggregator Java

The document outlines a task to compute a deterministic aggregate value (H) from multiple independent streams of pseudo-random integers. It specifies the input parameters, stream initialization, recurrence, and the formula for calculating H using popcount. The constraints and concurrency design suggestions are also provided to guide implementation in Java.

Uploaded by

manideepiitg31
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views3 pages

Prob-Popcount Stream Aggregator Java

The document outlines a task to compute a deterministic aggregate value (H) from multiple independent streams of pseudo-random integers. It specifies the input parameters, stream initialization, recurrence, and the formula for calculating H using popcount. The constraints and concurrency design suggestions are also provided to guide implementation in Java.

Uploaded by

manideepiitg31
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Java 2

Popcount Stream Aggregator


Background
A telemetry system receives events from multiple independent sources (“streams”).
Each stream produces a deterministic sequence of pseudo-random 31-bit non-negative
integers.
Your task is to compute a deterministic aggregate value (H).

Input
One line containing five integers:

P C B N seed

Meaning of the parameters


P : Number of independent streams (sources). Streams are indexed p = 0, 1, … , P − 1 .
N : Number of generated values per stream. Each stream generates x p,1 , x p,2 , … , x p,N .
seed : A signed 64-bit integer used to initialise each stream.

The following two values are provided as recommended concurrency design parameters:

C : Suggested number of worker threads (consumers) if you implement a parallel


solution.
B : Suggested capacity of a bounded buffer if you implement a producer–consumer
pipeline.

Important: C and B do not change the mathematical result.


They are included only to encourage a concurrency-based implementation. and
Implement a [Link]

Definitions
Let:

31
MOD31 = 2

M = 1,000,000,009
We define P independent streams. All values in the streams are computed modulo 2 31
(so
they stay in [0, 2 − 1]).
31

Stream initialisation
For each stream p = 0.. P − 1 :
31
x p,0 = (seed + 0x9E3779B9 ⋅ p) mod 2

After applying mod 2


31
,x p,0
must be in the range [0, 2 31
.
− 1]

Stream recurrence
For each stream p and for i = 1.. N :
31
x p,i = (1103515245 ⋅ x p,i−1 + 12345) mod 2

Popcount
Let pc(x) be the number of 1-bits in the binary representation of x (popcount).

Task
Compute:

P −1 N

H = (∑ ∑(pc(x p,i ) ⋅ (p + 1) ⋅ i)) mod M

p=0 i=1

Output
Print a single integer (H).

Constraints
1 ≤ P ≤ 32

1 ≤ C ≤ 32

1 ≤ B ≤ 100000

1 ≤ N

P ⋅ N ≤ 20000000

seed fits in signed 64-bit integer


Sample
Sample Input

2 2 4 3 7

Sample Output

287

Notes
All generator arithmetic is performed modulo 2 31
(keep only the lowest 31 bits).
The output is deterministic. If you use threads, your result must still be deterministic.
(C) and (B) are hints for concurrency design:
Use (C) threads to split streams among workers.
If you implement producer–consumer, (B) may be used as the buffer capacity.

You might also like